A*功能

Question

我只是想澄清一下，在两条路径具有相等的值的情况下，路径查找的A*应该如何操作，无论是在计算过程中，还是在计算结束时，如果有两条相等的短路径。

例如，我在我的开始节点，有两个可能的节点我可以展开，但它们都有相同的f(x)。它们都被扩展了吗?按什么顺序扩展？

如果在搜索结束时有两条相等的最短路径，会发生什么情况？

Answer 1

在这两种情况下，您只需选择一个任意的。请注意，A*会找到最短路径之一，而不是所有最短路径，并且不需要像您所描述的那样解决歧义的特定方法。

Answer 2

如果您构建自己的A*实现，您将确切地决定如何处理此类情况。通常，当算法确定所有剩余路径至少与最短路径一样昂贵时，当前相等的最短路径中的任何一个都将被返回最短路径。

在我的游戏程序中(在十六进制网格上)，我使用了两个独立的A*实现。一种用于短距离(并且没有道路移动)，它使用向量积作为相等路径之间的平局断路器，它选择视觉上更直接的路径。用于更长距离的一种允许道路移动，并忽略了上面的改进，但使用了更复杂的启发式方法，这种启发式方法在长距离内更有效。

在Game Development StackExchange上有许多问题涉及A*算法的各种改进。

Answer 3

一个好的启发式算法将在许多条件下进行评估(添加风险、成本、效用管理、操作合理性等概率条件)，从而最小化最短路径的数量。

但是，如果条纹(即可扩展节点数组)上仍有多条路径，则简单的A*将任意拾取。