稳定匹配算法及其栈优化

发布时间:2023年12月17日

?

目录

一、稳定匹配算法

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)

文章来源:https://blog.csdn.net/qq_48843954/article/details/135000745
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。