algorithm - 改进A星算法在迷宫中搜索多个目标

Question

如果我已经完成了在迷宫中实现 A* 算法以找到到单个目标的最短路径(就像吃 bean 游戏一样)，我应该如何改进我当前的启发式算法(曼哈顿到目标的距离 + 到目前为止的旅行成本从一开始)这样我的算法将支持迷宫中的多个目标。基本上，我想找到穿越迷宫中所有目标的最短路径。为了确保路径是最优的，假设我们忽略问题的一致性，启发式函数需要是可接受的。

我知道这就像旅行商问题，但现在我只处理相对少量的数据，所以我想继续使用 A 开始算法。

欢迎任何想法。谢谢!

Answer 1

A* 找到从一点到另一点的最短路径。

您不能向 A* 添加对允许路径的约束(例如，必须沿途访问所有这些节点)并期望它仍然产生最短路径。

您可以使用 A* 找到目标之间的距离(和路径)，然后解决目标之间的旅行推销员问题(使用这些距离)来计算访问目标的顺序，从而使您获得最短的总路径。