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

Question

如果一个节点的启发式值，比如说，达到目标的实际成本x 10 ^ 5怎么办？具有最低成本的节点仍然从优先级队列的顶部弹出。

例如：f(n) = g(n) + h(n)，where h(n) = h1(n) x 10^5, where h1(n) = h1′(n)

根据定义，这里的h高估了达到目标的实际成本。

我问的原因是因为无论是否有常数因素，我都无法真正看到算法性能的差异。那么，如果h是否可以接受，为什么重要呢？

Answer 1

Yes:

1. 一般来说：可接受性是A *最优性的充分条件，而不是必要条件。当然，你可能会发现一个不可接受的启发式存在，它也会返回一个最佳结果;只是A *在那时没有提供任何保证。
2. 特别是：“以一致的方式”是模糊的，但如果您考虑“缩放”以适合此描述，那么请注意，如果成本不是加法的，您的缩放启发式可能会失败。注意，A *不要求评估函数为f = g + h。虽然乍一看不直观，但是对于问题而言，完全可能且现实的还有其他评估功能，即添加路径成本甚至没有意义（例如，您的成本可能是概率）。

还要注意“一致性”has an entirely different meaning而不是你正在使用的那个，所以在使用该术语时要小心。按照通常的定义，不可能使一致的启发式方法不可接受。

Answer 2

如果一个节点的启发式值，比如说，达到目标的实际成本x 10 ^ 5怎么办？

假设使用完美的启发函数h'(n)，它总是等于从n到最近目标节点的路径的剩余成本，如果启发函数高估了常数因子，那么无论h是否可接受，都将找到相同的路径或不。

您可以将您的示例视为使用Dijkstra在图形G上的搜索，其中所有弧的成本乘以常数因子，从而生成新的图形G'。 G的每条最短路径都是G'的最短路径。

备注：如果启发式过高估计而不是所有节点的常数因子，答案将是相反的。在这种情况下，A *不保证找到最佳解决方案。

编辑：在阅读@Mehrdad关于推广评估函数以考虑非加性成本的答案之后，从纯粹主义的角度来看，我不会说当成本是非加成时我们正在应用A *。 A *解决了最短路径问题并假设成本是加性的，实际上，它的所有形式属性都基于该假设。

如果成本最小化标准被推广为包括解决方案路径的非加性成本度量，那么恕我直言，我们正在讨论一个不同的问题，因此需要一个不同的算法来解决它。在这种情况下，我认为这个问题在文献中被称为NSAP（非加性最短路径）。 Rina Dechter和Judea Perl在本文中可以找到一个例子：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.3090&rep=rep1&type=pdf（第507页），他们称算法解决泛化问题BF *，因为他们正在研究A *在两个限制，加法成本时的行为措施和附加评估功能被删除。