Эвристика для использования A*, чтобы найти путь с наибольшим усилением

Question

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

В моем случае цель не фиксируется как уникальный конечный узел. Узел определяется как любой узел, имеющий расстояние B от начальной точки.

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

Вместо этого в моей модифицированной версии ("поиск наиболее полезного пути") ребра помечаются утилитой, а не стоимостью, и я хочу максимизировать конечный выигрыш, учитывая ограничение прохождения максимум B ребер. Должен ли я переоценить полезность (то есть найти эвристику, которая больше или равна реальной полезности), чтобы заставить A * работать?

РЕДАКТИРОВАТЬ: более формализовано, пусть

f(n) = g(n) + h(n)

быть утилитой узла, состоящей из:

• g(n): что я получаю при переходе от начального узла к n
• h(n): эвристический, т. е. оценка того, что я получаю при переходе от n к цели (где целью является узел, расстояние от которого до начальной точки B)

Должен h(n) быть переоцененным и f(n) быть максимальным, чтобы определить лучший путь?

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

Answer 1

Ваша проблема - самая длинная проблема пути, которая сильно NP-Hard. Это означает, что не только (почти наверняка) нет быстрого точного алгоритма, но также (почти наверняка) нет хорошего приближенного алгоритма.

К сожалению, вам придется либо перебирать его, либо прибегать к различным методам глобальной оптимизации, таким как отжиг, генетическое программирование и т. Д.

---

Отрицание знака веса ребер, как предполагает @Charles, не будет работать, так как A* не может обрабатывать отрицательные веса ребер. А другие алгоритмы, которые могут обрабатывать отрицательные веса ребер, по-прежнему не могут обрабатывать отрицательные циклы.