algorithm - 在棋盘上移动 N 个国王

Question

假设我们有一个棋盘（任意大小）和 N 个国王最初放置在 N 个方格上。假设现在我们选择 N 个新方格来将国王移动到一系列合法移动（没有冲突）。目标是最小化所有国王移动的总距离。我真的想不出一种算法/适应可以处理移动所有部分，同时注意防止“碰撞”国王。该算法应该比递归选择目标方块和选择最小传输更快。我希望有人对这个问题有宝贵的建议。

谢谢

标签： algorithmchess

Answer 1

首先，您需要找到所有国王和所有目标方格之间的最小总距离完全二分匹配。您可以通过将每个距离替换为权重（something_big-distance）将其重铸为最大权重二分匹配，然后找到最大权重二分匹配，或者您可以只保持匹配完成的不变量并直接找到最小二分匹配.

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

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

1. 如果挡路之王还没有在它的目标方格，那么只需移动那个方格即可。
2. 如果路王已经在其目标方格上，则在您要移动的王和路王之间交换目标。然后移动王道。这不会改变您必须进行的移动总数。

当然，路中之王也可能有一位王在路上，所以再次应用这些规则，直到找到一个可以移动的规则。

现在您可能想知道如果每个必须移动的国王都有自己的国王该怎么办。只有当所有的国王都想在这个循环中移动时，才会发生这种情况……但这不可能发生。

围绕一个循环移动所有的国王需要移动，但它不会改变棋盘的状态。因此，这种情况意味着您在原始映射中找到的路径集不是最小的。由于它们是最小的，所以这样的条件是不可能的。