没有交叉路径
我试图让多个代理同时移动到2d地图上的指定点，并且具有一个代理可以移动的最大距离的上限。 如果可能，所有代理商应该移动最大距离，否则应该移动最小距 如果可能的话，不同代理商的路径不应该交叉，但是如果不可行，他们仍然可以交叉。
我的想法是某种调整后的A *算法。 这是一个好方法还是有更好的算法来解决这类问题？ （说实话，我目前在我的雷达上已经有了A *和dijkstra作为解决这个问题的可能性，所以如果有什么更好的话，推向正确的方向将会很棒）
感谢您的帮助
PS：我还没有任何一种底层图，所以我仍然对任何想法持开放态度，但当然可以创建一个适用于dijkstra / A *的图。
你的问题接近于顶点/边缘不相交路径问题，这通常是NP-Complete，你的受限版本似乎是NP-Complete，因为网格图中最短的不相交路径是NP-Hard，它与你的受限版本相关。 但是，对于网格中的不相交路径有很多算法（即使你有不同的图层），所以我可以建议的最佳选择是使用其中一种精确算法来找到顶点不相交路径，然后增加路径的大小（如果需要），通过遍历一些相邻的顶点。
此外，对于网格，您不需要Dijkstra来查找两个节点之间的路径（即使是最短路径或具有特定长度的路径），也可以简单地通过运行BFS来完成，并且是O（n）（从顶点v开始BFS，并设置其相邻的数量为1，然后为每个相邻的1的新值设置为2，...参见本答案和编号算法部分）。
如果你在动态的情况下寻找一些启发式的话，这个问题也可能有帮助。
链接地址: http://www.djcxy.com/p/63501.html上一篇: no crossing paths