如何为城市与道路相连问题确定启发式成本。该图具有非负加权的单向边，并且没有边将任何顶点连接到自身。在这个图中，任意两个顶点之间只有一条边。我的目标是使单一来源和单一目的地之间的距离最短。
最佳答案
如果你的边位于欧几里德平面内，你的顶点对应道路，顶点成本是道路的长度，那么Euclidian distance或 L2 范数是启发式成本的不错选择。
原因如下。但首先，一些快速术语:
设f(x) 为路径成本，即计算出的从起始节点到节点x 的最短距离。
令h(x) 为启发式成本，即从节点x 到目标的距离估计值。
因为 A*是一种定向最佳搜索算法。在每一步，它都会移动到最小化 h(x) + f(x) 的节点(并且计算 h(x) 需要我们在脑海中有一个目标节点) .
要使此方法保证找到开始节点和结束节点之间正确的最短补丁距离，h(x) 必须是 admissible heuristic .这实质上意味着它不能高估到目标节点的距离。
因此，如果您的节点是在欧几里得平面上组织的，并且您的成本对应于节点之间的 L2 范数距离，那么 Euclidian distance或者当前节点 x 和目标节点之间的 L2 范数保证是 admissible heuristic (这是两个节点之间的最短路径，因此图中一系列顶点的任何实际路径都必须更长)。
作为奖励，值得注意的是 Dijkstra's Algorithm只是 A* 的特例h(x) = 0。对于任何节点，我们假设到目标的路径是 0，这意味着我们只需采取尽可能小的步骤。这肯定是 admissible heuristic因为任意两个节点之间的距离不能小于 0(如果我们假设边成本为非负)。
关于java - 如何确定与道路相连的城市的 A* 搜索算法中的 H 成本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10055685/