如果启发式函数以一致的方式高估，那么在 A* 搜索中，可接受性是否重要？

Question

如果一个节点的启发值是，让\xe2\x80\x99s 说，达到目标的实际成本 x 10^5 该怎么办？f 成本最小的节点仍然从优先级队列的顶部弹出。

\n\n

例如：f(n) = g(n) + h(n)，where h(n) = h1(n) x 10^5, where h1(n) = h1\xe2\x80\xb2(n)

\n\n

根据定义，h这是对实现目标的实际成本的高估。

\n\n

我问这个问题的原因是因为我无法真正看到有或没有这个常数因子的算法性能的差异。如果那么的话，为什么 h 是否可以接受有那么重要呢？

\n

Answer 1

是的：

1. 一般来说：可接纳性是A*最优性的充分条件，而不是必要条件。当然，您可能会发现存在一种不可接受的启发式方法，但它也会返回最佳结果；只是 A* 此时不提供任何保证。

2. 特别是：“以一致的方式”是模糊的，但如果您考虑“扩展”以适应此描述，请注意，如果成本不相加，您的扩展启发式可能会失败。请注意，A* 不要求评估函数为 f = g + h。虽然乍一看不直观，但问题完全可能且现实地具有其他评估函数，而在这些函数中添加路径成本甚至没有意义（例如，您的成本可能是概率）。

另请注意，“一致性”的含义与您所使用的含义完全不同，因此在使用该术语时要小心。根据通常的定义，一致的启发式不可能不可接受。