热门标签 | 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送书环节又来了感谢大家一直以来的陪伴与支持送书活动参与方法 👇👇👇直接扫码参与抽奖即可


推荐阅读
  • Python 数据可视化实战指南
    本文详细介绍如何使用 Python 进行数据可视化,涵盖从环境搭建到具体实例的全过程。 ... [详细]
  • 在多线程并发环境中,普通变量的操作往往是线程不安全的。本文通过一个简单的例子,展示了如何使用 AtomicInteger 类及其核心的 CAS 无锁算法来保证线程安全。 ... [详细]
  • 本文详细介绍了数据库并发控制的基本概念、重要性和具体实现方法。并发控制是确保多个事务在同时操作数据库时保持数据一致性的关键机制。文章涵盖了锁机制、多版本并发控制(MVCC)、乐观并发控制和悲观并发控制等内容。 ... [详细]
  • POJ 2482 星空中的星星:利用线段树与扫描线算法解决
    在《POJ 2482 星空中的星星》问题中,通过运用线段树和扫描线算法,可以高效地解决星星在窗口内的计数问题。该方法不仅能够快速处理大规模数据,还能确保时间复杂度的最优性,适用于各种复杂的星空模拟场景。 ... [详细]
  • 深入浅析JVM垃圾回收机制与收集器概述
    本文基于《深入理解Java虚拟机:JVM高级特性与最佳实践(第3版)》的阅读心得进行整理,详细探讨了JVM的垃圾回收机制及其各类收集器的特点与应用场景。通过分析不同垃圾收集器的工作原理和性能表现,帮助读者深入了解JVM内存管理的核心技术,为优化Java应用程序提供实用指导。 ... [详细]
  • Ihavetwomethodsofgeneratingmdistinctrandomnumbersintherange[0..n-1]我有两种方法在范围[0.n-1]中生 ... [详细]
  • 本文详细介绍了在 Ubuntu 系统上搭建 Hadoop 集群时遇到的 SSH 密钥认证问题及其解决方案。通过本文,读者可以了解如何在多台虚拟机之间实现无密码 SSH 登录,从而顺利启动 Hadoop 集群。 ... [详细]
  • Scrum立会报告+燃尽图(十月十七日总第八次):分配Alpha阶段任务
    此作业要求参见:https:edu.cnblogs.comcampusnenu2018fallhomework2246项目地址:https:git.co ... [详细]
  • 看到成绩时,离散数学得了94分,本以为一切顺利,却没想到多媒体课程只有57分,四年的奖学金梦想也因此破灭。有没有曾经挂过科但后来依然取得好成就的同学?现在心情非常低落,希望能得到一些安慰和建议。虽然挂科有些遗憾,但至少以后不用再上那些乏味的课程了,而且评优的机会也与我无关了。 ... [详细]
  • 本文是Java并发编程系列的开篇之作,将详细解析Java 1.5及以上版本中提供的并发工具。文章假设读者已经具备同步和易失性关键字的基本知识,重点介绍信号量机制的内部工作原理及其在实际开发中的应用。 ... [详细]
  • 在安装 iOS 开发所需的 CocoaPods 时,用户可能会遇到多种问题。其中一个常见问题是,在执行 `pod setup` 命令后,系统无法连接到 GitHub 以更新 CocoaPods/Specs 仓库。这可能是由于网络连接不稳定、GitHub 服务器暂时不可用或本地配置错误等原因导致。为解决此问题,建议检查网络连接、确保 GitHub API 限制未被触发,并验证本地配置文件是否正确。 ... [详细]
  • 深入解析 OpenSSL 生成 SM2 证书:非对称加密技术与数字证书、数字签名的关联分析
    本文深入探讨了 OpenSSL 在生成 SM2 证书过程中的技术细节,重点分析了非对称加密技术在数字证书和数字签名中的应用。非对称加密通过使用公钥和私钥对数据进行加解密,确保了信息传输的安全性。公钥可以公开分发,用于加密数据或验证签名,而私钥则需严格保密,用于解密数据或生成签名。文章详细介绍了 OpenSSL 如何利用这些原理生成 SM2 证书,并讨论了其在实际应用中的安全性和有效性。 ... [详细]
  • Cosmos生态系统为何迅速崛起,波卡作为跨链巨头应如何应对挑战?
    Cosmos生态系统为何迅速崛起,波卡作为跨链巨头应如何应对挑战? ... [详细]
  • Python全局解释器锁(GIL)机制详解
    在Python中,线程是操作系统级别的原生线程。为了确保多线程环境下的内存安全,Python虚拟机引入了全局解释器锁(Global Interpreter Lock,简称GIL)。GIL是一种互斥锁,用于保护对解释器状态的访问,防止多个线程同时执行字节码。尽管GIL有助于简化内存管理,但它也限制了多核处理器上多线程程序的并行性能。本文将深入探讨GIL的工作原理及其对Python多线程编程的影响。 ... [详细]
  • 如何利用Java 5 Executor框架高效构建和管理线程池
    Java 5 引入了 Executor 框架,为开发人员提供了一种高效管理和构建线程池的方法。该框架通过将任务提交与任务执行分离,简化了多线程编程的复杂性。利用 Executor 框架,开发人员可以更灵活地控制线程的创建、分配和管理,从而提高服务器端应用的性能和响应能力。此外,该框架还提供了多种线程池实现,如固定线程池、缓存线程池和单线程池,以适应不同的应用场景和需求。 ... [详细]
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社区 版权所有