一对一指派问题中的最大成本最小化求解方法问询

问题回顾 #

给定两个各含n个元素的集合A、B，对应n×n的成本矩阵C，其中C[i][j]表示A中第i个元素指派到B中第j个元素的成本。我们需要找到一个一对一的置换指派，使得该指派中所有成本的最大值尽可能小（即minimax目标），替代低效的全枚举法（时间复杂度O(n!)，仅适用于极小n值）。

最优解法：二分查找+二分图完美匹配 #

这是目前效率最高的解法，核心思路是通过二分查找缩小“可能的最大成本”范围，再用二分图匹配验证当前范围是否存在合法指派。

步骤1：确定二分查找边界

• 下界low：取成本矩阵中的最小元素（最小可能的最大成本不会低于单个指派的最小成本）
• 上界high：取成本矩阵中的最大元素（最坏情况的指派最大成本）

步骤2：二分查找迭代验证

1. 计算中间值mid = (low + high) // 2
2. 构造二分图：左侧节点对应A的元素，右侧节点对应B的元素；当且仅当C[i][j] ≤ mid时，给A的第i个元素与B的第j个元素连一条边
3. 检查该二分图是否存在完美匹配（即每个A元素都能找到唯一对应的B元素，无重复）：
   • 若存在完美匹配：说明存在一种指派，所有成本都不超过mid，可以尝试寻找更小的mid，更新high = mid
   • 若不存在完美匹配：说明当前mid过小，无法覆盖合法指派的所有成本，更新low = mid + 1

步骤3：终止与结果

当low == high时，该值即为我们要找的最小化最大成本，对应的完美匹配就是满足目标的指派方案。

复杂度分析 #

• 二分查找次数：O(log(maxC))，其中maxC是成本矩阵的最大元素值
• 每次二分图匹配（用Hopcroft-Karp算法）：O(n²√n)（最多n²条边）
• 整体时间复杂度：O(n²√n log(maxC))，远优于全枚举法，可轻松处理n=100级别的问题

示例演示 #

假设n=3，成本矩阵为：

[
 [3, 5, 2],
 [4, 1, 6],
 [7, 3, 4]
]

1. 初始low=1，high=7，mid=4：构造的边包含所有C[i][j]≤4的组合，存在完美匹配（A0→B0、A1→B1、A2→B2），更新high=4
2. 新的low=1，high=4，mid=2：仅A0→B2、A1→B1有边，A2无可用边，无完美匹配，更新low=3
3. 新的low=3，high=4，mid=3：A2无符合C[i][j]≤3的边，无完美匹配，更新low=4
4. 此时low=high=4，即为最小化的最大成本，对应指派的最大成本为4

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