关于GS匹配算法（Gale_shaply)及想法

1.GS匹配算法

首先第一个问题。简单介绍一下GS匹配算法，Gale-Shapley匹配算法是基于“稳定婚姻”问题提出的。假设有n个男性和m个女性，每个男性都有自己的偏好列表，同样，每个女性也有自己的偏好列表。算法的目标是为这n对男女实现稳定匹配。

2.什么是稳定匹配

第二个问题就是什么是稳定匹配？

基于前面提到的n名男孩与m名女孩，每一名男孩对每一名女孩都有一个喜欢程度的评级，那么怎么处理这些男女匹配关系，使得经匹配后对任意a，b满足任一条件：

相对于b，a一定更喜欢当前跟他配对的女孩

相对于a，b一定更喜欢当前跟她配对的男孩

这时就是稳定匹配

那会不会出现不稳定匹配的情况呢？假设男女数量相等，n位男孩和n位女孩间，最大示爱次数是 n2−2n+2 如果某个女孩被示爱过，那么她就有了一个备选对象，且这个对象只会更换不会消失。这意味着，如果 n 位女孩都被示爱过，那么 n 位女孩都有一个备选对象，此时算法就结束了。所以，在算法的进行过程中，除了最后一步，都只有最多 n−1 位女孩被示爱过。

而这 n−1 位女孩最多拒绝过 (n−1)2 个人，因为n个男孩中一定有一个人是不会被拒绝的。算法每一步都至少要拒绝一个人，到目前为止，算法最多运行了 (n−1)2 步。还有最后一次没有拒绝而使得算法终止的示爱，一共是 (n−1)2+1=n2−2n+2 步。

3.算法具体实现

具体算法如何实现呢？

算法步骤

（1）初始化：所有人的状态均为单身。

（2）提议：每个单身男性向其偏好列表中的第一个女性表达爱意。

（3）响应：女性根据自身偏好，从示爱者中选择最满意的一个，若已有示爱者，则比较两者，保留更优的一个。

（4）更新状态：被拒绝的男性更新其偏好列表，继续向下一个女性示爱。

（5）重复步骤4，直到所有人均实现匹配。

4.python代码

下面是我写的代码，已经过测试：

class Person:
    def __init__(self, name):
        self.name = name
        self.preferences = []
        self.engaged_to = None 

    def prefer(self, person1, person2):
        # 确保person1和person2都是Person对象
        if not isinstance(person1, Person) or not isinstance(person2, Person):
            raise ValueError("Both arguments must be instances of the Person class.")
        return self.preferences.index(person1) < self.preferences.index(person2)

class Gale_shapley:
    def __init__(self, proposers, reviewers):
        self.proposers = proposers
        self.reviewers = reviewers
        self.matches = {reviewer: None for reviewer in reviewers}  # initialize

    def run(self):
        free_proposers = self.proposers[:]  
        
        while free_proposers:
            proposer = free_proposers[0]  
            for reviewer in proposer.preferences:
                if self.matches[reviewer] is None:
                    #若未婚，则'口头承诺'
                    self.matches[reviewer] = proposer
                    free_proposers.remove(proposer)
                    break
                else:
                    #若已婚，那就换呗,你总不能阻止我奔向更好的吧
                    current_partner = self.matches[reviewer]
                    if reviewer.prefer(proposer, current_partner):
                        self.matches[reviewer] = proposer  
                        free_proposers.remove(proposer)
                        free_proposers.append(current_partner)  
                        break
                       
        return self.matches

# 爱与被爱
proposers = [Person(f'male {i}') for i in range(4)]
reviewers = [Person(f'female {i}') for i in range(4)]

# 喜好排名
proposers[0].preferences = [reviewers[1], reviewers[2], reviewers[3], reviewers[0]]
proposers[1].preferences = [reviewers[2], reviewers[0], reviewers[1], reviewers[3]]
proposers[2].preferences = [reviewers[0], reviewers[3], reviewers[2], reviewers[1]]
proposers[3].preferences = [reviewers[3], reviewers[2], reviewers[0], reviewers[1]]

reviewers[0].preferences = [proposers[0], proposers[1], proposers[3], proposers[2]]
reviewers[1].preferences = [proposers[2], proposers[3], proposers[0], proposers[1]]
reviewers[2].preferences = [proposers[1], proposers[0], proposers[2], proposers[3]]
reviewers[3].preferences = [proposers[3], proposers[2], proposers[1], proposers[0]]

execute = Gale_shapley(proposers, reviewers)
matches = execute.run()

# 输出匹配结果
for reviewer, proposer in matches.items():
    print(f'{reviewer.name} is matched with {proposer.name}')

这是一个有趣的算法，因为我能从中得出一些结论和道理，哈哈

1.无论执行多少次，结果都是一样的，假设结果会出现变化，这就与稳定匹配相悖，两人间会出现背叛，呃

2.恋情中先主动的人有优势。该算法中假设都是男孩主动示爱，男孩获得了自己的最佳的伴侣，但是女孩都获得了自己的最差的伴侣，因为男孩可以根据自己的内心排序去选择，而女孩只能被动选择，而你，我的朋友，你根本不敢出击

3.所有人都能相互匹配，因为算法中的前提是人数有限，男女数量相等，双方正直专一

4.问题强调稳定匹配，不应强调爱情。什么时候爱情已经是充满选择与权衡？好吧，似乎就是这样，我很难相信人们描绘出的美好，但我仍为它们留有一丝幻想。

关于Gale-Shapley匹配算法有哪些应用呢？

1. 高等教育领域：用于学生与导师的匹配。高考呗
2. 医疗资源分配：医院与医生的匹配。西西
3. 企事业单位招聘：企业与求职者的匹配。
4. 网络广告投放：广告主与广告位的匹配。

结语

Gale-Shapley匹配算法作为一种经典的资源分配算法，具有公平、稳定的特点，在现实生活中具有广泛的应用价值。通过对算法原理的深入了解，可以更好地将其应用于实际场景，解决各种资源分配问题，为生活带来便利。