algorithm - 最佳优先搜索中使用了哪种启发式函数？

Question

因此，最佳优先搜索(有信息)和统一成本搜索(无信息)之间的主要区别在于，在 BFS 中，我们使用启发式函数来确定下一个节点。在 UCS 中，我们总是采用从我的初始状态计算出的最低成本。

最佳优先搜索中使用的启发式函数是什么？是mentioned启发式函数在所有地方都是 h(n) = f(n)，但是 f(n) 到底是什么？如果我的“ map ”有许多节点，只有从一个节点到另一个节点的路径成本？

Answer 1

启发式函数并不是独一无二的。您做出的决定在很大程度上取决于所解决问题的特定属性。即使那样，您也可以在不同的方法(功能)之间进行选择。通常，您会尝试选择的函数如何影响示例案例中找到的解决方案的质量，并测试备选方案。

例如，如果图是欧几里得图，其中节点表示 n 维空间中的坐标，边的成本是它的长度(连接节点之间的距离)，那么一种可能的启发式可能是源之间的距离和目标节点。

您对图的假设越少——您对其属性的了解越少——就越难找到合适的启发式函数。