带边权重依赖的加权图匹配：除整数线性规划外的标准解法？

这类问题属于带边间联合收益的匹配问题，常规Blossom算法仅能处理边权重独立的场景，除整数线性规划外，可参考以下几种标准思路：

1. 图扩展法 #

核心是把边的依赖关系编码到扩展后的图结构中，将联合收益转化为独立权重的边，从而复用现有匹配算法：

• 针对成对依赖的场景（如选C-D则A-B权重提升），可构建状态化扩展图：为原节点添加状态维度，状态代表是否已选中触发权重变化的边。比如设置状态0为未选C-D，状态1为已选C-D，那么A-B在状态0的权重为5，状态1的权重为10；C-D仅在状态0中存在，权重为其本身值，选中后则转移到状态1。随后在这个扩展图上求解最大权重匹配即可。
• 局限性：若依赖关系复杂（多组边互相依赖），扩展图的规模会指数级增长，仅适用于依赖组数量较少的场景。

2. 动态规划（DP） #

当图具有特定拓扑结构（如树、有顺序的二分图）时，可通过DP处理依赖：

• 设计DP状态记录已选中的触发依赖的边集合，按节点顺序处理，计算当前节点匹配时的最大收益。例如在树结构中，以子树为单位，状态记录子树内是否选中了触发依赖的边，逐步合并求解全局最优。
• 局限性：状态空间大小依赖于独立依赖边的数量，仅适合依赖关系简单的场景。

3. 启发式与近似算法 #

针对大规模、依赖复杂的场景，精确求解成本过高时，可采用启发式思路：

• 贪心+调整：先求解常规最大权重匹配，再遍历所有依赖关系，检查是否存在替换边以获取更高联合收益的可能，逐步优化匹配结果。
• 局部搜索：从初始匹配出发，通过交换边的操作探索包含依赖收益的邻域解，保留更优的结果，直到无法提升。
• 这类方法无法保证最优解，但能在合理时间内得到较好的近似解。

4. 分支定界结合Blossom算法 #

将依赖关系拆解为离散的分支场景，分别用Blossom算法求解后取最优：

• 针对“选X边则Y边权重变化”的依赖，分两种分支：
  • 分支1：强制将X边加入匹配，调整Y边的权重后，用Blossom算法求解剩余图的最大匹配，计算总收益；
  • 分支2：强制排除X边，用原权重求解最大匹配，计算总收益。
• 取两个分支的最优结果作为最终解。若存在多组独立依赖，可递归进行分支，适合依赖组数量较少的场景。

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