在棋盘上移动N个国王

Question

假设我们有一个棋盘（任意大小），并且有N个国王初始放置在N个方格上。现在假设我们选择N个新的方格，通过一系列合法移动（没有碰撞）将国王移动到这些方格上。目标是尽可能减少所有国王移动的总距离。我无法想出一种算法/修改方案，可以处理移动所有棋子的同时避免“碰撞”问题。该算法应该比递归选择目标方格并选择最小运输时间更快。希望有人能够提供宝贵的建议来解决这个问题。

谢谢

- Ian_L

---

只是为了澄清，这里的碰撞指的是在同一方格上的两个棋子，而不是在国际象棋中的邻近或能力捕获？ - kcsquared

所有国王在每一步都要一起移动吗？每一步所有国王都需要移动吗？还是他们可以在途中静止不动？目标方格是分配给单个国王，还是由算法决定哪个国王应该去哪个目标？当棋盘接近充满时，问题可能会变得非常棘手。 - JohanC

玩家每次只能移动一个国王，不能进行吃子操作，因此不允许与其他棋子发生碰撞。 - Ian_L

Answer 1

首先，你需要找到所有国王和目标方块之间的最小总距离完全二分匹配。你可以将其重新表述为最大权重二分匹配，方法是用权重（something_big-distance）替换每个距离，然后找到最大权重二分匹配，或者你可以保持匹配完整性并直接找到最小二分匹配。

我认为最简单的方法是使用Edmonds-Karp算法。这通常用于查找最大流，但最大权重二分匹配本质上就是该问题的一个实例，只需添加单个源和汇点顶点即可。

一旦你找到了国王和他们目标方块之间的匹配，你就可以移动国王。无论你以什么顺序移动它们，只要你沿着每个国王的最短路径移动，并且不将国王移动到已占用的方块上，就不会有太大的区别。如果一个国王想要移动到一个已占用的方块上，有两个选择：

1. 如果挡路的国王还没有到达目标格子，那么只需移动挡路的国王。
2. 如果挡路的国王已经在其目标格子上，则交换要移动的国王和挡路的国王的目标，并移动挡路的国王。 这不会改变您需要移动的总步数。

当然，挡路的国王也可能有一个国王挡住了它的路，因此再次应用这些规则，直到到达可以移动的国王。

现在您可能会想知道如果每个移动的国王都有一个挡路的国王怎么办。 如果所有国王都要在一个周期内移动，那么这种情况只会发生一次... 但这是不可能发生的。

将所有国王移动到一个循环中会耗费步数，但不会更改棋盘的状态。 因此，这种情况意味着您在原始映射中找到的路径集合不是最小的。 由于它们是最小的，所以这种情况是不可能的。

- Matt Timmermans

---

非常好。我之前在匹配方面遇到了一些麻烦，但是循环参数消除了任何不确定性。 - Ian_L

Answer 2

以下算法应该可以工作：

1. 找到离其最近的国王更远的目标方块。
2. 将最近的国王移动到该方格。（不会发生阻塞，因为国王必须更接近才能阻止另一个国王）
3. 重复此过程，直到所有国王都已移动到目标位置。

可能会出现一个在目标上的国王阻挡了第二步中未移动的国王，但我不确定是否会发生这种情况。

---

经过进一步思考，我发现我的上述算法更像是贪心方法启发式而非确定性解。我可以很容易地举出一个例子，证明它无法产生最优解。

例如，在[(1到5)×(1到5)]的4个棋子和3个目标的棋盘上：

• K = {(2,2), (3,4), (4,3), (5,5)}
• T = {(1,1), (1,2), (2,1), (3,3)}

我的算法将首先尝试将 K:{(2,2), (3,4), (4,3)} 移动到 T:(3,3)，这是错误的。 它应该先移动 K:(5,5) 到 T:(3,3)，然后再进行其他操作。

- RBarryYoung

---

那么我们必须根据最近的国王将方块分组，以找到每个国王最东边的方块？ - Ian_L

@Ian_L 抱歉，那是个打错字了。“Furtherest away”应该是“最远的”。 - RBarryYoung

需要将右侧国王向右移动，然后再将左侧国王向右移动。建议的算法未选择正确的顺序。 - n. m.