如果我已经在迷宫中完成了A *算法的实现，以找到单个目标的最短路径（就像pacman游戏一样），我应该如何改进我目前的启发式（曼哈顿到目标旅行费用的距离从头开始）这样我的算法就可以在迷宫中支持多个目标 . 基本上，我想找到通过迷宫中所有目标的最短路径 . 为了确保路径是最优的，假设我们忽略问题的一致性，则需要允许启发式函数 .
我知道这就像旅行商问题，但是现在我只处理相对少量的数据，所以我想继续使用A start算法 .
欢迎任何想法 . 谢谢！
A *找到从一个点到另一个点的最短路径 .
您不能将约束添加到允许的路径（例如，必须沿途访问所有这些节点）到A *并期望它仍然产生最短路径 .
您可以使用A *查找目标之间的距离（和路径），然后解决目标之间的旅行商问题（使用这些距离），以确定访问目标的顺序，从而获得最短的整体路径 .
您可以使用到最近未访问过的目标的距离;这样，当最后一个目标被访问时，它只会变为0 .
2 回答
A *找到从一个点到另一个点的最短路径 .
您不能将约束添加到允许的路径（例如，必须沿途访问所有这些节点）到A *并期望它仍然产生最短路径 .
您可以使用A *查找目标之间的距离（和路径），然后解决目标之间的旅行商问题（使用这些距离），以确定访问目标的顺序，从而获得最短的整体路径 .
您可以使用到最近未访问过的目标的距离;这样，当最后一个目标被访问时，它只会变为0 .