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

Question

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

Answer 1

如果您试图优化行驶距离，欧几里德距离是一个很好的基线启发

Answer 2

如果边位于欧几里德平面上，顶点对应于道路，并且顶点代价是道路的长度，那么Euclidian distance或L2范数是启发式代价的良好选择

---

原因如下。但首先，一些快速术语：

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

设h(x)为启发式成本，即从节点x到目标的距离估计值

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

---

为了保证这种方法能够找到起始节点和结束节点之间正确的最短补丁距离，h(x)必须是admissible heuristic。这本质上意味着它不能高估到目标节点的距离

因此，如果节点是在欧几里德平面上组织的，并且成本与节点之间的L2范数距离相对应，然后，当前节点x和目标节点之间的Euclidian distance或L2范数保证为admissible heuristic（这是两个节点之间可能的最短路径，因此沿图中一系列顶点的任何实际路径都必须更长）

---

另外，值得注意的是Dijkstra's Algorithm只是A*与h(x) = 0的一个特例。对于任何节点，我们假设目标的路径是0，这意味着我们只需采取尽可能小的步骤。这当然是一个admissible heuristic，因为任何两个节点之间的距离都不能小于0（如果我们假设非负边缘成本）

Answer 3

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