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

Question

假设节点的启发值是达到目标的实际成本 x 10^5 怎么办？具有最小 f 成本的节点仍然从优先级队列的顶部弹出。

例如:f(n) = g(n) + h(n)，其中 h(n) = h1(n) x 10^5，其中 h1(n ) = h1′(n)

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

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

Answer 1

是:

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

2. 特别是:“以一致的方式”含糊不清，但如果您考虑“缩放”以符合此描述，请注意您的缩放启发式可能会失败如果成本不是添加剂。请注意，A* 不要求评估函数为 f = g + h。虽然乍一看不直观，但一个问题完全有可能且现实地具有其他评估函数，其中 甚至没有意义 添加路径成本(例如，您的成本可能是概率)。

另请注意“一致性”has an entirely different meaning比您正在使用的那个，所以在使用该术语时要小心。在通常的定义下，一致性启发式不可能是 Not Acceptable 。