棋盘上N个国王移动总距离最小化的无碰撞高效算法问询

问题核心拆解 #

该问题可以拆分为两个独立的可解子问题，完全不需要用递归枚举目标格的低效率方案：

1. 最优目标格匹配：给每个国王分配独有的目标格，保证所有国王的总移动距离最小
2. 无碰撞路径调度：规划移动顺序和路径，保证全程没有碰撞，且总开销尽可能贴近匹配得到的理论最小值

最优目标格匹配方案 #

国王的单步移动支持8个方向，两点之间的最短移动距离为切比雪夫距离：max(|x1-x2|, |y1-y2|)，基于这个特性可以用远优于递归的效率完成匹配：

• 如果目标格可以任意选择（仅要求互不重叠）：将所有国王初始坐标的x+y和x-y分别排序，按排序后的对应值生成目标坐标，即可得到总距离最小的目标分配，时间复杂度仅为O(N log N)
• 如果目标格是预先指定的N个不重叠格子：将国王初始位置和目标位置作为二分图的两侧，边权为两点的切比雪夫距离，用匈牙利算法/ KM算法求解二分图最小权匹配，时间复杂度为O(N³)，堆优化的KM算法可以进一步压缩到O(N² log N)

无碰撞路径调度方案 #

完成目标匹配后，不需要修改已有的最优匹配结果，仅靠调度就能实现无碰撞，且不会明显增加总移动距离：

• 给所有国王设置固定优先级，比如按初始坐标的x+y升序排列，优先级越高移动权限越高
• 每个国王优先走最短路径，优先级低的国王遇到冲突时，选择原地等待或绕开冲突点1步即可，国王8方向移动的特性保证绕路最多只会给单个国王增加1~2步的开销，对总距离的影响可以忽略
• 同步移动场景下只需额外禁止同一时间步两个国王进入同一格、以及两个国王直接交换位置的情况即可，调度的时间复杂度为O(N*T)，其中T为所有国王的最长移动路径长度

效率对比 #

内容的提问来源于stack exchange，提问作者Ian L