Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: поиск путей на графе  (Прочитано 17412 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 09-08-2009 17:08 » 

поиск путей на графе

дан ориентированый граф из 2-50 вершин, где каждому существующему ребру соотвествует рейтинг +-R, ребер соединающих вершину саму с собой не существует, нужно за кратное K число переходов, но не большее чем К*МAX, проити из вершины 0 в вершину 1, так чтобы сумма рейтингов переходов была максимальной и выдать полученный рейтинг

как я понимаю задачу нужно разбить на 3 этапа:

1) найти, то что существует путь приемлимой длинны из 0 в 1 кратный К - иначе выдать, что с данными параметрами задача не имеет решения ( тут могут эти вершины быть совсем не связаными, либо связаными неприемлимым каличеством перехдов которых не удасться накрутить )

2) найти цикл максимальным соотношением суммарного рейтинга к числу его переходов, если его рейтинг меньше 0, то придется просто искать оптимальный путь ( тут совершенно не понятно, как поступать в ситуациях когда есть менее привлекательный цикл, но расположеный более оптимально к вершинам при сильно ограниченном max)

3) определить количество циклов, так чтобы число переходов в циклах+вход+выход из цикла оказалось кратными К

это ваще реально решить?
Записан

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 10-08-2009 03:48 » 

наверное, так можно решить:

при помощи волнового алгоритма находим список "первых" кратчайших путей, каждый найденный путь проверяем на нужные критерии. Выбираем более подходящий путь
Записан

Mayor
Специалист

ru
Offline Offline

« Ответ #2 : 10-08-2009 10:29 » 

при помощи волнового алгоритма находим список "первых" кратчайших путей, каждый найденный путь проверяем на нужные критерии. Выбираем более подходящий путь

так бы было слишком просто, допустим нужно попасть из вершины 1 в 2 за число ходов кратное 2 но не большее, чем 2*4:
возьмем граф с 3мя вершинами и ребрами:
1-2=1
2-1=1
1-3=2
3-2=2
прямым кратчайшим путем будет 1-2, обратным 2-1, сколько по нему не ходи и не возвращайся обратно переход не кратен 2 - полученое решение отпадает

зы забыл добавить, реализация должна выдать ответ за несколько секунд работы на персоналке с ограничением по МAX<10**9
Записан

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 10-08-2009 10:44 » 

шота я не понимаю... Вот смотри:

волновик находит путь 1-2. Но этот путь не канает, атк как количество переходов нечётное.
Идём дальше, будет найден путь 1-3-2 , то, что нужно.

По времени - справится даже египетский каменный калькулятор Улыбаюсь
Записан

Mayor
Специалист

ru
Offline Offline

« Ответ #4 : 11-08-2009 15:39 » 

шота я не понимаю... Вот смотри:
волновик находит путь 1-2. Но этот путь не канает, атк как количество переходов нечётное.
Идём дальше, будет найден путь 1-3-2 , то, что нужно.
По времени - справится даже египетский каменный калькулятор Улыбаюсь

ну что осталось еще 47 вершин, добавляем:
1-2=1
2-1=1
1-3=2
3-2=2
3-4=3
4-3=3

и твой волновик сел в лужу
Записан

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 11-08-2009 16:03 » 

чёта я опять не понял
[цытато из Mayor]
возьмем граф с 3мя вершинами и ребрами:
[/цытато]

где тут 47 ?

А кроме того, волновой алгоритм работает в любой стратегии, а там этих вершин - вся карта. Да ещё каждое ребро может иметь по куче всяких свойств по проходимости. Включая и лужи

Всё прекрасно работает в реальном времени
Записан

Mayor
Специалист

ru
Offline Offline

« Ответ #6 : 11-08-2009 16:22 » 

чёта я опять не понял
[цытато из Mayor]
возьмем граф с 3мя вершинами и ребрами:
[/цытато]

где тут 47 ?

А кроме того, волновой алгоритм работает в любой стратегии, а там этих вершин - вся карта. Да ещё каждое ребро может иметь по куче всяких свойств по проходимости. Включая и лужи

Всё прекрасно работает в реальном времени

перечитай еще раз первый пост, где описана задача, вершин может быть до 50, да на них в реальном времени сможет сработать волновой алгоритм, вот только он не имеет отношения к решению этой задачи
Записан

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 11-08-2009 16:34 » 

ещё как имеет. Лучше этого алгоритма ничего нету. А если взять поле самой завалящей стратегии, 100*100 ячеек, то их там получается аж 10000, что всё ещё прекрасно обсчитывается в реальном времени Улыбаюсь
Записан

Mayor
Специалист

ru
Offline Offline

« Ответ #8 : 11-08-2009 19:06 » 

ещё как имеет. Лучше этого алгоритма ничего нету. А если взять поле самой завалящей стратегии, 100*100 ячеек, то их там получается аж 10000, что всё ещё прекрасно обсчитывается в реальном времени Улыбаюсь

да что ты говоришь ? а мне на кой эти 10к ячеек для этой задачи?
а тебя не смущает, то что еще есть другие алгоритмы на графах?
и еще почему-то в волновом отсутсвует вес ребер ...
например есть еще алгоритм дейкстры, который учитывает вес ребер, если ты про такой слышал? правда он тоже тут не подходит ...

может быть ты объяснишь, как волновой выберет 1 из нескольких циклов сумма рейтингов которых может быть максимальной?

или вернемся к первому графу с параметрами кратности 3*6:
1-2=1
2-1=1
1-3=2
3-2=2

1-2-1-2.... и так до 9 хода, хотя можно было сделать 18

это я к тому, что он прекрасно отработает в реальном времени, так и не найдя оптимального решения
Записан

1n c0de we trust
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 11-08-2009 19:13 » 

эхъ, какой тяжёлый случай... Волновой прекрасно посчитает суммарный вес. Всё зависит от желания
Записан

Mayor
Специалист

ru
Offline Offline

« Ответ #10 : 13-08-2009 16:50 » 

эхъ, какой тяжёлый случай... Волновой прекрасно посчитает суммарный вес. Всё зависит от желания

да на кой мне сумарный вес ближайшего пути?

все зависит от возможностей, ни у тебя ни у меня и у кого либо еще, возможно за исключением димки -  пока их нет
только ты этого не понимаешь, и пытаешься притянуть за уши первый попавшийся алгоритм
а я безуспешно пытался найти ссылку на какой нить еще более приближенный к этой задаче
Записан

1n c0de we trust
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines