产生负值的启发式函数是否不可接受？

Question

据我了解，对于给定的评估节点，启发式算法的可接受性保持在“距离的实际成本”的范围内。我不得不为状态空间上的 A* 解决方案搜索设计一些启发式方法，并且使用有时可能返回负值的启发式方法获得了很多积极的效率，因此使某些节点与目标更“紧密地形成”国家在边疆的地位更高。

但是，我担心这是不可接受的，但无法在网上找到足够的信息来验证这一点。我确实找到了德克萨斯大学的这篇论文，它似乎在后来的证明之一中提到“......因为启发式函数是非负的”。任何人都可以证实这一点吗？我认为这是因为返回负值作为您的启发式函数会使您的 g-cost 变为负值（因此会干扰 A* 的“默认”dijkstra-esque 行为）。

Answer 1

结论：产生负值的启发式函数本身并不是不可接受的，但有可能破坏 A* 的保证。

有趣的问题。从根本上来说，可接受性的唯一要求是启发式永远不会高估距目标的距离。这很重要，因为在错误的地方高估可能会人为地使最佳路径看起来比另一条路径更糟糕，并阻止它被探索。因此，可能提供高估的启发式方法失去了对最优性的任何保证。低估并不带来同样的成本。如果您低估了朝某个方向前进的成本，最终边权重加起来将大于朝不同方向前进的成本，因此您也会探索该方向。唯一的问题是效率损失。

如果所有优势都有正成本，则负启发值只能是过低估计。从理论上讲，低估只会比更精确的估计更糟糕，因为它提供的有关路径潜在成本的信息严格较少，并且可能导致更多节点被扩展。尽管如此，它不会被拒绝受理。

然而，这里有一个例子，证明负启发值理论上有可能打破 A* 的最优性保证：

在此图中，通过节点 A 和 B 显然更好。这将产生 3 的成本，而不是通过节点 C 和 D 的成本 6。但是，C 和 D 的负启发值D 将导致 A* 在探索节点 A 和 B 之前通过它们到达终点。本质上，启发式函数一直认为这条路径会变得更好，直到为时已晚。在 A* 的大多数实现中，这将返回错误的答案，尽管您可以通过继续探索其他节点直到 f(n) 的最大值大于您找到的路径的成本来纠正此问题。请注意，这种启发式并没有什么不可接受或不一致的地方。事实上，我真的很惊讶非负性并没有更频繁地被提及作为 A* 启发式的规则。

当然，这表明您不能自由地使用返回负值的启发式方法而不担心后果。对于给定问题的给定启发式方法尽管是否定的，但完全有可能会产生很好的结果。对于您的特定问题，不太可能发生这样的事情（我发现它非常有趣，它对您的问题非常有效，并且仍然想更多地思考为什么会这样）。