算法怎么玩(一): 从直男到渣男

前言

文章内容取自http://www.cs.cmu.edu/~arielpro/15896s16/slides/896s16-16.pdf并有所修改, 如有侵权等问题, 请提示删除(手动感谢). 这次主要是开个系列分享分享有趣的算法.


稳定匹配(The Stable Matching Problem)

不稳定对(Unstable pair)

如果:

  • 男生x相比现有配对更喜欢女生y
  • 女生y相比现有配对更喜欢男生x

这就是一个不稳定对, 很好理解吧. 那么稳定匹配就是不存在不稳定对的匹配. 举个小栗子, 现在给出联谊上3男3女的喜欢表, 提什么男男/女女的, 一对多的, 麻烦关闭页面(手动无奈).

男生\喜欢

1st

2nd

3rd

X

A

B

C

Y

B

A

C

Z

A

B

C

女生\喜欢

1st

2nd

3rd

A

Y

X

Z

B

X

Y

Z

C

X

Y

Z

这里我们尝试给出一个解, 看是不是稳定匹配. X-C, Y-B, Z-A. 很明显, X, A, B是可能出事情的. 如果X-A, 就出事了, 因为A比起现在匹配的Z更喜欢X; 同理, X-B也出事了, B可是最喜欢X的. 那么GG, 红线崩了.

男生\喜欢

1st

2nd

3rd

X

A

B

C

Y

B

A

C

Z

A

B

C

女生\喜欢

1st

2nd

3rd

A

Y

X

Z

B

X

Y

Z

C

X

Y

Z

X-A, Y-B, Z-C如何呢? 发现是稳定的, 因为A, B都最不喜欢Z.

男生\喜欢

1st

2nd

3rd

X

A

B

C

Y

B

A

C

Z

A

B

C

女生\喜欢

1st

2nd

3rd

A

Y

X

Z

B

X

Y

Z

C

X

Y

Z

但是不是每次都这么好运能找到稳定匹配的, 所以需要算法帮助解决问题.


Propose-And-Reject Algorithm

Propose-And-Reject Algorithm(Gale-Shapley 1962)可以解决问题. 贴一下伪代码, 这个算法原本是解决求婚问题的, 但是当成联谊看比较合适, 哪有人日常换未婚夫的(手动滑稽).

Initialize each person to be free.
while (some man is free and hasn't proposed to every woman) {
    Choose such a man m
    w = 1st woman on m's list to whom m has not yet proposed
    if (w is free)
        assign m and w to be engaged
    else if (w prefers m to her fiancé m')
        assign m and w to be engaged, and m' to be free
    else
        w rejects m
}

那么上面那一题就很快得出答案了, 就是我给的稳定匹配. 但是需要证明一下, 当然我引用的文献证明, 我的证明能力就很佛系了.

  • 完整性证明

全部男女都找到了另一半

  • 假设Z凉凉, 没有匹配.
  • 那么由于一对一的限制, 某个妹子A也没人爱. 换句话说, 没人向A表白.
  • 但是Z必须要向全部妹子表白才结束循环.
  • 所以反证成功.
  • 稳定性证明

没有不稳定对

  • 假设A-Z不稳定, 要搞事.
  • 情况1: Z没有向A表白
  • 说明Z更喜欢现有伴侣而不是A.
  • A-Z稳定.
  • 情况2: Z有向A表白
  • A拒绝了Z(立刻或者之后甩了).
  • 那说明A更喜欢现有伴侣.
  • A-Z稳定.
  • 反证成功.

最后

想要代码实现你要加上数据结构, 复杂度是n的平方, 毕竟程序 = 数据结构 + 算法. 然后的话, 所以想要获得幸福, 要主动出击以及保持好形象(手动捂脸). 还有还有, 我不是标题党哈, 你试试跑个10男10女的匹配, 这个算法绝对渣出天际. 喜欢记得点赞, 有意见或者建议评论区见~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaQ

和大牛之间的差距

上班的途中看了网络大V的一篇关于差距是如何产生的文章,略有小感。 文章的大意是差距是因为勤奋而导致的,无论先天和后天条件如何,只要足够勤奋都可以和别人产生差距。...

3515
来自专栏Python中文社区

十本书教你从Pythoner通往Pythonista

1、Python基础教程 本书是经典教程的全新改版,作者根据Python 3.0版本的种种变化,全面改写了书中内容,做到既能“瞻前”也能“顾后”。本书层次鲜明、...

41710
来自专栏程序员互动联盟

为什么这么多人惧怕C++?

C++在诞生之处,赢得了很多了口碑,但是随着编程大众化,以及编程语言的简单化趋势的发展,这门语言很多的弊端表现的越来越明显,特别让初学者选择c++作为初级入门语...

3329
来自专栏Python小屋

Python教学与学习过程中应注意的九句话

1、Python是以快速解决问题为出发点的,不建议把太多时间花费在底层语言细节上,例如内存分配与管理,千万别像教/学C语言一样教/学Python。

1004
来自专栏blackheart的专栏

[程序设计语言]-00:目录

1. 开篇概览  前一周写了一篇博文“记-码农的“启蒙”之《程序设计语言-实践之路》和《面向对象分析和设计》两书”,其中说打算总结下这两本书中有哪些收获,就是关...

1945
来自专栏Java学习网

为什么程序员总是写糟糕的代码?这3个原因

我最近一直在想我们作为一个行业为什么总是产出糟糕代码的原因。 1.明显原因…… 我一下子想到的最明显的原因是,有好的程序员,也有不那么好的程序员,有的人技术水平...

3566
来自专栏函数式编程语言及工具

scala泛函编程是怎样被选中的

      现在计算机技术发展现象是:无论硬件技术如何发展都满足不了软件需求;无论处理器变得能跑多快,都无法满足软件对计算能力的需要。按照摩尔定律(Moore...

2077
来自专栏企鹅号快讯

零基础入门Python,值得推荐的几本书籍!

于我个人而言,我很喜欢Python,当然我也有很多的理由推荐你去学Python我只说两点.一是简单,二是写Python薪资高.我觉得这俩理由就够了,对不对.买本...

22510
来自专栏spring源码深度学习

业务开发工程师,你真的愿意做一辈子 CRUD boy 吗?

你是不是觉得数据结构和算法,跟操作系统、计算机网络一样,是脱离实际工作的知识?可能除了面试,这辈子也用不着?

1K1
来自专栏老九学堂

【拓展】Hello World你以为你知道?

Hello Wold你造(知道)么?我知道啊,不就是你好世界么。呵呵..... 今天我们来讲讲到底什么才是Hello World!!别在很傻很天真的说你好世界了...

3275

扫码关注云+社区