Найдите самый длинный путь с A *

Question

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

Я пробовал с максимальным max(f(n)=g(n)+h(octile-distance)), но мне кажется, что это неправильно.

1. Если допустимая эвристика недооценивает f*, для самого длинного пути мне нужно было найти эвристику, которая всегда переоценивает f*?

2. Согласно 1, если мне нужно переоценить географическое расстояние до цели.кто-то может порекомендовать меня для какой-нибудь эвристики?

3. Оптимально ли найти самый длинный путь с A *, как этот?

Answer 1

Нахождение самого длинного пути - NP-Hard , поэтому попытка адаптировать A * или любой другой алгоритм кратчайшего пути, чтобы найти его, к сожалению, не будет работать.