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

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

Общая стоимость (сумма ресурсов) пути не очень важна, но она должна быть больше 0, а длина должна быть минимально возможной.

Например, рассмотрим такой график:

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

Кратчайший путь будет A-E-F-E-D

Сам по себе алгоритм Дейкстры не работает, потому что он не может обрабатывать отрицательные значения. Итак, я подумал о нескольких решениях:

Сначала используется алгоритм Дейкстры для вычисления длины кратчайшего пути от каждого узла до выходного узла без учета весов. Это можно использовать как своего рода эвристическое значение, как в A *. Я не уверен, что это решение сработает, к тому же оно очень дорогое. Я также думал о реализации алгоритма Флойда-Уоршалла, но не знаю, как это сделать.

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

Например:

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

Не могли бы вы помочь мне решить эту проблему?

РЕДАКТИРОВАТЬ: Если при вычислении кратчайшего пути вы достигли точки, в которой сумма ресурсов равна нулю, этот путь недействителен, поскольку вы не можете продолжать движение, если больше нет бензина.


java algorithm shortest-path dijkstra floyd-warshall
person foobars    schedule 06.01.2012    source источник
comment
В этом примере, будет ли A-E-A-E-D также подходящим решением?   -  person mbeckish    schedule 06.01.2012
comment
На первый взгляд кажется, что есть 2 способа увеличить сумму ресурсов: 1) отклониться от кратчайшего пути, чтобы найти ближайший узел с высоким ресурсом, и 2) колебаться между двумя узлами на кратчайшем пути с увеличением чистой суммы ресурсов. Тогда уловка состоит в том, чтобы вычислить эвристику, чтобы определить, какой вариант выбрать.   -  person mbeckish    schedule 06.01.2012
comment
Я думаю, что основная проблема, которую вы не можете применить dijkstra, НЕ в том, что веса отрицательны (вы можете добавить минимальный вес ко всем весам), более того, что один узел можно посещать несколько раз ...   -  person Karussell    schedule 09.08.2012
comment
Да, вы правы, теоретически я мог бы использовать положительные черты, но не мне было разрабатывать графики. Вы не всегда можете свободно программировать то, что хотите.   -  person foobars    schedule 10.08.2012

Ответы (4)


arrow_upward
2
arrow_downward

Это не кажется изящным решением, но, учитывая возможность создавать циклические пути, я не вижу способа обойти это. Но я бы просто решил итеративно. Используя второй пример - начните с точки в точке A, дайте ей значение A. Переместитесь на один «поворот» - теперь у меня есть две точки, одна в точке B со значением 5, а другая в точке D также со значением 5. Переместитесь снова - теперь у меня есть 4 точки, которые нужно отслеживать. C: 45, A: 15, A: 15 и E: 0. Возможно, тот, что находится в E, может колебаться и стать действительным, поэтому мы пока не можем его выбросить. Перемещение и накопление и т. Д. Когда вы впервые достигнете конечного узла с положительным значением, вы закончите (хотя могут быть дополнительные эквивалентные пути, которые входят в тот же ход)

Очевидно, проблема заключается в том, что количество точек для отслеживания будет расти довольно быстро, и я предполагаю, что ваш фактический график намного сложнее, чем пример.

person Mikeb    schedule 06.01.2012
comment
определенно решает проблему, но он должен быть более эффективным, чем это - person foobars; 06.01.2012
comment
Кроме того, если какой-то путь в какой-то момент достигает 0, его следует отбросить. Так и должно быть. Если у вас закончится бензин, вы не сможете двигаться дальше. Я забыл упомянуть об этом в описании, извините за это. - person foobars; 06.01.2012

arrow_upward
4
arrow_downward

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

Алгоритм Беллмана-Форда решает проблему кратчайшего пути из одного источника даже при наличии ребер с отрицательным весом. Однако он не обрабатывает отрицательные циклы (круговой путь на графике с отрицательной суммой весов). Если ваш график содержит отрицательные циклы, у вас, вероятно, проблемы, потому что я считаю, что это делает проблему NP-полной (потому что это соответствует задача самого длинного простого пути).

person Aasmund Eldhuset    schedule 06.01.2012

arrow_upward
1
arrow_downward

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

Используя ваш пример графика:

График состояний, полученный на основе вашего примера графика

  • Octagons: закончилось топливо
  • Поля: Дочерние узлы опущены из-за недостатка места

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

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

person DataWraith    schedule 07.01.2012

arrow_upward
0
arrow_downward

Попробуйте добавить абсолютное значение минимального веса (в данном случае 5) ко всем весам. Это позволит избежать негативных циклических путей

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

Удачи

person jorgeu    schedule 06.01.2012
comment
ой! также здесь ссылка Некоторые люди пытаются оптимизировать dijsktra, когда вам нужно решение только для 1 узла - person jorgeu; 06.01.2012
comment
Я не думаю, что это сработает - итоговые веса будут A: 15, E: 0, D: 0; оставив впечатление, что A-E-D был правильным путем. - person Mikeb; 06.01.2012