要求算法找到N Knights全局最短路径

Question

我已经对一个奇怪的问题进行了测试.

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

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

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

抱歉我的英语,我很少使用它.

Answer 1

我想你知道如何为一名 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 //从 i 到 j 正好有一个 knigt

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 等等...只要我保持相同数量的上下移动，并且它们是有效的。

2. 骑士移动的顺序：

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

例子：

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

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


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

通过这两个评论，可以证明计算出的下限在任何情况下都不是最佳的。