a-star - 产生负值的启发式函数是否 Not Acceptable ？

Question

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

但是，我担心这是 Not Acceptable ，但无法在网上找到足够的信息来验证这一点。 I did find this one paper from the University of Texas这似乎在后来的证明之一中提到“......因为启发式函数是非负的”。任何人都可以证实这一点吗？我认为这是因为返回负值作为您的启发式函数会使您的 g-cost 变为负值(因此会干扰 A* 的“默认”dijkstra-esque 行为)。

Answer 1

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

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

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

但是，这里有一个示例说明 理论上，负启发式值可能会破坏 A* 的保证最优性:


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

当然，这表明您不能随意使用返回负值的启发式方法而不用担心后果。尽管是负面的，但对于给定问题的给定启发式算法恰好能很好地解决问题，这是完全有可能的。对于您的特定问题，不太可能发生这样的事情(我发现它对您的问题非常有效，并且仍然想更多地考虑为什么会这样，这真的很有趣)。