顾森新书《神机妙算：一本关于算法的闲书》 | 图论算法：稳定婚姻问题
作者简介
顾森（Matrix67），数学、算法爱好者，上古数学科普博客Matrix67.com博主，《思考的乐趣》、《浴缸里的惊叹》作者。重症拖延癌患者。
蔡雪琴（@_404号），人类幼崽饲养员，业余设计师。与作者是夫妻兼挚友。
代序
多年前的一个晚上，本书作者找到我，说会在《程序员》杂志连载一系列文章，主题是生活中的算法。连载结束后，会集结成册汇成一本书，他想请我为这本八字还没一撇的书绘制插图。
一开始我是拒绝的。我既不是专业插画师，对所谓生活中的算法也没什么概念，这本书能不能顺利出版也还是未知数，但在他的一再坚持下，最终还是答应了这个缥缈的请求。当时我俩谁也没想到，他所说的这本书，从连载到最后成型出版，整整酝酿了八年。这八年间，我已经和他结了婚，我们的两个孩子都比这本书先“问世”了。
连载的那段时间，他每完成一篇文章，都会先发给我看看。而我作为这个系列的第一个读者，每次看完都会反馈给他能不能看懂、有没有问题、好不好玩，从一个业余读者的角度，尽可能地监督他把问题简单有趣地讲明白。
一个算法，可以讲到它的前世今生，讲到它在生活中的应用，就连我们在生活中遇到的真实问题，也被他写进书里做例子，甚至附上了日期时间。跨越八年，有些例子也带上了些许年代感，令人感叹。
临近出版，该给书写个序了。他坐在我边上盯着屏幕发呆，似乎没什么思路。瞄了一眼屏幕，这个家伙竟然在一本正经地搜索“如何给一本书写序”……我说要不我先从我的角度写写吧，抛砖引玉，看看我写完能不能给你点灵感。于是便有了这篇代序。
——蔡雪琴，2021 年 8 月
序言
小学时，我特别喜欢解数学谜题。为了把狼、羊、白菜运到河对岸，为了找出重量较轻的那枚假币，为了在 3 分钟内煎好全部大饼，为了判断出谁是骑士谁是无赖，我常常会废寝忘食地在纸上写写画画，最后为自己发现了答案而兴奋不已。有个谜题让我至今记忆犹新：把 4 个 A、4 个 B、4 个C、4 个 D 排成一个 4 × 4 的方阵，使得每一行都没有重复的字母，每一列也没有重复的字母。我把它解决了，而且获得了更大的爽快感。因为，问题的答案并不是我盲目地试出来的，而是用一个自己想到的“招数”得出的。在第一排按顺序写下 A、B、C、D 这 4 个字母，然后把第一个字母挪到最后面，变成下一排的字母顺序，并且不断地这样做下去。等 4 排都写完了，就会得到一个正确的答案。
A B C D
B C D A
C D A B
D A B C
而且我发现，这个“招数”十分万能，它可以直接用于字母更多的情况。现在回想起来，这没准儿是我解决的第一个算法问题。
中学时，我开始搞信息学竞赛，才知道这是一个经典问题，叫作拉丁方阵（Latin square）。当年我找到的，不过是 4 阶拉丁方阵的一个最基本的解。4 阶拉丁方阵还有很多，有些没法拿我当年的“招数”得出，比如下面这个：
A D B C
B C A D
C B D A
D A C B
更让我吃惊的是，这个看似纯粹的数字游戏，在生产生活中竟然有非常真实的应用。假设某汽车发动机制造商想要测试并比较 4 种汽油添加剂的性能。不妨把这 4 种汽油添加剂分别记作 A、B、C、D。如果所有试验全在某一辆车上进行，可能会出现一些问题，比方说该车的某些特性正好能让A 充分发挥性能，最终的试验结果会显示 A 的性能更好，但这个结论无法广泛适用于各种场合。类似地，驾驶员的习惯或许也会无意地影响到试验结果。为了消除这些因素的影响，我们可以选择 4 辆不同的车（编号分别为 1、2、3、4）、4 名不同的驾驶员（编号也分别为 1、2、3、4）。在我当年得出的拉丁方阵中，第 2 行第 3 列是 D，我们就把 D 装进 2 号车，交给3 号驾驶员去开。所有 16 次测试中，每种汽油添加剂都用了 4 次，这 4 次都是跟不同的车、不同的驾驶员搭配，而且每一名驾驶员都没开过重复的车。这样得到的试验结果就能很好地反应更普遍的情况。
算法，不但是编写程序的人需要掌握的一门学问，在人们的日常生活中也扮演着重要的角色。拉丁方阵就是一个非常好的例子。
大学时，看了不少科普书，自己也试着写了一些。当时，市面上有很多经济学、心理学等“兴趣学科”的优秀科普书，既不像教科书那样无趣，又不像“快餐书”那样泛泛而谈，不管是门外汉还是业内人士，看完后都觉得收获颇丰。我忽然萌生了一个想法：算法也是一个应用广泛、妙趣横生的学科，计算机行业内外的人应该都会有兴趣，但为什么没有写给大家看的算法书呢？那时，我就计划着自己写一本。
我和很多人分享了这个想法。2012 年，应卢鸫翔编辑的邀请，我开始为《程序员》杂志的算法栏目供稿。2013 年末，稿件数量已经累积到我觉得比较满意的程度了，我便着手将它们串联并扩充成一本完整的算法书。2015年，这本书的初稿终于完成了。接下来，这本书进入了漫长而曲折的审校打磨阶段，图书编辑和插画师轮番抱娃，耽误了不少进度，我作为完美主义者、拖延症患者和插画师的孩子他爸，对此书跳票亦有卓越贡献。一眨眼，已经到 2020 年了。八年的时间里凝聚了太多人的智慧和汗水。这里，向所有对这本书的写作和出版有帮助的人致谢。
最后，也想对正在阅读序言的你说一句，祝愿这本书能陪伴你度过一段难忘的算法之旅。如果你喜欢刚才那个拉丁方阵的例子，那你可要做好准备了。拉丁方阵不过是算法这个游乐园里的旋转木马，后面的内容将会像过山车一样惊险刺激！
——顾森，2021年8月
编辑推荐
适读人群 ：所有对算法感兴趣的人群
兴趣永远是好老师！好奇心是有效的驱动力！
这是一本妙趣横生的算法书。作者从小对算法有浓郁的兴趣，乐此不疲地研究各类算法问题，有一天，他突然意识到：“算法，不但是编写程序的人需要掌握的一门学问，在人们的日常生活中也扮演着重要的角色。拉丁方阵就是一个非常好的例子。“——这本书就这样诞生了，一本写给大家看的算法闲书。
说它闲，其实它并不闲，短短的篇幅却涵盖了本领域的各类经典算法；
说它不闲，它又正儿八经是本小闲书，生活中的事例随处可见，读来亲切自然，读者完全可以在悠闲的漫步中收获种种小惊喜！
《神机妙算：一本关于算法的闲书》选用生活中平常的事例，激发出读者的好奇心和兴趣，再用生动的语言、有趣的手绘图表，引导读者透视其背后隐藏的算法思想，牵引出一个个经典算法，关键是，这些算法不仅仅是纸上谈兵，而且实实在在地能帮助人们解决生活中的难题。
相信每一位读者，不仅能通过《神机妙算：一本关于算法的闲书》拓展自己的见识，更能借此锻炼自己的思维能力，举一反三，解决更多生活和工作中的难题。
内容简介
本书撷取生活中的趣闻逸事，将它们抽象成一个一个算法，寓教于乐，阐述了主流算法背后的来龙去脉，包括贪心算法、排序算法、RSA 算法、递归、分治、动态规划等经典内容,让读者在轻松的文笔中获得思考的乐趣。视角独特，表达方式深入浅出，以小见大。在轻松的学习中享受思考带来的乐趣，也是有益的思维锻炼。本书适合任何对算法有好奇心的人群阅读。
目录
图论算法
稳定婚姻问题
欧拉路径与德布鲁因序列
网络流与棒球赛淘汰问题
贪心与动态规划
一类最优序列问题的贪心算法
动态规划与文本排版
最优前缀码问题
递归与分治
组合游戏中的必胜策略
格雷码及其应用
漫话图像抖动技术
一堂特别的排序算法课
跨越千年的 RSA 算法
可公度线段与辗转相除法
中国剩余定理与贝祖定理
从欧几里得定理到欧拉定理
公钥加密与 RSA 算法
密码学与协议
散列函数与承诺方案
有限域上的多项式插值与秘密共享协议
基于 RSA 算法的数字现金协议
计算几何
线性代数的魅力
美术馆问题
KD 树与最邻近搜索
智力游戏的启示
“囚犯与灯泡”游戏与跷跷板协议
猜帽子游戏与汉明码
中文信息处理与数据挖掘
汉语的句法结构识别和语义识别
社交网络里的文本数据挖掘
图灵机与 NP 问题
可数集、图灵机及我们的世界
P 问题、NP 问题及 NP 完全问题
图论算法：稳定婚姻问题
什么是算法？
每当有人问我这样的问题，我总会引用下面这个例子。
假如你是一个媒人，有若干名单身男子登门求助，还有同样多的单身 女子也来征婚。如果你已经知道这些女孩儿在每个男孩儿心目中的排名，以及男孩儿们在每个女孩儿心目中的排名，那么你该怎样为他们牵线配对呢？
最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。
这当然很完美，但绝大多数情况下都不可能实现。
比方说，男 1 号的最爱是女 1 号，而女 1 号的最爱不是男 1 号，这两个人的最佳选择就不可能被同时满足。如果出现了好几位男士的最爱是同一个女孩儿的情况，这几位男士的首选也不会同时得到满足。
当这种最为理想的配对方案无法实现时， 怎样的配对方案才能令人满意呢？
其实，找对象不见得需要那么完美，和谐才是关键。
如果男 1 号和女 1 号各有各的对象，但男 1 号觉得女 1 号比自己的现任更好，女 1 号也觉得对方比自己的现任更好，那么两人就可能扔下自己现在的另一半，走在一起——因为这个结果对他们两人都更好一些。
如果在一种男女配对方案中出现了这种情况，我们就说这种配对方案是不稳定的。作为一个红娘，你深深地知道，介绍对象就怕婚姻关系不稳定。因此，在给客户牵线配对时，虽然不能让每个人都得到最合适的，但婚姻搭配必须得是稳定的。
现在，我们的问题就是：稳定的婚姻搭配总是存在的吗？如果存在，又应该怎样寻找出一个稳定的婚姻搭配？
为了便于分析，下面我们做一些约定。我们用字母 A、B、C 对男性进行编号，用数字 1、2、3 对女性进行编号。我们把所有男性从上到下列在左侧，括号里的数字表示每个人心目中对所有女性的排名；再把所有女性列在右侧，用括号里的字母表示她们对各位男性的偏好。
图 1 所示就是有 2 男 2 女的一种情形，每个男的都更喜欢女 1 号，但女 1 号更喜欢男 B，女 2 号更喜欢男 A。若按 A—1、B—2 进行搭配，则男 B 和女 1 都更喜欢对方一些，这样的婚姻搭配显然是不稳定的。但若换一种搭配方案（如图 2 所 示），这样的搭配就是稳定的了。
图 1 一个不稳定的婚姻搭配（男 B 和女 1 都不满意现任伴侣）
图 2 一个稳定的婚姻搭配
可能很多人会立即想到一种寻找稳定婚姻搭配的策略：不断修补当前搭配方案。如果两个人互相之间都觉得对方比自己当前的伴侣更好，那就让这两个人成为一对，刚刚被甩的那两个人组成一对。如果还有想要在一起的男女对，就继续按照他们的愿望对换情侣，直到最终消除所有的不稳定组合。
容易看出，应用这种“修补策略”所得到的最终结果一定满足婚姻的稳定性，但这种策略的问题在于，它不一定有一个“最终结果”。按照 上述方法反复调整搭配方案，最终有可能陷入一个死循环，无法得出一个确定的方案（如图 3 所示）。
图 3 应用“修补策略”可能会产生死循环
1962年，美国数学家戴维·盖尔（David Gale）和罗伊德·沙普利（Lloyd Shapley）发明了一种寻找稳定婚姻的策略。
不管男女各有多少人，也不管他们各自的偏好如何，应用这种策略后总能得到一个稳定的婚姻搭配。换句话说，他们证明了稳定的婚姻搭配总是存在的。
有趣的是，这种策略反映了现实生活中的很多真实情况。
在这种策略中，男士将一轮一轮地去追求他中意的女子，而女子可以选择接受或拒绝相应的追求者。第一轮，每位男士都选择向自己最心仪的女子表白。
此时，每个女子可能面对的情况有三种：没有人向她表白，只有一个人向她表白，有不止一个人向她表白。
在第一种情况下，这个女子什么都不用做，只需继续等待；在第二种情况下，接受那个人的表白，答应暂时和他做男女朋友；在第三种情况下，从所有追求者中选择自己最中意的那一位，答应暂时和他做男女朋友，并拒绝其他所有的追求者。
第一轮结束后，有些男士已经有女朋友了，有些男士仍然单身。第二轮，每位单身男士都从所有尚未拒绝他的女子中选出自己最中意的，并向她表白，无论她现在是否单身。
和第一轮一样，每位女子需要从表白者中选择自己最中意的一位，拒绝其他追求者。
注意，如果这个女子已经有男朋友，当遇到更好的追求者时，她必须抛开现任男友，投向新的追求者的怀抱。这样，一些单身男士将会找到女友，而那些已经有女友的也可能会恢复单身。
在以后的每一轮中，单身的男士继续按照心目中的排序追求下一个女子，而女子则从包括现男友在内的所有追求者中选择自己最中意的一个，并对其他人说不。这样一轮一轮地进行下去，直到某个时候所有人都不再单身，接下来的一轮将不会发生任何表白，整个过程也就自动结束 （如图 4 所示）。此时的婚姻搭配就一定是稳定的了。
图 4 应用上述策略，三轮之后将得出稳定的婚姻搭配
这个策略会不会像之前的修补法一样，出现永远也无法终止的情况呢？
不会。
下面我们将说明，随着轮数的增加，总有一个时候所有人都能配上对。
由于在每一轮中，至少会有一个男士向某个女子告白，因此总的告白次数将随着轮数的增加而增加。倘若整个流程一直没有因所有人都配上对而结束，最终必然会出现某个男子追遍了所有女孩儿的情况。而一个女孩儿只要被人追过一次，以后就不可能再单身了。既然所有女孩儿都被这个男人追过，就说明所有女孩儿现在都不是单身，也就是说此时所有人都配上对了。
接下来，我们还需要证明，这样得出的配对方案确实是稳定的。
首先注意到，随着轮数的增加，一个男人追求的对象总是越来越糟，而一个女孩儿的男友只可能变得越来越好。假设男 A 和女 1 各自有各自的对象，但比起现在的对象来，男 A 更喜欢女 1。
因此，在此之前男 A 肯定已经跟女 1 表白过。既然女 1 最后没有跟男 A 在一起，说明女 1 拒绝了男 A，也就是说她有了比男 A 更好的男人。这就证明了，两个人虽然不是一对，但都觉得对方比自己现在的伴侣好，这样的情况绝不可能发生。
我们把用来解决某种问题的一个策略，或者说一个方案，或者说一个 处理过程，或者说一系列操作规则，或者更贴切的，一套计算方法，叫作“算法”（algorithm）。
上面这个用来寻找稳定婚姻的策略就叫作“盖尔–沙普利算法”（Gale-Shapley algorithm），有些人也管它叫“延迟认可算法”（deferred acceptance algorithm）。
盖尔–沙普利算法带给我们很多启发。作为一个为这些男女牵线的媒人，你并不需要亲自使用这个算法来计算稳定匹配，甚至根本不需要了解每个人的偏好，而只需按照这个算法组织一个男女配对活动即可。你要做的仅仅是把算法流程当作游戏规则告诉大家，游戏结束后会自动得到一个大家都满意的婚姻匹配。
整个算法可以简单地描述为：每个人都去做自己想做的事情。
对于男性来说，从最喜欢的女子开始追起是顺理成章的事；对于女性来说，不断选择最好的男子也正好符合她的利益。因此，大家会自动遵守游戏规则，无须担心有人虚报自己的偏好。
历史上，这样的“配对游戏”还真有过实际应用，并且更有意思的是， 这个算法的应用居然比算法本身的提出还早 10 年。
早在 1952 年，美国就开始用这种办法给医学院的学生安排工作，这被称为“全国住院医师配对项目”。
配对的基本流程就是，各医院从尚未拒绝这一职位的医学院学生中 选出最佳人选并发送聘用通知，当学生收到来自各医院的聘用通知后，系统会根据他所填写的意愿表自动将其分配到意愿最高的职位，并拒绝掉其他的职位。如此反复，直到每个学生都分配到了工作。
当然，那时人们并不知道这样的流程可以保证工作分配的稳定性，只是凭直觉认为这是很合理的。直到 10 年之后，盖尔和沙普利才系统地研究了这个流程，提出了稳定婚姻问题，并证明了这个算法的正确性。
这套理论成功地解决了诸多市场资源配置问题，罗伊德·沙普利也因此获得了 2012 年诺贝尔经济学奖。很可惜，戴维·盖尔没能与他共享这一荣誉——他在 2008 年就已经离开人 世了。
盖尔–沙普利算法还有很多有趣的性质。比如说，大家可能会想，这种男追女女拒男的方案对男性更有利还是对女性更有利呢？答案是，这种方案对男性更有利。
事实上，稳定婚姻搭配往往不止一种，然而上述算法的结果可以保证，每一位男性得到的伴侣都是所有可能的稳定婚姻搭配方案中最理想的，同时每一位女性得到的伴侣都是所有可能的稳定婚姻搭配方案中最差的。受篇幅限制，我们略去证明的过程。
当然，为了得到一种对女性最优的稳定婚姻搭配，我们只需要把整个算法反过来，让女孩儿去追男孩儿，男孩儿拒绝女孩儿就行了。
这个算法还有一些局限性。例如，它无法处理 2𝑛 个人不分男女的稳定搭配问题。
一个简单的应用场景便是宿舍分配问题：假设每个宿舍住两个 人，已知 2𝑛 个学生中每一个学生对其余 寻找一个稳定的宿舍分配？此时，盖尔 2𝑛 − 1 个学生的偏好评价，如何 –沙普利算法就不再有用武之地了。
而事实上，宿舍分配问题中很可能根本就不存在稳定的搭配。例如，有 A、 B、C、D 四个人，其中 A 把 B 排在第一，B 把 C 排在第一，C 把 A 排在第 一，而且他们三人都把 D 排在最后。容易看出，此时一定不存在稳定的宿舍分配方案。倘若 A、D 同宿舍，B、C 同宿舍，那么 C 会认为 A 是更好的室友（因为 C 把 A 排在了第一），同时 A 会认为 C 是更好的室友（因为他 把 D 排在了最后）。同理，B、D 同宿舍或者 C、D 同宿舍也都是不行的，因而稳定的宿舍分配是不存在的。
此时，重新定义宿舍分配的优劣性便是一个更为基本的问题。稳定婚姻问题还有很多其他的变种，有些问题至今仍然没有一种有效的算法。这些问题都是图论当中非常有趣的话题。
感谢出版社支持
评论点赞数最高的5位读者
12月9日晚12时截止
可获出版社赠新书