Как найти лучший путь в графе со взвешенными узлами и вершинами

Допустим, у меня есть этот график

пример графика

  • всегда полный график
  • один начальный узел - также финишный узел
  • взвешенные узлы и вершины

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

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

О, и это не домашнее задание, я просто хочу создать специальный поиск пути.

ИЗМЕНИТЬ

До сих пор мне удалось построить рабочий алгоритм, который может найти какой-то путь за несколько секунд. Но я не получаю столько баллов, сколько хотел бы - я набираю только около 85% от желаемого. А если я изменю параметры алгоритма, то время будет в часах и больше...


java graph shortest-path graph-algorithm
person user219882    schedule 17.03.2012    source источник
comment
Является ли график направленным? В противном случае: найдите минимальное весовое ребро (u,v) такое, что u будет вашим источником, а (u,v),(v,u) — кратчайшим путем. Вы не упомянули о каких-либо проблемах с использованием одного и того же ребра дважды.   -  person amit    schedule 17.03.2012
comment
Это не направлено. Конечно, я не могу использовать одно и то же ребро дважды — это нарушит условие, согласно которому я не могу пройтись по уже посещенным узлам.   -  person user219882    schedule 17.03.2012
comment
Вы должны посетить источник дважды, если он также является узлом назначения, как вы сказали. путь будет: v -> ... -> v, а v нужно посетить дважды.   -  person amit    schedule 17.03.2012
comment
Итак, @Tomas, возможно ли решение (start,v) -> (v,start) в вашей ситуации?   -  person amit    schedule 17.03.2012
comment
Я забыл об этом - дважды можно посетить только источник. Но твой простой путь не годится - не хватает очков. start -> 5p -> 2p -> start даст мне больше очков и ту же длину. Одним из возможных решений может быть и такое: start -> 5p -> 8p -> start (в зависимости от максимально допустимой длины).   -  person user219882    schedule 17.03.2012
comment
О, вы хотите набрать больше всего очков? не меньше очков?   -  person amit    schedule 17.03.2012
comment
Да :) Я сказал это в вопросе...   -  person user219882    schedule 17.03.2012
comment
Это очень похоже на вариант коммивояжера. Для этого существует множество довольно хороших эвристических алгоритмов. Быстрый поиск в Google укажет вам на исследовательские работы, а также на реализации.   -  person Jochen    schedule 19.03.2012
comment
Но TS проходит по всем узлам, я этого не хочу. Но, возможно, я мог бы использовать аналогичную эвристику для моего текущего алгоритма...   -  person user219882    schedule 19.03.2012

Ответы (2)


arrow_upward
1
arrow_downward

Я не думаю, что это решаемо лучше, чем время грубой силы. Вы можете рассчитать все пути до определенной длины ограничения. Однако для сколь угодно большого графа это было бы крайне медленно. Если вы ищете надежное предположение, я бы начал с жадного алгоритма, который выбирает шаг с наибольшим значением Points per Length, пока не будет достигнут предел. Затем вы можете добавить такие вещи, как реверсирование в случае преждевременного заполнения (скажем, если вы прошли 5, но ваш предел равен 6, и ваш текущий узел не имеет соединенных путей длины один), чтобы узнать, как это работает.

person FrankieTheKneeMan    schedule 17.03.2012
comment
Я думаю ты прав. Кажется, это проблема NP. Я не знаю, как совместить эффективный алгоритм с поиском пути. Брутфорс с эвристикой и ветвями и границами по-прежнему бесполезен — время огромно, потому что у меня около 80 узлов. - person user219882; 19.03.2012

arrow_upward
0
arrow_downward

Я не уверен, что это действительно сработает, но вот мои первоначальные мысли:

Возможно, попробуйте с максимальным связующим деревом (Прима или Крускала). Поскольку вы не хотите повторять вершины, ваш путь должен в конечном итоге стать графом цикла. Пройдитесь по остовному дереву (может быть, какой-то жадный алгоритм?), и как только вы наткнетесь на лист, вернитесь к начальной вершине (поскольку исходный граф был полным графом). Это сработало бы (возможно) только в том случае, если бы не было отрицательных весов ребер.

Пока только некоторые мысли - уже поздно, утром посмотрю внимательнее. :)

person adelbertc    schedule 18.03.2012