算法简史

作者简介

克里斯·布利克利（Chris Bleakley），爱尔兰都柏林大学计算机科学学院教授，曾任该院院长，有近40年的算法设计经验。除学术研究和教学外，布利克利在产业界也有丰富的从业经验，曾担任多家业内公司的顾问、高级研究员和副总裁。

内容简介

第6章 大海捞针 稳定的婚姻 路线图并不是组合优化问题的唯一体现。匹配问题寻求以最佳方式配对对象。一个典型的匹配问题是将有希望的大学申请人与可供申请的课程进行配对。我们面临的挑战是，如何以一种既公平又能让尽可能多的学生和大学满意的方式为高中毕业生分配课程。与其他组合优化问题一样，随着对象数量的增加，匹配变得困难。即使是面对中等数量的学生，也必须使用快速算法。 关于配对的开创性论文是由大卫·盖尔（David Gale）和劳埃德·沙普利（Lloyd Shapley）在1962年发表的。两人在新泽西州的普林斯顿大学建立了友谊，他们都在那里攻读数学博士学位。从普林斯顿大学毕业后，盖尔加入了位于罗得岛的布朗大学，而沙普利则去了兰德公司。盖尔和沙普利的论文解决了一个由来已久的问题，即为单身人士匹配婚恋对象。 “稳定婚姻问题”（Stable Marriage Problem）寻求的是让男性和女性配对结婚。一开始，女性参与者根据自己的喜好对所有男性进行排名（第1名、第2名、第3名等），反之亦然，男性也对女性进行排名。问题的目标是让参与者以一种让婚姻稳定的方式配对。如果不存在一男一女对彼此的偏爱超过他们各自对自己配偶的偏爱，那么他们与其配偶的组合就被认为是稳定的。否则，他们和他们的配偶就可能会离婚。 盖尔和沙普利的论文提出了一个非常简单的算法来解决稳定婚姻问题。事实上，它是如此简单，以至于作者们根本就没有办法发表它。在论文中，盖尔和沙普利使用稳定婚姻问题作为现实世界中一系列双向（two-way）匹配问题的代表。“双向”指的是双方都有自己的偏好，而不仅仅是一方有。盖尔—沙普利算法迅速成为实际上的双向匹配方法。该算法至今仍被广泛应用于各种实践场景中，包括为危重病人匹配器官捐赠者。 盖尔—沙普利算法在连续的多个回合中匹配男性和女性。在每一轮匹配中，所有单身男性都要求婚一次。每一位单身男性都会向他最喜欢的且之前没有拒绝过他的女性求婚。如果被求婚的女性还没有订婚，她会自动接受求婚。如果她已经订婚了，那么她会比较自己对新追求者和对自己的未婚夫的偏好。如果她更喜欢她的新追求者，她就会抛弃她的未婚夫，并与她的新情人订婚。如果她更喜欢她的未婚夫，她会拒绝潜在闯入者的求爱。一旦她做出了决定，算法就会继续关注下一位未婚男性。当所有未婚男性都求过婚后，算法就会进入下一轮匹配。在这个阶段，一个被抛弃的未婚夫可以自由地向其他人求婚。当所有参与者都完成订婚时，算法就结束了。 假设有6个朋友——3位男性和3位女性——住在纽约靠近中央公园的两套公寓里，仅隔着一条走廊。为了谨慎起见，我们称他们为亚历克斯、本、卡洛斯、黛安娜、埃玛和菲奥娜。大家互相都认识，所有人都是单身，他们都有结婚的念头。当被问及婚姻偏好时，他们的陈述见表6.2。 在第一轮匹配中，亚历克斯向黛安娜求婚。黛安娜接受了，因为她现在单身。接下来，本向广受欢迎的黛安娜求婚。由于黛安娜更喜欢本而不是亚历克斯，所以她抛弃了后者，接受了本的求婚。卡洛斯也向黛安娜求婚，但被断然拒绝。在第二轮匹配中，亚历克斯和卡洛斯是单身。亚历克斯向埃玛求婚，这是他求婚列表上的第2名。埃玛到目前为止还没有伴侣，所以她默许了亚历克斯的求爱。卡洛斯向菲奥娜求婚，菲奥娜答应了，因为她现在还没有订婚。就是这样。现在每个人都订婚了——亚历克斯和埃玛、本和黛安娜、卡洛斯和菲奥娜。所有的婚姻都很稳定。埃玛更喜欢本，但她无法拥有本，因为本宁愿与黛安娜——他的准妻子——结婚。同样，亚历克斯和卡洛斯对黛安娜有单相思，但黛安娜准备嫁给她的理想男人——本。菲奥娜很开心地和她的头号人选卡洛斯订婚了，尽管卡洛斯也喜欢黛安娜。 作为一种安排约会的方法，盖尔—沙普利算法是残酷的——看看所有这些拒绝！然而，也有人会怀疑，人类在寻找伴侣时是否真的会从直觉上遵循类似于盖尔—沙普利算法的思想过程。在现实生活中，明确的求婚和坚定的答复变成了隐秘的微笑、渴望的眼神、通过朋友的询问和礼貌的拒绝。有相似之处，也有不同之处。事实上，人的偏好会随着时间的推移而演变。分手的情感代价意味着个人不愿做出重大改变。尽管存在这些矛盾，一些线上婚恋机构现在还是使用盖尔—沙普利算法来匹配客户。 美国住院医师匹配计划（National Residency Matching Program，NRMP）每年都会开展世界上规模最大的匹配活动之一。该计划将医学院毕业生与美国各地医院的实习机会进行配对。目前，该项目每年为4.2万名毕业生申请者提供3万个医院职位。1952年创立时，NRMP采用了之前一家票据清算所的匹配算法。波士顿池（Boston Pool）算法被NRMP一用就是40年。20世纪70年代，人们发现波士顿池算法实际上和独立开发的盖尔—沙普利算法是一样的东西。这对著名的数学家—经济学家组合做出这项发明比不知名的波士顿池团队晚了超过10年，这相当令人尴尬。当然，前者的学术论文包含了正式的证明，而波士顿池算法是专门针对票据清算写的。 20世纪90年代，著名经济学家、数学家阿尔文·罗斯（Alvin Roth）参与了对NRMP 匹配算法的改进。随着时代的发展，罗斯的新方法允许从医的夫妻寻求同城工作。它还力求防止不怀好意的申请者利用系统为自己谋利。与波士顿池算法不同，罗斯的技术依赖于单向匹配，即只考虑申请人的偏好。 沙普利和罗斯因为他们在博弈论（game theory）领域的研究于2012年被授予诺贝尔经济学奖。博弈论是数学的一个分支，研究聪明决策者之间的竞争与合作。沙普利被广泛认为是一位伟大的理论家，他为罗斯关于市场如何运作的实践性研究奠定了基础。他们的诺贝尔奖授奖词强调的贡献之一是盖尔—沙普利算法。盖尔于2008年去世，因此无法获得诺贝尔奖。沙普利于2016年去世，享年92岁。罗斯继续在斯坦福大学和哈佛大学工作。 1.一部横跨4000年的算法简史 2.语言通俗易懂，不使用编程语言，全书几乎没有一个公式 3.一本书读懂算法如何塑造、影响我们的日常生活：导航软件、语音和图像识别、自然语言处理、社交网络的“流量密码”、人工神经网络…… 4.中国工程院院士、中科曙光创始人兼董事长、中国计算机学会杰出贡献奖获得者李国杰、清华大学计算机科学与技术系教授马少平、中国科学院沈阳自动化研究所研究员周晓锋携手推荐