Skip to content

Munkres’ Assignment Algorithm

这是我在准备考研复试上机遇到的一个问题，在清华 OJ 上的题目，其实也是经典的题目

算法解决什么？

如图所示，一言以蔽之，找最小消耗的匹配。这个问题很常见，比如 n 个工人处理 n 个事情。

算法原理

还是一样，我不进行算法原理讲述，我只是搬运工。这里有几个不错的文章：
1. https://www.cnblogs.com/xiaxuexiaoab/p/17838305.html: 这篇文章可以暂时不用看后面的第四章及之后的内容，前面的例子特别好。
2. https://blog.csdn.net/yiran103/article/details/103826367: 这篇文章快速浏览一遍即可
3. https://users.cs.duke.edu/~brd/Teaching/Bio/asmb/current/Handouts/munkres.html: 这篇文章据说代码非常好，我当时就是看的这篇弄懂的。

注意: 不要和最大匹配弄混

这个方法也叫做匈牙利算法。我在网上查的资料，百分之八九十都在介绍二分图，介绍匹配。但很多都弄错了，匈牙利算法不是求最大匹配，而是求最大权匹配。

最大匹配就是二分图中，找出匹配边数最多的匹配。而最大权匹配，是指的在最大匹配前提下，边上有权重，求出边权和最大的匹配。

对于上面的 Munkres' Assignment Algorithm，它是两两都有权重，所以最大匹配那肯定是 n，所以这个问题和最大匹配没关系，本质是最大权匹配。

同时也不要和最大婚姻算法弄混了，如下是 GPT 帮忙总结的内容：

匹配问题
│
├── 二分图匹配（Graph Matching）
│   │
│   ├── 最大匹配（Maximum Matching）
│   │   - 问题：匹配边数最大
│   │   - 算法：增广路算法（国内常叫“匈牙利算法”）
│   │   - 特点：不考虑权重，能匹多少匹多少
│   │
│   └── 带权匹配（Weighted Matching）
│       │
│       ├── 最优分配问题（Assignment Problem）
│       │   - 问题：总代价最小/效益最大
│       │   - 算法：Hungarian Method (Kuhn, 1955)，改进版 Munkres (1957)
│       │   - 特点：必须是完美匹配
│       │
│       └── 一般图最小权匹配（更复杂，用 Blossom algorithm 等）
│
└── 稳定匹配（Stable Matching）
    │
    └── 稳定婚姻问题（Stable Marriage Problem）
        - 问题：没有两个人会互相更喜欢对方而背弃现配偶
        - 算法：Gale–Shapley 提议–接受算法
        - 特点：关注稳定性，而非边数或权重

Comments