Алгоритм A * работает с отрицательными весами ребер?

Question

Я пытался выяснить, почему эвристика, используемая в поиске дерева A *, должна быть допустимой, если A * должна быть оптимальной.Под поиском по дереву я имею в виду, что исследуемый набор не поддерживается алгоритмом.

При этом я столкнулся с вопросом: работает ли A * для отрицательных весов ребер?

Answer 1

Алгоритм A * в основном Алгоритм Дейкстры с эвристикой. А алгоритм Дейкстры не работает с отрицательными весами ребер. Так что A * не будет работать и с отрицательным весом ребер.

Если вы ищете алгоритм, который работает с отрицательными весами, взгляните на алгоритм Беллмана-Форда (но он не использует эвристику).

Answer 2

Эта превосходная статья о Дейкстре может оказаться полезной и послужит хорошим примером отрицательных краев ...

http://www.ics.uci.edu/~eppstein/161/960208.html