改进A星算法在迷宫中搜索多个目标
Improve A star algorithm to search multiple goals in a maze
如果我已经完成了在迷宫中实现 A* 算法以找到到达单个目标的最短路径（就像吃豆子游戏一样），我应该如何改进我当前的启发式算法（到目标的曼哈顿距离 + 旅行成本到目前为止），以便我的算法将支持迷宫中的多个目标。基本上，我想找到穿越迷宫中所有目标的最短路径。为了确保路径是最优的，假设我们忽略问题的一致性，启发式函数需要是可接受的。
我知道这就像旅行商问题，但现在我只处理相对少量的数据，所以我想继续使用 A 开始算法。
欢迎任何想法。谢谢！
您可以使用距离最近的尚未访问的目标的距离；这样它只会在访问最后一个目标时变为 0。
A* 找到从一点到另一点的最短路径。
您不能向 A* 添加对允许路径的约束（例如，必须沿途访问所有这些节点）并期望它仍然产生最短路径。
您可以使用 A* 找到目标之间的距离（和路径），然后解决目标之间的旅行推销员问题（使用这些距离）来找出使您总体上最短的访问目标的顺序路径。
选择 Dijkstra 算法而不是 A*。
因为A*算法不能应用于那些有很多目标节点的图。如果你有很多目标节点并且你不知道哪一个最接近主节点，A* 就不是最优的。这是因为它需要 运行 几次（每个目标节点一次）才能到达所有这些节点。
参考：
How does Dijkstra's Algorithm and A-Star compare? - Intellipaat Community
如果我已经完成了在迷宫中实现 A* 算法以找到到达单个目标的最短路径（就像吃豆子游戏一样），我应该如何改进我当前的启发式算法（到目标的曼哈顿距离 + 旅行成本到目前为止），以便我的算法将支持迷宫中的多个目标。基本上，我想找到穿越迷宫中所有目标的最短路径。为了确保路径是最优的，假设我们忽略问题的一致性，启发式函数需要是可接受的。
我知道这就像旅行商问题，但现在我只处理相对少量的数据，所以我想继续使用 A 开始算法。
欢迎任何想法。谢谢！
您可以使用距离最近的尚未访问的目标的距离；这样它只会在访问最后一个目标时变为 0。
A* 找到从一点到另一点的最短路径。
您不能向 A* 添加对允许路径的约束（例如，必须沿途访问所有这些节点）并期望它仍然产生最短路径。
您可以使用 A* 找到目标之间的距离（和路径），然后解决目标之间的旅行推销员问题（使用这些距离）来找出使您总体上最短的访问目标的顺序路径。
选择 Dijkstra 算法而不是 A*。 因为A*算法不能应用于那些有很多目标节点的图。如果你有很多目标节点并且你不知道哪一个最接近主节点，A* 就不是最优的。这是因为它需要 运行 几次（每个目标节点一次）才能到达所有这些节点。
参考： How does Dijkstra's Algorithm and A-Star compare? - Intellipaat Community