A *功能

Question

我刚刚澄清了一下，A *路径查找应该如何在两个具有相同值的路径的情况下进行操作，无论是在计算期间，还是在末尾有两条相等的短路径。

例如我在我的开始节点，有两个可能的节点，我可以扩展到，但他们都有相同的f（x）。他们都扩大了，并按顺序？

如果在搜索结尾有两条相等的最短路径会发生什么？

Answer 1

在这两种情况下，你只要选择一个任意一个。请注意，A *找到最短路径中的一条，而不是全部，并且没有解决模糊的具体方式，就像您描述的那样是必要的。

Answer 2

如果您构建您自己的A *实现，您可以准确决定如何处理这些案例。典型地，等于最短路径的取其电流此刻当该算法确定所有剩余路径至少为昂贵将返回为的最短路径。

在我的游戏程序中（使用十六进制网格），我使用了两个独立的A *实现。一个用于短距离（并且没有道路移动）使用矢量产品作为平等路径之间的平局，其选择视觉上更直接的。距离较长的路段可以实现道路移动并忽略上述改进，但使用更复杂的启发式方法，该方法在远距离范围内效率更高。

关于Game Development StackExchange有很多问题可以解决A *算法的各种改进。

Answer 3

一个很好的启发式将评估许多条件（添加概率条件，如风险，成本，公用事业管理，操作的合理性等），从而最小化最短路径的数量。

但是，如果条纹（即可扩展节点阵列）上仍有多条路径，则简单的A *将随意拾取。