如果你有一组可接受的启发式：h1,h2,h2,...,hn

如何使h = max(h1,h2,h2,...,hn)成为一个主导所有这些启发式的可接受启发式？

不是h(n)值越低越好吗？

对于A*，f = g + n，列表中f值最低的元素将被移除。所以不应该使用min来获得主导启发式吗？

回答：

可接受的启发式永远不会高估达到目标状态的成本。也就是说，它的估计值会低于实际成本或正好等于实际成本，但绝不会高于实际成本。这是贪婪方法如A*搜索找到全局最优解所必需的条件。

例如，假设你找到一个成本为10的解决方案。最佳解决方案的成本为8。你没有使用可接受的启发式，而对于那个实际成本为8的解决方案，启发式的估计值为12（它高估了）。由于你已经有一个成本为10的解决方案，A*永远不会评估那个被估计为更昂贵的最佳解决方案。

理想情况下，你的启发式应该尽可能准确，即可接受的启发式不应过多低估真实成本。如果它确实低估了，A*最终仍会找到最佳解决方案，但可能需要更长的时间，因为它会尝试许多根据你的启发式看起来不错，但实际上效果不佳的解决方案。

这就是你问题的答案所在。你的启发式h1, ..., hn都是可接受的，因此它们估计的成本等于或低于真实成本。这组估计的最大值因此按定义是最接近实际成本的估计（记住你永远不会高估）。在理想情况下，它将是确切的成本。

如果你取最小值，你将得到与实际成本相差最远的估计——如上所述，A*仍然会找到最佳解决方案，但效率会大大降低。