《算法的乐趣》7.稳定匹配与舞伴问题------python

本文主要是介绍《算法的乐趣》7.稳定匹配与舞伴问题------python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - 稳定匹配问题
  - - 概念
    - Gale-Shapley稳定匹配算法:
    - 舞伴问题
    - 穷举所有完美匹配结果
    - 完美匹配中去除不稳定因素
  - 二部图与二分匹配
  - - 概念
    - 最大流(maximalflow)算法或匈牙利(Hungarian algorithm)算法:

稳定匹配问题

假设 $n$ 个未婚男人的集合 $M={m_{1},m_{2},…,m_{n}}$ 和 $n$ 个未婚女人的集合 $W={w_{1},w_{2},…,w_{n}}$ ,令 $M \times W$ 为所有可能的形如 $m_{i},w_{i})$ 的有序对的集合，其中 $m_{i}\in M,w_{i}\in W$ .

概念

匹配: $S$ 是来自 $M \times W$ 的有序对的集合，并且具有以下性质：每个 $M$ 的成员和每个 $W$ 的成员至多出现在 $S$ 的一个有序对中。
完美匹配: $S^{'}$ 是一个具有以下性质的匹配： $M$ 的每个成员和 $W$ 的每个成员恰好出现在 $S^{'}$ 的一个对里。

$S$ 和 $S^{'}$ 这两个定义的差别就是“至多”和“恰好”两个词，可以将 $S$ 理解为 $M$ 和 $W$ 的成员配对结婚，但是 $M$ 和 $W$ 中不一定所有成员都能配对成功，还有剩余的男人和女人是单身。而完美匹配 $S^{'}$ 则是 $S$ 的一种特殊情况，即 $S^{'}$ 是所有人都配对成功，不存在落单的男人和女人。

在完美匹配的背景下引入优先或偏好的概念，每个男人都按照个人喜好对所有女人排名，如果某个男人 $m$ 给女人 $w$ 的排名高于给 $w^{'}$ 的排名，就可以理解为 $m$ 喜欢 $w$ 胜过 $w^{'}$ .反过来也一样，每个女人也按照自己的喜好对所有的男人排名。以上排名必须区分先后顺序，不能有排名并列的情况出现。

稳定匹配就是在引入优先排名的情况下，一个完美匹配 $S$ 如果不存在不稳定因素，则称这个完美匹配是稳定匹配。

不稳定因素:假设在完美匹配 $S$ 中存在两个配对 $(m, w)$ 和 $(m^{'}, w^{'})$ ,但是从优先排名上看， $m$ 更喜欢 $w^{'}$ 而不喜欢 $w$ ，同时 $w^{'}$ 也更喜欢 $m$ 而不喜欢 $m^{'}$ ,在这种情况下，我们称这个完美匹配S是不稳定的，像 $(m, w^{'})$ 这样有“私奔”倾向的不稳定对（unstable pair）就是 $S$ 的一个不稳定因素。

稳定匹配满足两个条件：首先，它是一个完美匹配；其次，它不含有任何不稳定因素。

Gale-Shapley稳定匹配算法:

对每一个单身男在其所有尚未拒绝他的女士中选择一位排名最优先的女士；
女士有三种状态：没被选择，一个选择，多个选择；
一个选择：两人绑定，
多个选择：每一位女士将正在追求她的单身男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若单身男优于当前男友，则抛弃当前男友；否则保留当前男友，拒绝单身男。若某男士被其女友抛弃，重新变成单身男。
循环。直到全部组合

舞伴问题

from collections import deque## 初始化
boys = ["Albert", "Brad", "Chuck"]
girls = ["Laura", "Marcy", "Nancy"]
# 偏爱列表
sort_boy_to_girl = [[1, 3, 2], [3, 1, 2], [1, 2, 3]]
sort_girl_to_boy = [[2, 3, 1], [1, 3, 2], [2, 1, 3]]def find_free_partner(boys, girls, sort_boy_to_girl, sort_girl_to_boy):# 当前选择的舞伴current_boys = {boys[0]:None, boys[1]:None, boys[2]:None}current_girls = {girls[0]:None, girls[1]:None, girls[2]:None}count = len(boys)# 建立队列，男孩下一次选择的女孩next_select = {}for i in range(count):next_select[boys[i]] = deque()argsort_p = sorted(range(count), key=lambda k: sort_boy_to_girl[i][k])for j in range(count):next_select[boys[i]].append(girls[argsort_p[j]])# 女孩选择男孩字典sort_girl = {}for i in range(count):sort_girl[girls[i]] = {}for j in range(count):sort_girl[girls[i]][boys[j]] = sort_girl_to_boy[i][j]while None in current_boys.values():for i in range(count):bid = boys[i]if current_boys[bid]:# 男孩有对象，跳过continueelse:# 优先选择的女孩select = next_select[bid][0]if current_girls[select] == None:# 女孩没对象，两者结合current_boys[bid] = selectcurrent_girls[select] = bidnext_select[bid].popleft()else:# 和女孩的对象好感度对比if sort_girl[select][current_girls[select]] < sort_girl[select][bid]:next_select[bid].popleft()else:current_boys[current_girls[select]] = Nonecurrent_boys[bid] = selectcurrent_girls[select] = bidnext_select[bid].popleft()return current_boys

print(find_free_partner(boys, girls, sort_boy_to_girl, sort_girl_to_boy))

{'Albert': 'Nancy', 'Brad': 'Marcy', 'Chuck': 'Laura'}

穷举所有完美匹配结果

首先穷举完所有的完美匹配；
然后从中去除掉含有不稳定因素的项。

# 穷举
# 书中采用递归实现全排列的方式
## 初始化
boys = ["Albert", "Brad", "Chuck"]
girls = ["Laura", "Marcy", "Nancy"]
# 偏爱列表
sort_boy_to_girl = [[1, 3, 2], [3, 1, 2], [1, 2, 3]]
sort_girl_to_boy = [[2, 3, 1], [1, 3, 2], [2, 1, 3]]current_boys = {boys[0]:None, boys[1]:None, boys[2]:None}
current_girls = {girls[0]:None, girls[1]:None, girls[2]:None}all_select = []
count = 0
def perm(girls, begin, end):global countif begin >= end:current_boys = {boys[0]:girls[0], boys[1]:girls[1], boys[2]:girls[2]}all_select.append(current_boys)count += 1else:i = beginfor num in range(begin, end):girls[num], girls[i] = girls[i], girls[num]perm(girls, begin+1, end)girls[num], girls[i] = girls[i], girls[num]return all_select

all_select = perm(girls, 0, len(girls))
print(all_select)

[{'Albert': 'Laura', 'Brad': 'Marcy', 'Chuck': 'Nancy'}, {'Albert': 'Laura', 'Brad': 'Nancy', 'Chuck': 'Marcy'}, {'Albert': 'Marcy', 'Brad': 'Laura', 'Chuck': 'Nancy'}, {'Albert': 'Marcy', 'Brad': 'Nancy', 'Chuck': 'Laura'}, {'Albert': 'Nancy', 'Brad': 'Marcy', 'Chuck': 'Laura'}, {'Albert': 'Nancy', 'Brad': 'Laura', 'Chuck': 'Marcy'}]

完美匹配中去除不稳定因素

### 去除不稳定因素# 男孩选择女孩字典
count = len(boys)
sort_boy = {}
for i in range(count):sort_boy[boys[i]] = {}for j in range(count):sort_boy[boys[i]][girls[j]] = sort_boy_to_girl[i][j]# 女孩选择男孩字典
sort_girl = {}
for i in range(count):sort_girl[girls[i]] = {}for j in range(count):sort_girl[girls[i]][boys[j]] = sort_girl_to_boy[i][j]def remove_unstable_factors(all_select):global sort_boy, sort_girla = 0stable = []for select in all_select:judge_girl = []for boy, girl in select.items():if sort_boy[boy][girl] == 1:judge_girl.append(girl)a += 1else:for i in range(sort_boy[boy][girl]-1):ju_girl = list(sort_boy[boy].keys())[list(sort_boy[boy].values()).index(i+1)]if ju_girl in judge_girl:ju_boy = list(select.keys())[list(select.values()).index(ju_girl)]if sort_girl[ju_girl][ju_boy] > sort_girl[ju_girl][boy]:a = -1000000else:a += 1if a > 0:  stable.append(select)a = 0return stableprint(remove_unstable_factors(all_select))

[{'Albert': 'Marcy', 'Brad': 'Nancy', 'Chuck': 'Laura'}, {'Albert': 'Nancy', 'Brad': 'Marcy', 'Chuck': 'Laura'}]

二部图与二分匹配

概念

二部图 $G = (V, E)$ 它的顶点集合 $V$ 可以划分为 $X$ 和 $Y$ 两个集合，它的边集合 $E$ 中的每条边都有一个端点在 $X$ 集合，另一个端点在 $Y$ 集合。
二部图的匹配：给定一个二部图 $G = (V, E)$ 的子图 $M$ ,如果 $M$ 的边集中任意两条边都不依附于同一个顶点，则称 $M$ 是一个匹配。
最大匹配：如果 $G$ 的一系列子图 $M_{0},M_{2},...M_{n}$ 都是匹配，那么包含边数最多的那个匹配就是图 $G$ 的最大匹配。
完美匹配：如果一个最大匹配中所有的点都有边与之相连，没有未覆盖点，则这个最大匹配就是完美匹配。
当二部图中两个顶点集合中的顶点个数相等时，这个最大匹配同时也是完美匹配。