6

我遇到了一个奇怪的问题。

我有一个无界的棋盘，N 个骑士起始位置和 N 个目标位置。

任务是找到所有骑士到达所有目标位置的最少移动次数。

我知道单个骑士的最短路径问题可以使用广度优先搜索来解决，但是如何解决多个骑士的问题呢？

对不起我的英语，我很少用它。

4

4 回答 4

2

您可以按照 Ricky 的建议使用广度优先搜索来计算成本矩阵。所以现在，cost[i][j] 表示选择骑士 i 到终点位置 j 的成本。然后您可以使用匈牙利算法找到最终答案，该答案可以以 O(N^3) 复杂度计算。

于 2011-10-19T18:33:19.707 回答
2

我假设您知道如何为一个 Knigt 做到这一点。

您可以将问题重新表述为线性程序：

我将使用以下符号：

我们有 N 个骑士和 N 个地点。

xij = 1如果你选择骑士 i 去位置 j 和 0 否则

cij是将骑士 i 移动到位置 j 的最小长度

然后你有以下线性程序：

变量：

xij 为 [0,N] 中的 ij

成本函数：

C= SUM(cij.xij for (i,j) in [0,N]x[0,N])

约束：

SUM(xij for j in [1,N]) = 1 //正好有一个 knigt 从 i 到 j

SUM(xij for i in [1,N] ) = 1

（矩阵 (xij) 是一个随机矩阵）

如果 X 是 (xij) 的矩阵，则您有 n！可能的矩阵。这个问题可能是NP-Hard （这个系统没有简单的解决方案，解决这个系统与测试所有可能的解决方案非常相似）。

编辑：

这个问题被称为分配问题，有多种算法可以在多项式时间内解决它。（查看@purav 答案以获取示例）

正如@Purav 所提到的，即使这类问题可能是 NP 难的，但在这种情况下，它可以在 O(n^3) 中解决

关于@j_random_hacker 提出的问题：

问题

如果一个骑士在一个端点，下一个骑士应该不能通过这个端点。因此，可能需要在每个骑士移动后更新 Cij。

评论 ：

1.多条最优路径：

由于棋盘的一侧没有限制（无限棋盘），因此您为获得最短路径而进行的移动顺序无关紧要，因此总是有很多不同的最短路径（我不会做这里的组合）。

以 2 个骑士为例

假设您有 2 K 和 2 个端点（'x'），绘制了最佳路径。

    -x
   |
   | 
   x
   |
K-- --K

您将右 K 移动到第一个点（1 次移动），第二个不能使用最佳路径。

    -x
   |
   |  
   K
   |
K-- --:

但是我可以轻松地创建一个新的最佳路径，而不是移动 2 右 1 上然后 2 上 1 右。1 可以移动 2 上 1 右 1 上 2 右（正好相反）

   --K
  |
 -    
|   K
|   |
:    --:

以及任何路径组合：

1 U 2 R 然后 2 U 1 R 等等......只要我保持相同的向上 LEFT DOWN 和 RIGHT 移动次数并且它们是有效的。

2. 移动骑士的顺序：

第二件事是我可以选择我的移动顺序。

例子：

对于前面的示例，如果我选择从左骑士开始并转到上端点，则不再有端点约束。

    -K
   |
   | 
   x
   |
:-- --K


    -K
   |
   | 
   K
   |
:-- --:

有了这两条评论，就有可能证明不存在计算的下限不是最优的情况。

于 2011-10-19T09:29:51.157 回答
1

BFS 在这里仍然可以工作。你需要稍微调整一下你的状态，但它仍然可以工作：

让S是一组可能的状态：
S={((x1,y1),(x2,y2),...,(xn,yn))|knight i is in (xi,yi)}

对于 S 中的每个 s，定义：
Successors(s)={all possible states, moving 1 knight on the board}

你的目标状态当然是你的目标点的所有排列[你实际上不需要开发这些排列，只需检查你是否达到了所有方块都被“填充”的状态，这很容易检查]

start=(start_1,start_2,...,start_n)其中 start_i 是骑士 i 的起始位置。

从start[每个骑士的初始位置] 开始的 BFS 运行保证如果存在解决方案 [因为 BFS 是完整的] 找到解决方案。它也保证是最短的解决方案。

(*) 请注意，单骑士的情况是此解决方案的私有实例，n=1。

虽然 BFS 可以工作，但需要很多时间！这里的分支因子是 4n，因此算法需要开发O((4n)^d)顶点，其中 n 是骑士的数量，d 是解决方案所需的步数。

可能的优化：

  1. 空间：请注意，由于 BFS 使用大量内存 [ O((4n)^d)]，您可能需要使用迭代深化 DFS，它的行为类似于 BFS，但消耗的内存要少得多 [ O(nd)]，但需要更多时间来运行。
  2. 时间：为了加速解决方案搜索，您可以使用具有 可接受启发式函数的A Star。如果存在解决方案，也保证找到解决方案，并确保找到的解决方案是最优的，并且可能 [具有良好的启发式] 需要开发比 BFS 更少的顶点。
于 2011-10-19T15:25:17.000 回答
0

所以，我找到了解决方案。

BFS 在无限棋盘上无法正常工作。使用任何最短路径算法是没有意义的——骑士从位置 a 移动到位置 b 的次数可以在 O(1) 时间内计算出来——M. Deza，距离字典，p。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

于 2012-02-09T11:55:07.550 回答