java - 如何确定与道路相连的城市的 A* 搜索算法中的 H 成本

Question

如何决定heuristic cost问题cities connected with roads。该图具有非负加权单向边，并且没有边将任何顶点连接到自身。在这个图中，任意两个顶点之间只有一条边。single source我的目标是获得和之间的最短距离single destination。

Answer 1

如果您的边位于欧几里得平面上，您的顶点对应于道路，并且顶点成本是道路的长度，那么欧几里得距离或 L2 范数对于启发式成本是一个不错的选择。

---

这就是为什么。但首先，一些快速的术语：

设f(x)为路径成本，即计算出的从起始节点到节点的最短距离x。

让h(x)是启发式成本，从节点到目标的距离的估计x。

因为A*是一个有向的最佳优先搜索算法。在每一步，它都会移动到最小化的节点 h(x) + f(x)（计算h(x)需要我们记住一个目标节点）。

---

为了保证这种方法在开始和结束节点之间找到正确的最短补丁距离，h(x)必须是一个可接受的启发式。这实质上意味着它不能高估到目标节点的距离。

因此，如果您的节点是在欧几里得平面上组织的，并且您的成本对应于节点之间的 L2 范数距离，那么当前节点和目标节点之间的欧几里德距离x或 L2 范数保证是一个可接受的启发式（它是两个节点之间可能的最短路径，因此沿着图中一系列顶点的任何实际路径必须更长）。

---

作为奖励，请注意Dijkstra 算法只是A*的一个特例，具有h(x) = 0. 对于任何节点，我们假设到达目标的路径是0，这意味着我们只是采取最小的可能步骤。这当然是一种可接受的启发式方法，因为任何两个节点之间的距离不能小于0（如果我们假设非负边成本）。

Answer 2

如果您尝试优化行驶距离，欧几里得距离是一个很好的基线启发式方法。

Answer 3

如果给定一个加权图，请使用边权重，就好像它是线段的长度一样。加权图中的最短路径是组合边权重最低的路径。