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

[Mayor]

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

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

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

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

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

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

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

[Алексей++]

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

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

[Mayor]

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

так бы было слишком просто, допустим нужно попасть из вершины 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

[Алексей++]

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

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

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

[Mayor]

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

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

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

[Алексей++]

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

где тут 47 ?

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

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

[Mayor]

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

где тут 47 ?

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

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

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

[Алексей++]

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

[Mayor]

ещё как имеет. Лучше этого алгоритма ничего нету. А если взять поле самой завалящей стратегии, 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

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

[Алексей++]

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

[Mayor]

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

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

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