求算法找到N个骑士全局最短路径
我遇到了一个奇怪的问题。
我有一个无界棋盘，N 个骑士起始位置和 N 个目标位置。
任务是找到所有骑士到达所有目标位置的最少移动次数。
我知道单个骑士的最短路径问题可以使用广度优先搜索来解决，但是对于多个骑士如何解决呢？
对不起我的英语，我很少用它。
I've stampled upon a curious problem.
I've got an unbounded chessboard, N knights starting locations and N target locations.
The task is to find minimal number of moves for all knights to reach all target locations.
I know that shortest path problem for a single knight can be solved using breadth-first search, but how can it be solved for multiple knights?
Sorry for my english, I use it seldom.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可以按照 Ricky 的建议使用广度优先搜索来计算成本矩阵。所以现在，cost[i][j]表示选择骑士i前往结束位置j的成本。然后你可以使用匈牙利算法来找到最终答案，其计算时间为 O(N ^3) 复杂性。
You can compute the cost matrix as suggested by Ricky using breadth first search. so now, cost[i][j] denotes the cost of choosing knight i to goto end location j. Then you can use the Hungarian algorithm to find the final answer, which can be computed in O(N^3) complexity.
我想你知道如何为一名骑士做到这一点。
您可以将您的问题重新表述为线性程序：
我将使用以下符号：
我们有 N 个骑士和 N 个位置。
xij = 1如果您选择骑士 i 前往位置 j，否则选择 0cij是将骑士 i 移动到位置 j 的最小长度那么您将得到以下结果线性规划：
如果 X 是 (xij) 的矩阵，则有 n！可能的矩阵。这个问题可能是NP-Hard（该系统没有简单的解决方案，解决该系统与测试所有可能的解决方案非常相似）。
编辑：
这个问题称为分配问题并且存在多种算法在多项式时间内解决它。 （查看@purav答案的例子）
正如@Purav提到的，即使这种问题可能是NP困难的，在这种情况下它可以在O(n^3)内解决
关于@j_random_hacker提出的问题：
备注：
1.多个最佳路径：
由于棋盘的边没有限制（无限棋盘），因此实现最短路径的移动顺序并不相关，因此总是有很多不同的最短路径路径（我不会在这里进行组合）。
有 2 个骑士的示例
假设您有 2 K 和 2 个端点（“x”），则绘制了最佳路径。
您将右边的 K 移动到第一个点（移动 1 次），第二个点无法使用最佳路径。
但我可以轻松创建一条新的最佳路径，而不是向右移动 2 1 向上，然后向右移动 2 向上 1。
1 可以将 2 向上 1 向右移动 1 向上 2 向右（正好相反）
路径的任意组合都有效：
2.骑士移动的顺序：
第二件事是我可以选择移动的顺序。
示例：
在前面的示例中，如果我选择从左骑士开始并到达上端点，则不再有端点约束。
通过这两个评论，可以证明计算出的下界在任何情况下都不是最佳的。
I assume you know how to do it for one Knigt .
You can reformulate your problem as a linear program:
I will use the following notations :
We have N knights and N en locations.
xij = 1if you chose knight i to go to location j and 0 otherwisecijis the min length of moving knight i to location jThen you have the following linear program :
if X is the matrix of (xij) you have n! possible matrix. This problem can be NP-Hard (there is no easy solution to this system, solving the system is pretty similar than testing all possible solutions).
EDIT:
This problem is called the assignment problem and there exist multiple algorithms to solve it in polynomial time . (check out @purav answer for an example)
As mentionned by @Purav even though this kind of problems can be NP-hard, in this case it can be solve in O(n^3)
About the problem @j_random_hacker raised :
Remarks :
1. multiple optimal paths :
As there is no constraint on the side of the chessboard (ilimited chessboard), the order in which you do your move for achiveing the shortest path is not relevant, so there is always a lot a different shortest path (I won't do the combinatorics here).
Example with 2 knights
Let say you have 2 K and 2 endpoints ('x'), the optimal path are drawned.
you move the right K to the first point (1 move) the second cannot use the optimal path.
But I can easily create a new optimal path, instead of moving 2 right 1 up then 2 up 1 right.
1 can move 2 up 1 right the 1 up 2 right (just inverse)
and any combination of path works :
2. order in which knights are moved :
The second thing is that I can chose the order of my move.
example:
with the previous example if I chose to start with the left knight and go to the upper endpoint, dont have anymore endpoint constraint.
With these 2 remarks it might be possible to prove that there is no situation in which the lower bound calculated is not optimal .
BFS 在这里仍然可以工作。您需要稍微调整一下状态，但它仍然有效：
让
S为可能状态的集合：S={((x1,y1),(x2,y2),...,(xn,yn))|骑士 i 在 (xi,yi)}对于每个 s在S中，定义：
Successors(s)={所有可能的状态，在棋盘上移动 1 个骑士}你的目标状态当然是你的目标点的所有排列[你实际上不需要开发这些排列，只需检查是否达到了所有方块都被“填充”的状态，这很容易检查]
start=(start_1,start_2,...,start_n)其中 start_i 是奈特岛从
start[每个骑士的初始位置] 开始运行 BFS，如果存在的话，一定能找到解决方案 [因为 BFS 是 完整]。它还保证是最短的解决方案。(*) 请注意，单骑士的情况是此解决方案的私有实例，其中 n=1。
虽然 BFS 可以工作，但是会花费很多时间！这里的分支因子是4n，所以算法需要开发
O(( 4n)^d)顶点，其中 n 是骑士的数量，d 是解决方案所需的步骤数。可能的优化：
O((4n)^d)]，您可能会想要使用迭代深化DFS，其行为类似于BFS，
但消耗的内存要少得多 [
O(nd)]，但需要更多的运行时间。允许的启发式函数。也保证能找到一个
解决方案（如果存在），并且还确保找到的解决方案是
最佳的，并且可能[通过良好的启发]需要开发
比 BFS 更少的顶点。
BFS can still work here. You need to adjust your states a bit, but it will still work:
let
Sbe the set of possible states:S={((x1,y1),(x2,y2),...,(xn,yn))|knight i is in (xi,yi)}For each s in S, define:
Successors(s)={all possible states, moving 1 knight on the board}Your target states are of course all permutations of your target points [you don't actually need to develop these permutations, just check if you reached a state where all the squares are "filled", which is simple to check]
start=(start_1,start_2,...,start_n)where start_i is the start location of knight i.A run of BFS, from
start[the initial position of each knight], is guaranteed to find a solution if one exists [because BFS is complete]. It is also guaranteed to be the shortest possible solution.(*) Note that the case for single knight is a private instance of this solution, with n=1.
Though BFS will work, it will take a lot of time! the branch factor in here is 4n, so the algorithm will need to develop
O((4n)^d)vertices, where n is the number of knights and d is the number of steps needed for a solution.Possible optimizations:
O((4n)^d)] you mightwant to use Iterative Deepening DFS, which behaves like a BFS,
but consumes much less memory [
O(nd)], but takes more time to run.admissible heuristic function. It is also guarenteed to find a
solution if one exists, and also ensures the solution found is
optimal, and will probably [with good heuristic] need to develop
less vertices then BFS.
所以，我找到了解决方案。
BFS 在无限的棋盘上效果不佳。使用任何最短路径算法都是没有意义的——骑士从位置 a 到位置 b 的移动次数可以在 O(1) 时间内计算出来——M. Deza，距离词典，第 17 页。 251
http://www.scribd.com/doc/53001767/Dictionary-of-Distances-M-Deza-E-Deza-Elsevier-2006-WW
分配问题可以使用以下方法解决mincost-maxflow 算法（例如 Edmonds-Karp）：
http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
So, I've found the solution.
BFS won't work well on an unlimited chessboard. There is no point in using any shortest path algorithm -- number of knight's moves from location a to location b can be computed in O(1) time -- M. Deza, Dictionary of Distances, p. 251
http://www.scribd.com/doc/53001767/Dictionary-of-Distances-M-Deza-E-Deza-Elsevier-2006-WW
The assignment problem can be solved using mincost-maxflow algorithm (eg. Edmonds-Karp):
http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm