我正在尝试使多个特工同时移动到2d地图上的指定点，并为一个特工可以移动的最大距离设置上限。如果可能的话，所有座席都应移动最大距离，否则应移动。如果可能，不同代理的路径不应交叉，但如果不能，则它们仍可以交叉。
我的想法是某种调整后的A *算法。这将是一个好方法还是针对此类问题的更好算法？（说实话，我目前可以解决这个问题，因此我现在有A *和dijkstra，所以如果有更好的选择，朝正确的方向推进将是巨大的）
感谢您的帮助
PS：我还没有任何底层图，所以我仍然对任何想法持开放态度，但是当然可以创建适用于dijkstra / A *的图
您的问题很接近顶点/边缘不相交路径问题，通常是NP-Complete，您的受限版本也似乎是NP-Complete，因为网格图中最短的不相交路径是NP-Hard，这与您的受限版本有关。但是网格中有很多不相交路径的算法（即使您有不同的图层），所以我建议的最佳选择是使用一种确切的算法来查找顶点不相交的路径，然后增加路径的大小（ （如果需要），则遍历一些相邻的顶点。
同样对于网格，您不需要Dijkstra来查找两个节点之间的路径（即使是最短路径或具有特定长度的路径），也可以通过运行BFS并将其设置为O（n）来完成（从顶点v开始BFS，然后设置与其1相邻的数字，然后为1的每个相邻数字将新值设置为2，...参见此答案和编号算法部分）。
如果您在动态情况下寻找一些启发式方法，也许这个问题也会有所帮助。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句