在棋盘上移动 N 个国王
Moving N Kings on chess board
假设我们有一个棋盘（任意大小）和最初放置在 N 个方格上的 N 个国王。让我们假设现在我们 select N 个新方格通过一系列合法的移动（无碰撞）将国王移动到。目标是最小化所有国王移动的总距离。我真的想不出一个 algorithm/adaptation 可以在处理移动所有棋子的同时注意防止“碰撞”国王。该算法应该比递归 selecting 目标方块和 selecting 最小传输更快。我希望有人对这个问题有宝贵的建议。
谢谢
以下算法应该有效：
- 找到距离最近的国王更远的目标方格。
- 将最近的国王移到那个方格。 （不会发生阻塞，因为一个国王必须更靠近另一个国王才能阻止另一个国王）
- 重复直到所有国王都被移动到一个目标。
它的目标上的国王可能会在#2 中阻挡未移动的国王，但我不确定这是否会发生。
经过进一步思考，我很清楚我上面的算法更像是一种贪心法启发式算法，而不是确定性解决方案。我可以很容易地想出一个无法产生最佳解决方案的例子。
考虑当 N=4 在 [(1 到 5)x(1 到 5)] 板上时：
- 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) 并且可能不是第一个。
首先，您需要找到所有国王和所有目标方块之间的最小总距离完全二分匹配。您可以通过将每个距离替换为权重 (something_big-distance) 将其重铸为 maximum weight bipartite matching，然后找到最大权重二分匹配，或者您可以只维护匹配完成的不变量并找到最小值直接二分匹配
我认为最简单的方法是使用 Edmonds-Karp Algorithm。这通常用于寻找最大流，但最大权重二分匹配本质上是该问题的一个实例，一旦您添加单个源和汇点顶点。
找到国王与其目标方格之间的匹配项后，您就可以移动国王了。只要您沿着最短路径移动每个国王，并且您不将国王移动到已经被占据的方格上，那么您制作它们的顺序并没有太大区别。如果一个国王想要移动到一个被占领的方格上，有两种选择：
- 如果拦路之王尚未到达其目标方格，则只需移动那个方格即可。
- 如果挡路王已经在它的目标方格上，那么在你想要移动的国王和挡路王之间交换目标。然后移动国王在路上。这不会改变您必须进行的移动总数。
当然，国王在路上也可能有一个国王它的方式，所以再次应用这些规则，直到你得到一个你可以移动的。
现在您可能想知道如果每个必须移动的国王都有一个国王顺其自然，该怎么办。这只有在存在一个所有国王都想绕着这个循环移动的循环时才会发生……但这不能发生。
围绕一个循环移动所有国王需要移动，但不会改变棋盘的状态。因此，这种情况意味着您在原始映射中找到的路径集是 not 最小的。由于它们 是 最小的，所以这种情况是不可能的。
假设我们有一个棋盘（任意大小）和最初放置在 N 个方格上的 N 个国王。让我们假设现在我们 select N 个新方格通过一系列合法的移动（无碰撞）将国王移动到。目标是最小化所有国王移动的总距离。我真的想不出一个 algorithm/adaptation 可以在处理移动所有棋子的同时注意防止“碰撞”国王。该算法应该比递归 selecting 目标方块和 selecting 最小传输更快。我希望有人对这个问题有宝贵的建议。
谢谢
以下算法应该有效：
- 找到距离最近的国王更远的目标方格。
- 将最近的国王移到那个方格。 （不会发生阻塞，因为一个国王必须更靠近另一个国王才能阻止另一个国王）
- 重复直到所有国王都被移动到一个目标。
它的目标上的国王可能会在#2 中阻挡未移动的国王，但我不确定这是否会发生。
经过进一步思考，我很清楚我上面的算法更像是一种贪心法启发式算法，而不是确定性解决方案。我可以很容易地想出一个无法产生最佳解决方案的例子。
考虑当 N=4 在 [(1 到 5)x(1 到 5)] 板上时：
- 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) 并且可能不是第一个。
首先，您需要找到所有国王和所有目标方块之间的最小总距离完全二分匹配。您可以通过将每个距离替换为权重 (something_big-distance) 将其重铸为 maximum weight bipartite matching，然后找到最大权重二分匹配，或者您可以只维护匹配完成的不变量并找到最小值直接二分匹配
我认为最简单的方法是使用 Edmonds-Karp Algorithm。这通常用于寻找最大流，但最大权重二分匹配本质上是该问题的一个实例，一旦您添加单个源和汇点顶点。
找到国王与其目标方格之间的匹配项后，您就可以移动国王了。只要您沿着最短路径移动每个国王，并且您不将国王移动到已经被占据的方格上，那么您制作它们的顺序并没有太大区别。如果一个国王想要移动到一个被占领的方格上，有两种选择：
- 如果拦路之王尚未到达其目标方格，则只需移动那个方格即可。
- 如果挡路王已经在它的目标方格上，那么在你想要移动的国王和挡路王之间交换目标。然后移动国王在路上。这不会改变您必须进行的移动总数。
当然，国王在路上也可能有一个国王它的方式，所以再次应用这些规则，直到你得到一个你可以移动的。
现在您可能想知道如果每个必须移动的国王都有一个国王顺其自然，该怎么办。这只有在存在一个所有国王都想绕着这个循环移动的循环时才会发生……但这不能发生。
围绕一个循环移动所有国王需要移动，但不会改变棋盘的状态。因此，这种情况意味着您在原始映射中找到的路径集是 not 最小的。由于它们 是 最小的，所以这种情况是不可能的。