前言
最近看了一档综艺《心动的信号》(唉, 单身久了, 开始喜欢看别人谈恋爱了)
节目中共有n男n女, 他们会在节目的最后进行表白, 如果我喜欢你, 恰好你也喜欢我, 那么便就会在一起, 自此传为一段佳话.
于是, 我就在想, 如何用算法来实现这个匹配的过程呢?
单一匹配
将信息抽象化, 现有两个集合 M
N
, 每个集合中存在a个对象.
结果集 R
中元素为 (m, n)
, 其中 m ∈ M
, n ∈ N
, m 喜欢 n, n 也喜欢 m.
OK, 设计数据结果进行实现. (以下以Go进行简单演示)
package main
import "fmt"
type people struct {
Name string // 名字
LikePeople string // 喜欢的人名
}
type lovers struct {
Boy people
Girl people
}
func main() {
// 分别构造男女队列
boyArr := []people{
}
girlArr := []people{
}
// 分别对他们进行匹配
var result []lovers
for _, boy := range boyArr {
// 查看他喜欢的女孩是否喜欢他
for _, girl := range girlArr {
if boy.LikePeople == girl.Name {
// 两情相悦了
if girl.LikePeople == boy.Name {
result = append(result, lovers{
Boy: boy,
Girl: girl,
})
}
break
}
}
}
fmt.Println(result)
}
当然, 这就是简单的循环查找, 但是如果将喜欢的人, 从单个换成一个列表呢? 别说, 我后面找了一下, 还真有这么一个算法.
Gale-Shapley 算法
再来.现有两个集合 M
N
, 每个集合中分别存在a个对象. 匹配集 R
中的元素为: (m, n)
, 其中 m ∈ M
, n ∈ N
.
到这, 基本上和我们上面的匹配一致. Gale-Shapley
在此基础上, 提出了完美匹配和稳定匹配的概念.
完美匹配
完美匹配是指, M
和N
的每个成员, 都恰好出现在R
的一个匹配队列中. 恰好的意思是, 不多不少就一次.
说人话就是: M
和N
中的所有人都配对成功, 不存在落单的男孩或女孩.
稳定匹配
一个完美匹配中如果不存在不稳定因素, 就称为稳定匹配.
我们上面每个人只能喜欢一个人, 现在不是了, 每个人都有一个喜欢程度从高到低的列表.
如果说 m1
在 n1
n2
中更喜欢 n2
, 那么m1
的喜欢列表就是[n2, n1]
.
简单解释一下不稳定因素. 如果在结果集中, 存在这样的两个元素: (m1, n1)
, (m2, n2)
. 而m1
相较于n1
更喜欢n2
, 同时n2
相较于m2
也更喜欢m1
, 那么他俩就有私奔的可能. 这种可能就称为不稳定因素.
Gale-Shapley
算法, 就是从中得出一个稳定匹配的算法. 算法的思想通俗易懂, 一句话概括: 所有男生依次尝试想所有女生表白
算法的实现步骤如下:
- 找到一个还没有对象, 且未向所有女生表白的男生
m
- 找到一个
m
还没有表白过的女生n
- 如果
n
还没有对象, 则进行匹配 - 如果
n
有对象. 则判断n
的喜欢列表. 若更喜欢当前对象, 则保持不变, 若更喜欢m
则抛弃当前对象 - 直到
m
找到对象或向所有女生都表白过. 则回到第一步, 直到找不到这样的男生.
通过流程上来看, 这是一个时间复杂度O(n^2)
的算法. 借用Go
来简单实现一下:
package main
type people struct {
Name string // 名字
LikePeople []string // 喜好列表
CurrentLike int // 后面算法记录当前表白对象时使用
Friend string // 当前匹配对象
}
func main() {
// 分别构造男女队列
boyArr := []*people{
}
girlArr := []*people{
}
for true {
// 找到一个没有对象, 且未全部表白的男生
var searchBoy *people
for _, boy := range boyArr {
if boy.Friend != "" {
// 当前男孩已经有对象了
continue
}
// 男孩向所有女生表白过了
if boy.CurrentLike >= len(boy.LikePeople) {
continue
}
searchBoy = boy
break
}
if searchBoy == nil {
// 已经全部有对象了, 结束
break
}
// 男生向女生依次表白
var i int
for i := searchBoy.CurrentLike; i < len(searchBoy.LikePeople); i++ {
girlName := searchBoy.LikePeople[i]
// 找到这个女孩
girl := searchPeople(girlArr, girlName)
if girl == nil {
// 习惯了, 判下空
continue
}
if girl.Friend == "" {
// 若女孩没有对象, 则直接配对
girl.Friend = searchBoy.Name
searchBoy.Friend = girl.Name
break
} else {
// 若女孩有对象, 看下 girl 更喜欢谁
searchBoyIdx := searchNameIndex(girl.LikePeople, searchBoy.Name)
girlFriendIdx := searchNameIndex(girl.LikePeople, girl.Friend)
if girlFriendIdx < searchBoyIdx {
// 保持当前
continue
} else {
// 重新组队
girlFriend := searchPeople(boyArr, girl.Friend)
if girlFriend != nil {
// 分手了
girlFriend.Friend = ""
}
girl.Friend = searchBoy.Name
searchBoy.Friend = girl.Name
}
}
}
searchBoy.CurrentLike = i
}
}
func searchPeople(peopleArr []*people, name string) *people {
for _, people := range peopleArr {
if people.Name == name {
return people
}
}
return nil
}
func searchNameIndex(nameArr []string, name string) int {
for i, tmpName := range nameArr {
if tmpName == name {
return i
}
}
return -1
}
拢共也没有几行, 但是, 它可以保证完美匹配和稳定匹配么? 这简单的逻辑让我都有点不相信自己了, 不行, 得证明一下.
首先是完美匹配, 因为是进行的一对一匹配, 如果最终存在落单的女生, 那么就一定存在相同数量落单的男生. 同时, 因为在女生没有对象的时候, 会接收任意男生的表白, 可以得出落单的女生没有收到过任何男生的表白. 而在匹配的过程中, 男生会向喜欢列表中的所有女生依次进行表白, 得出落单的男生一定向所有女生进行过表白. 前后矛盾. 故不存在这样的情况. 因此结果为完美匹配.
那么结果是否是稳定匹配呢? 如果结果中存在不稳定因素, 既(m1, n1), (m2, n2)
, 其中m1
更喜欢n2
, 同时n2
也更喜欢m1
. 根据算法的规则, m1
会先向n2
表白, 此时, 如果n2
单身, 则会接受表白, 如果n2
已经接受了m2
的表白, 则会毅然决然的选择分手, 和m1
在一起. 即使后面n2
再次收到m2
的表白, 也不会和m1
进行分手. 故不存在这样的不稳定因素. 因此结果为稳定匹配.
算法优化
我们在最开始分析的时候, 时间复杂度是O(n^2)
, 现在再来看一下我们实现的时间复杂度. 上方算法共有一下几层循环:
- 找到没有对象且未全部表白的男生, n
- 向女生依次表白, n
- 找到表白的女生, n
- 若女生有对象, 则从女生的喜欢列表中, 找到这两个男孩. 2n
- 若重新组队, 则找到女生的当前对象, n
- 向女生依次表白, n
. 很显然, 大 O 时间复杂度为O(n^3)
. 哎? 怎么和之前分析的不一样呢? 很明显, 就差在了第三层. 只要想办法消掉就好啦.
- 找到要表白的女孩. 直接存储女孩的索引即可直接找到.
- 找到女生当前对象同理, 直接存储索引.
- 从女生的喜欢列表中, 找到更喜欢谁? 将数组换成 map, 即可实现
O(1)
的查找. 空间换时间呗.
至此, 第三层的循环全部去掉. 时间复杂度为O(n^2)
. 能不能再降低呢? 我还没有想到.
扩展
人数不匹配
如果男女生人数不一致呢? 那自然是无法得出完美匹配与稳定匹配了, 但是通过上面的步骤, 无论是让人数较少的一方主动选择, 还是人数较多的一方主动选择, 得出的还是一个比较满意的匹配结果. 当然, 因为人数不匹配, 最终是一定有落单的人.
喜欢列表不为全部
如果女生的喜欢列表, 只是部分男生呢? 那么对于未出现在喜欢列表的人有两种情况:
- 十分讨厌, 不能进行匹配
- 无所谓, 如果不能和我喜欢的人在一起, 那和谁都一样
对于这两种态度, 处理方式也自然不同.
如果不能进行匹配, 则匹配结果可能不是完美匹配, 因为你喜欢的已经和别人跑了, 而喜欢你的你又拒绝了.
如果是无所谓的态度, 处理流程基本上和上面一致. 比较是不存在的给出一个较大的默认值即可.
应用
那么这个算法可以应用到哪些场景呢? 想了一下, 关于这种意向匹配的场景, 基本上都可以参考此算法, 比如: 相亲、工作分配、大学招生、拍卖等等
别人看综艺, 想从中学到交友之法, 而我看到的却是算法? 或许, 破案了? 唉, 不说了, 刷剧去了.
今天的文章galeshapley算法_levenberg-marquardt 算法「建议收藏」分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/64256.html