热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【送书福利】图论算法:如何找到最适合自己的另一半?

文末抽奖送书3本什么是算法?每当有人问我这样的问题,我总会引用下面这个例子。假如你是一个媒人,有若干名单身男子登门求助,还有

文末抽奖送书3本

44c512d5447c009e9ddbe961a5eeb3f9.png

什么是算法?

每当有人问我这样的问题,我总会引用下面这个例子。 

假如你是一个媒人,有若干名单身男子登门求助,还有同样多的单身 女子也来征婚。如果你已经知道这些女孩儿在每个男孩儿心目中的排名,以及男孩儿们在每个女孩儿心目中的排名,那么你该怎样为他们牵线配对呢? 

最好的配对方案当然是,每个人的另一半正好都是自己的“第一选择”。

这当然很完美,但绝大多数情况下都不可能实现。

比方说,男 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 所 示),这样的搭配就是稳定的了。

758bb59f4ae87c1a6b7a432052b999c9.png

图 1 一个不稳定的婚姻搭配(男 B 和女 1 都不满意现任伴侣)

f740f5ba58c244e089f367a604081a55.png

图 2 一个稳定的婚姻搭配

可能很多人会立即想到一种寻找稳定婚姻搭配的策略:不断修补当前搭配方案。如果两个人互相之间都觉得对方比自己当前的伴侣更好,那就让这两个人成为一对,刚刚被甩的那两个人组成一对。如果还有想要在一起的男女对,就继续按照他们的愿望对换情侣,直到最终消除所有的不稳定组合。

容易看出,应用这种“修补策略”所得到的最终结果一定满足婚姻的稳定性,但这种策略的问题在于,它不一定有一个“最终结果”。按照 上述方法反复调整搭配方案,最终有可能陷入一个死循环,无法得出一个确定的方案(如图 3 所示)。

4d7a6ff185b36d38aa3e1ff1c3757cfe.png

图 3 应用“修补策略”可能会产生死循环

1962年,美国数学家戴维·盖尔(David Gale)和罗伊德·沙普利(Lloyd Shapley)发明了一种寻找稳定婚姻的策略。

不管男女各有多少人,也不管他们各自的偏好如何,应用这种策略后总能得到一个稳定的婚姻搭配。换句话说,他们证明了稳定的婚姻搭配总是存在的。

有趣的是,这种策略反映了现实生活中的很多真实情况。 

在这种策略中,男士将一轮一轮地去追求他中意的女子,而女子可以选择接受或拒绝相应的追求者。第一轮,每位男士都选择向自己最心仪的女子表白。

此时,每个女子可能面对的情况有三种:没有人向她表白,只有一个人向她表白,有不止一个人向她表白。

在第一种情况下,这个女子什么都不用做,只需继续等待;在第二种情况下,接受那个人的表白,答应暂时和他做男女朋友;在第三种情况下,从所有追求者中选择自己最中意的那一位,答应暂时和他做男女朋友,并拒绝其他所有的追求者。

第一轮结束后,有些男士已经有女朋友了,有些男士仍然单身。第二轮,每位单身男士都从所有尚未拒绝他的女子中选出自己最中意的,并向她表白,无论她现在是否单身。

和第一轮一样,每位女子需要从表白者中选择自己最中意的一位,拒绝其他追求者。

注意,如果这个女子已经有男朋友,当遇到更好的追求者时,她必须抛开现任男友,投向新的追求者的怀抱。这样,一些单身男士将会找到女友,而那些已经有女友的也可能会恢复单身。

在以后的每一轮中,单身的男士继续按照心目中的排序追求下一个女子,而女子则从包括现男友在内的所有追求者中选择自己最中意的一个,并对其他人说不。这样一轮一轮地进行下去,直到某个时候所有人都不再单身,接下来的一轮将不会发生任何表白,整个过程也就自动结束 (如图 4 所示)。此时的婚姻搭配就一定是稳定的了。

2cde581278cd84ff7a13552b503287c6.png

图 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 同宿舍也都是不行的,因而稳定的宿舍分配是不存在的。

此时,重新定义宿舍分配的优劣性便是一个更为基本的问题。稳定婚姻问题还有很多其他的变种,有些问题至今仍然没有一种有效的算法。这些问题都是图论当中非常有趣的话题。

* 本文摘自《神机妙算:一本关于算法的闲书》一书,欢迎阅读此书了解更多有关算法的内容!

66284d1d2e1345092ea98e2463ee56bf.gif

94612c4c7a2dcf434b74ce6ca2ee7a22.png

▊《神机妙算:一本关于算法的闲书

顾森 著,蔡雪琴 绘

  • 写给大家看的算法书,用算法来观察生活,解决难题!

  • 《漫画算法》作者小灰、啊哈磊、李智慧等大咖力荐!

本书撷取生活中的趣闻逸事,将它们抽象成一个一个算法,寓教于乐,阐述了主流算法背后的来龙去脉,包括贪心算法、排序算法、RSA 算法、递归、分治、动态规划等经典内容,让读者在轻松的文笔中获得思考的乐趣。视角独特,表达方式深入浅出,以小见大。在轻松的学习中享受思考带来的乐趣,也是有益的思维锻炼。本书适合任何对算法有好奇心的人群阅读。

a4e22e599b3bd722bae9d1ebeb03b874.png

(京东满100减50,快快扫码抢购吧!)

d903bb3dd9d15bac3f9e0ad308a5e24a.png

如果喜欢本文

欢迎 在看丨留言丨分享至朋友圈 三连

福利时间GIFT TIME送书环节又来了感谢大家一直以来的陪伴与支持送书活动参与方法 👇👇👇直接扫码参与抽奖即可


推荐阅读
  • Excel技巧:单元格中显示公式而非结果的解决方法
    本文探讨了在Excel中如何通过简单的方法解决单元格显示公式而非计算结果的问题,包括使用快捷键和调整单元格格式两种方法。 ... [详细]
  • 探索CNN的可视化技术
    神经网络的可视化在理论学习与实践应用中扮演着至关重要的角色。本文深入探讨了三种有效的CNN(卷积神经网络)可视化方法,旨在帮助读者更好地理解和优化模型。 ... [详细]
  • 我整理了HMOV四大5G旗舰的参数,可依然没能拯救我的选择困难症
    伊瓢茕茕发自凹非寺量子位报道|公众号QbitAI报道了那么多发布会,依然无法选出要换的第一部5G手机。这不,随着华为P40系列发布,目前国 ... [详细]
  • Java高级工程师学习路径及面试准备指南
    本文基于一位朋友的PDF面试经验整理,涵盖了Java高级工程师所需掌握的核心知识点,包括数据结构与算法、计算机网络、数据库、操作系统等多个方面,并提供了详细的参考资料和学习建议。 ... [详细]
  • 对于非计算机专业背景的开发者而言,如何快速掌握.NET基础知识以应对技术面试是一个挑战。本文将提供一系列实用建议,帮助读者在短时间内提高.NET基础水平。 ... [详细]
  • Java虚拟机及其发展历程
    Java虚拟机(JVM)是每个Java开发者日常工作中不可或缺的一部分,但其背后的运作机制却往往显得神秘莫测。本文将探讨Java及其虚拟机的发展历程,帮助读者深入了解这一关键技术。 ... [详细]
  • 春季职场跃迁指南:如何高效利用金三银四跳槽季
    随着每年的‘金三银四’跳槽高峰期的到来,许多职场人士都开始考虑是否应该寻找新的职业机会。本文将探讨如何制定有效的职业规划、撰写吸引人的简历以及掌握面试技巧,助您在这关键时期成功实现职场跃迁。 ... [详细]
  • TCP协议中的可靠传输机制分析
    本文深入探讨了TCP协议如何通过滑动窗口和超时重传来确保数据传输的可靠性,同时介绍了流量控制和拥塞控制的基本原理及其在实际网络通信中的应用。 ... [详细]
  • 我的读书清单(持续更新)201705311.《一千零一夜》2006(四五年级)2.《中华上下五千年》2008(初一)3.《鲁滨孙漂流记》2008(初二)4.《钢铁是怎样炼成的》20 ... [详细]
  • 本文详细介绍了如何正确设置Shadowsocks公共代理,包括调整超时设置、检查系统限制、防止滥用及遵守DMCA法规等关键步骤。 ... [详细]
  • Windows操作系统提供了Encrypting File System (EFS)作为内置的数据加密工具,特别适用于对NTFS分区上的文件和文件夹进行加密处理。本文将详细介绍如何使用EFS加密文件夹,以及加密过程中的注意事项。 ... [详细]
  • 本文详细介绍了如何在ARM架构的目标设备上部署SSH服务端,包括必要的软件包下载、交叉编译过程以及最终的服务配置与测试。适合嵌入式开发人员和系统集成工程师参考。 ... [详细]
  • Flutter 核心技术与混合开发模式深入解析
    本文深入探讨了 Flutter 的核心技术,特别是其混合开发模式,包括统一管理模式和三端分离模式,以及混合栈原理。通过对比不同模式的优缺点,帮助开发者选择最适合项目的混合开发策略。 ... [详细]
  • 电商高并发解决方案详解
    本文以京东为例,详细探讨了电商中常见的高并发解决方案,包括多级缓存和Nginx限流技术,旨在帮助读者更好地理解和应用这些技术。 ... [详细]
  • 本文详细介绍了JVM内存分配的相关知识,包括内存规整、内存分配方式以及并发指针碰撞问题的解决方案。 ... [详细]
author-avatar
kanney姜_958
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有