稳定匹配算法及其栈优化

?

目录

一、稳定匹配算法

1、问题描述

2、稳定匹配算法的解决思路：

3、解题描述：

4、代码实现：

二、栈优化

1、数据结构——栈

2、优化过程描述：

3、代码实现：

三、性能分析

1、时间复杂度：

2、空间复杂度：

---

一、稳定匹配算法

1、问题描述

????????设有两个集合，集合M包含n个男性，集合W包含n个女性。每个男性有一个关于女性的偏好排名，同样地，每个女性也有一个关于男性的偏好排名。需要找到一个匹配方式，使得没有一对男女会愿意抛弃各自的当前匹配对象去与对方配对。

2、稳定匹配算法的解决思路：

1. 男生向还未拒绝其的女生中选出优先级最高的，并向其求婚
2. 女生如果没有已经被优先级更高的男生求婚，则答应（女生以后可以反悔）。 如果反之，则拒绝
3. 对此步骤进行loop，直到没有求婚发生

3、解题描述：

????????以男方主动视角：
设boys矩阵为男生的喜欢情况，girls矩阵为女生喜欢情况，数组matching为在女生视角下的匹配情况，初始值为-1，变量yes为已经成功匹配的男生人数初始为0。stable数组表示男生目前匹配对象的好感度排名,初始值都为0
① 初始化：数组matching初始值全为-1，数组stable初始值全为0，，变量yes为0
② i = yes+1,j = stable[i]
③ 通过男生i的好感度列表boys[i-1]匹配boys[i-1][j],并令k=boys[i-1][j]，即女生k
④ 查看女生k的目前匹配对象match[k-1]，定义其为i0。
⑤ 若i0为-1，则yes++，matching[k] = i,stable[i] = j；回到第二步；若Yes等于男生总人数则结束，反之i=yes+1；反之则进入下一步
⑥ 导入女生k的好感度列表girls[k-1]，对比其对男生i与男生[i0]的好感，如果男生i好感度更靠前，则男生i得以上位，令stable[i] = j,j = stable[i0] + 1,i = i0；反之，j++，即男生i匹配他的下一个，并回到第三步
⑦ 返回匹配列表

4、代码实现：

def stable_matching(boys, girls):
????# 初始化、第一步
????n = len(boys)
????matching = [-1] * n
????stable = [0] * n
????yes = 0

????# 第二步
????while(yes < n):
????????i = yes + 1
????????j = 0
????????while j < n:
????????????# 第三步
????????????k = boys[i-1][j]
????????????# 第四步
????????????i0 = matching[k-1]
????????????# 第六步
????????????if i0 != -1: ?# 如果已经有配对了
????????????????if girls[k-1].index(i) < girls[k-1].index(i0): ?

# 如果男生i的好感度更高
????# 换i上位，并存储男生i的匹配信息、将男生i0的信息调取出来继续匹配
????????????????????stable[i-1] = j
????????????????????matching[k-1] = i
????????????????????j = stable[i0-1] + 1
????????????????????i = i0
????????????????else: ?# 反之男生i继续匹配
????????????????????j += 1
????????????# 第五步
????????????else:
????????????????yes += 1
????????????????matching[k-1] = i
????????????????stable[i-1] = j
????????????????break
????return matching


boys = [[1, 2, 3], [3, 1, 2], [3, 1, 2]]
girls = [[1, 2, 3], [2, 3, 1], [1, 2, 3]]
print(stable_matching(boys, girls))

二、栈优化

????????稳定匹配的过程中，存在大量出栈入栈操作，通过栈优化可以大大降低程序的时空复杂度。

1、数据结构——栈

# 定义一个栈
class Stack:
????def __init__(self):
????????self.items = []
????# 清空
????def is_empty(self):
????????return self.items == []
????# 入栈
????def push(self, item):
????????self.items.append(item)
????# 出栈
????def pop(self):
????????if not self.is_empty():
????????????return self.items.pop()
????# 查看、但是不取出
????def peek(self):
????????if not self.is_empty():
????????????return self.items[-1]
????????else:
????????????return -1
????# 栈大小
????def size(self):
????????return len(self.items)

2、优化过程描述：

????????稳定匹配算法的栈优化方法
设boys矩阵为男生的喜欢情况，girls矩阵为女生喜欢情况，数组栈matching为在女生视角下的匹配情况，初始为空，变量yes为已经成功匹配的男生人数初始为0，数组栈stack_boys存储男生的喜欢栈
① 初始化：数组matching初始全为空，变量yes为0

② i = yes+1，若Yes等于男生总人数则结束，反之i=yes+1
③ 导入男生i的的好感栈stack_boys[i-1]，出栈元素push,并令k=boys[i-1].push，即女生k
④ 查看女生k的目前匹配对象match[k-1]，定义其为i0 = match[i-1].peek。
⑤ 若i0为-1，则yes++，将男生i压入栈，回到第二步；反之则进入下一步
⑥ 导入女生k的好感度列表girls[k-1]，对比其对男生i与男生i0的好感，如果男生i好感度更靠前，则男生i压入栈，i = i0；回到第三步

3、代码实现：

def stable_matching(boys, girls):
????n = len(boys)
????# 创建两个栈，分别存储男生和女生的偏好列表
????stack_boys = [Stack() for _ in range(n)]
????matching = [Stack() for _ in range(n)]
????yes = 0
????for i in range(n):
????????for j in range(n):
????????????stack_boys[i].push(boys[i][n - j -1])

????while yes < n:
????????i = yes + 1
????????while 1:
????????????# 第三步
????????????k = stack_boys[i - 1].pop()
????????????# 第四步
????????????i0 = matching[k - 1].peek()
????????????# 第六步
????????????if i0 != -1: ?# 如果已经有配对了
????????????????if girls[k - 1].index(i) < girls[k - 1].index(i0): ?# 如果男生i的好感度更高
?# 换i上位，并存储男生i的匹配信息、将男生i0的信息调取出来继续匹配
????????????????????matching[k - 1].push(i)
????????????????????i = i0
????????????# 第五步
????????????else:
????????????????yes += 1
????????????????matching[k - 1].push(i)
????????????????break

????matches = [0] * n
????for j in range(n):
????????matches[j] = matching[j].peek()
????return matches

三、性能分析

1、时间复杂度：

未优化稳定匹配算法的时间复杂度：Q(n2)

优化后时间复杂度：Q(n)

2、空间复杂度：

未优化稳定匹配算法的空间复杂度：Q(2n2+3n)

优化后空间复杂度：Q(2n2+n)