改进一个星型算法在迷宫中搜索多个目标

如果我已经完成了在迷宫中实现A *算法以寻找到单个目标的最短路径（就像pacman游戏一样），我应该如何改进我当前的启发式（曼哈顿距离目标+距离开始的旅行成本），这样我的算法将支持迷宫中的多个目标。基本上，我想找到走过迷宫中所有目标的最短路径。为了确保路径是最优的，假设我们忽略问题的一致性，启发函数需要被允许。改进一个星型算法在迷宫中搜索多个目标

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

欢迎任何想法。谢谢！

来源

2016-09-21 Deidara

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

您不能将约束添加到A *的允许路径（例如，必须访问所有这些节点），并且期望它仍然会生成最短路径。

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

来源

2016-09-21 02:18:49

你能更具体吗？我正在考虑使用星形来计算目标之间的距离，然后应用最小生成树。但是我在这里有一个迷宫而不是一个图表，这意味着在目标之间应用一颗星可能有不止一个可能的路径......在搞清楚访问目标的顺序之前，要做太多的前期工作...... – Deidara

如果你有目标'a'，'b'，'c'，'d'，你可以用A *来找到'（a，b）'，'（a，c）'，'（a ，d），'（b，c）'，'（b，d）'，'（c，d）'。这是一个图表，你可以解决旅行商问题。如果你只有几个，只是尝试每个排列都会足够快。 –

您可以使用距离最近的目标的距离;这样，当最后一个目标被访问时它只会变成0。

来源

2016-09-21 02:15:09

改进一个星型算法在迷宫中搜索多个目标

回答

相关问题