用 A* 找到最长的路径

Question

我想弄清楚是否可以使用 A* 算法在可接受性假设下确定最长的目标路径。

我试过最大max(f(n)=g(n)+h(octile-distance))，但我觉得不对。

1. 如果可接受的启发式方法是低估 f*，对于最长路径，我必须找到总是高估 f*?

   [= 的启发式方法27=]

2. 根据 1，如果我需要高估到目标的地理距离。有人可以向我推荐某种启发式方法吗？

3. 像这样用A*求最长路径是最优的吗？

Answer 1

正在寻找 longest path is NP-Hard，因此尝试采用 A* 或任何其他最短路径算法来找到它很遗憾是行不通的。