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

Question

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

Пусть G - ориентированный граф с некоторыми отрицательными ребрами.Мы хотим запустить A * на G.

Во-первых, если G имеет отрицательные циклы, достижимые из источника и достигающие цели, нет допустимой эвристики, поскольку невозможно недооценить стоимостьдостижение цели, потому что это -∞.

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

У меня сложилось впечатление, что в этом случае A * может работать просто отлично.

PSЯ мог бы запустить Беллмана-Форда на графике, обнаружить отрицательные циклы, а если их нет, перевесить, чтобы избавиться от отрицательных ребер.Но, если я знаю , что нет отрицательных циклов, я могу просто пропустить это и запустить A *.

---

Это тривиально неправильно.Стоимость вершины - это сумма эвристики и пути, построенной до сих пор ... в то время как эвристика недооценивает стоимость достижения цели, сумма эвристики и пройденного пути может и не быть.Максима виноват.

Кажется, что сортировка открытого множества с помощью функции, которая недооценивает стоимость достижения цели, при прохождении через данную вершину может работать, хотя ... если использовать <sum of negative edges in the graph> в качестве такой функции, она выглядиткак будто вырождается в обход графа.

Answer 1

Рассмотрим пример с 3 узлами и 3 весами:

1 2 -10
1 3 -3
3 2 -8

От 1 до 2 есть путь с весом -10.Таким образом, вы получите это первым и установите его как минимальный путь к 2. Однако есть путь (1-3-2), который меньше первого.

Answer 2

В примере с ответом с самым высоким рейтингом: (2, -10) помещается в очередь с приоритетами.Согласовано.Так же, как (3, x), где x <= - 11 как эвристика допустима.Теперь (3, x) отображается как x <-10, и мы получаем правильное решение. </p>

Я не могу оставить это как комментарий, так как у меня недостаточно репутации.

Answer 3

Это тривиально неправильно. Стоимость вершины - это сумма эвристический и путь, построенный до сих пор ... в то время как эвристический недооценивает стоимость достижения цели, сумму эвристики и путь, пройденный до сих пор, не может.

A * никогда не расширит узел так, что сумма эвристики и пройденного пути (значение f) будет больше, чем оптимальная длина пути. Это происходит потому, что вдоль оптимального пути всегда есть один узел с f-значением, меньшим или равным оптимальной стоимости.

Таким образом, даже с ребрами с отрицательным весом A * найдет оптимальный путь, если такой путь существует, если существует конечное число ребер с f-значением, меньшим, чем оптимальная стоимость.