带相邻单元格配对约束的网格最优分配高效算法问询

在N行M列的网格中（N、M≤1000）存在若干红色与绿色单元格，目标是找到红-绿单元格的分配方案，使得匹配的总距离最小。额外约束为：相邻（共享边或顶点）的红色单元格可配对，移动到任意相邻的绿色单元格配对中（允许配对形态不同），且红、绿单元格数量无需相等。

已将问题建模为ILP（整数线性规划）问题：

• 构建红、绿单元格的完全二分图，边权为单元格间的欧氏距离；
• 构建合法红、绿单元格配对的完全二分图，边权为配对中心的欧氏距离；
• 定义布尔变量表示单个/配对分配，约束每个红单元格必须被分配，每个绿单元格最多被分配一次，目标为总距离最小。

已实现基于pulp库的Python版本，约2500条边的场景可在0.5秒内求解。

是否存在比当前ILP方案更高效的最优算法，可适配1000×1000的网格规模，同时满足配对约束？

针对1000×1000的大规模网格，ILP方案会因变量和约束量爆炸无法适配，以下两类最优算法可满足需求：

1. 最小费用流建模求解 #

将问题转化为最小费用流问题，利用网络流的高效算法（如带势的连续最短路算法、容量缩放算法）处理大规模场景：

• 节点构造：
  • 源点、汇点；
  • 红单元格节点：每个红单元格对应一个节点，源点连向该节点，容量1，费用0；
  • 红配对节点：每对相邻红单元格对应一个节点，源点连向该节点，容量1，费用0；同时该节点需连向组成配对的两个红单元格节点，容量1，费用0（确保配对时两个红单元格都被覆盖）；
  • 绿单元格节点：每个绿单元格对应一个节点，该节点连向汇点，容量1，费用0；
  • 绿配对节点：每对相邻绿单元格对应一个节点，该节点连向汇点，容量1，费用0；同时组成配对的两个绿单元格节点需连向该节点，容量1，费用0；
• 边的构造：
  • 红单元格节点→绿单元格节点：边权为两者的欧氏距离，容量1；
  • 红单元格节点→绿配对节点：边权为该红单元格到绿配对中心的欧氏距离，容量1；
  • 红配对节点→绿单元格节点：边权为红配对中心到该绿单元格的欧氏距离，容量1；
  • 红配对节点→绿配对节点：边权为两个配对中心的欧氏距离，容量1；
• 该模型天然满足红单元格必分配、绿单元格最多分配一次的约束，最小费用流的解即为总距离最小的分配方案。

2. 分层匹配+动态规划优化 #

利用网格的空间局部性，通过分层策略降低计算复杂度：

• 局部配对预处理：先生成所有相邻红单元格的候选配对、相邻绿单元格的候选配对，计算所有配对的中心坐标；
• 稀疏二分图最小权匹配：将问题拆分为四类匹配（单个红→单个绿、单个红→绿配对、红配对→单个绿、红配对→绿配对），转化为带约束的二分图最小权匹配。结合四叉树等空间索引，只保留距离较近的节点/配对间的边，再用优化后的KM算法求解；
• 动态规划调整：对局部匹配结果进行动态规划调整，确保相邻红单元格的配对选择不会增加全局总距离，同时满足所有约束条件。

方案对比 #

• 最小费用流方案：严格保证最优解，针对稀疏网络（实际网格中红/绿单元格占比通常较低），高效算法能在可接受时间内处理1000×1000网格；
• 分层匹配+DP方案：在保证最优性的前提下，利用空间局部性进一步压缩计算量，适合红/绿单元格分布集中的场景。

内容的提问来源于stack exchange，提问作者Creative Username