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

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

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

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

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

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

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

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

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

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