婚姻匹配问题设计——基于 Gale - Shapley 算法

创作时间:

作者:

@小白创作中心

婚姻匹配问题设计——基于 Gale - Shapley 算法

引用

CSDN

https://m.blog.csdn.net/2301_80688700/article/details/143748449

婚姻匹配问题概述

问题描述：有N男N女，每个人都按照他对异性的喜欢程度排名。现在需要写出一个算法安排这N个男的、N个女的结婚，要求两个人的婚姻应该是稳定的。何为稳定？有两对夫妻M1 F2，M2 F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的，随时都可能发生M1和F1私奔或者M2和F2私奔的情况。所以在做出匹配选择的时候（也就是结婚的时候），我们需要做出稳定的选择，以防这种情况的发生。

要求：boys和girls各自给出自己心仪的嘉宾的顺序，请编写程序求出一种稳定的匹配，使匹配结果不会发生私奔现象。

Gale - Shapley 算法

2.1 Gale - Shapley 算法的背景

盖尔-沙普利(Gale-Shapley)稳定匹配算法是美国数学家 David Gale 和 Lloyd Shapley在1962年提出的一种寻找稳定婚姻的策略。

这种匹配方式的特点在于:不管需要匹配的总人数有多少、不管他们各自的偏好如何,只要男女人数相等,并且男女双方每个人都能在心中给对方打分,那么应用这种策略后总能得到一个稳定的婚姻搭配。

换句话说,他们证明了稳定的婚姻搭配总是存在的。并且这种策略反映了现实生活中的很多真实情况,也不仅仅局限于婚姻匹配。

算法代码实现和解析

下面这段代码实现了稳定婚姻匹配算法。它通过不断循环未匹配的男性，让他们向心仪的女性求婚。如果女性未匹配，则接受求婚；如果女性已匹配，则比较当前求婚男性和已匹配男性在她心中的排名，若当前男性排名更靠前，则更换匹配对象。最后，输出稳定的婚姻匹配结果。

步骤一：初始化

所有男性和女性都是未婚状态。

// 判断是否所有男性都已匹配
bool allMenMatched(int matches[]) {
    for (int i = 0; i < N; i++) {
        if (matches[i] == -1) {
            return false;
        }
    }
    return true;
}

步骤二：求婚阶段（男性求婚）

每一个未婚的男性会向他偏好列表中排名最高的女性求婚。因为每个男性都有自己的偏好排序，所以他会从最喜欢的女性开始追求。

例如，假设有男性 M1、M2、M3 和女性 W1、W2、W3。M1 的偏好顺序是 W1 > W2 > W3，那么 M1 会先向 W1 求婚。

// 找到男性的下一个心仪女性
int findNextPreference(int man, int preferences[][N], int current) {
    for (int i = 0; i < N; i++) {
        if (preferences[man][i] == current) {
            return i + 1;
        }
    }
    return -1;
}

步骤三：回应阶段（女性考虑求婚）

当女性收到求婚请求时，她会比较求婚者和她当前的未婚夫（如果有的话）。如果她更喜欢这个求婚者，她会接受求婚，并且她之前的未婚夫（如果有的话）就会变成未婚状态。

继续上面的例子，如果 W1 当前没有未婚夫，她会接受 M1 的求婚。但如果 W1 已经有未婚夫 M2，并且她更喜欢 M1，那么她会抛弃 M2，接受 M1 的求婚，M2 就变成未婚状态。

// 判断女性是否更喜欢当前男性而不是已匹配男性
bool doesWomanPreferCurrentMan(int woman, int man1, int man2, int preferences[][N]) {
    for (int i = 0; i < N; i++) {
        if (preferences[woman][i] == man1) {
            return false;
        }
        if (preferences[woman][i] == man2) {
            return true;
        }
    }
    return false;
}

步骤四：循环求婚 - 回应过程

未婚的男性会继续向他们偏好列表中剩下的女性求婚，这个过程会一直重复，直到所有的男性和女性都匹配成功。

例如，M2 被 W1 抛弃后，他会向自己偏好列表中的下一个女性（比如 W2）求婚。如果 W2 接受，那么 M2 和 W2 就匹配成功。这个过程会不断循环，直到所有男性和女性都有匹配的伴侣。

stableMarriage函数（核心函数）——函数特色

功能：实现整个稳定婚姻匹配的过程。
实现细节：
初始化阶段：首先定义了两个数组menMatches和womenMatches，分别用于存储男性和女性的匹配结果，初始时将这两个数组的所有元素都设置为 -1，表示所有人都未匹配。
匹配循环阶段：进入一个while循环，循环条件是通过allMenMatched函数判断是否所有男性都已匹配，只要还有男性未匹配，循环就会继续执行。在循环内部，有一个嵌套的for循环，用于遍历每个男性。对于每个未匹配的男性（通过判断menMatches[man] == -1），会再次进入一个内层的for循环，按照他的偏好顺序依次考虑女性。如果某个女性未匹配（通过判断womenMatches[woman] == -1），就直接将该男性和这个女性进行匹配，即更新menMatches[man]和womenMatches[woman]的值；如果女性已经匹配，就通过doesWomanPreferCurrentMan函数判断她是否更喜欢当前正在考虑的男性，如果是，就更新匹配结果，让当前男性和这个女性匹配，同时将原来匹配的男性（通过menMatches[currentMan] = -1）设置为未匹配状态。

void stableMarriage(int menPreferences[][N], int womenPreferences[][N]) {
    int menMatches[N];
    int womenMatches[N];
    for (int i = 0; i < N; i++) {
        menMatches[i] = -1;
        womenMatches[i] = -1;
    }
    while (!allMenMatched(menMatches)) {
        for (int man = 0; man < N; man++) {
            if (menMatches[man] == -1) {
                for (int i = 0; i < N; i++) {
                    int woman = menPreferences[man][i];
                    if (womenMatches[woman] == -1) {
                        menMatches[man] = woman;
                        womenMatches[woman] = man;
                        break;
                    } else {
                        int currentMan = womenMatches[woman];
                        if (doesWomanPreferCurrentMan(woman, man, currentMan, womenPreferences)) {
                            menMatches[man] = woman;
                            menMatches[currentMan] = -1;
                            break;
                        }
                    }
                }
            }
        }
    }
    printf("稳定的婚姻匹配结果：\n");
    for (int i = 0; i < N; i++) {
        printf("男人 %d 和女人 %d\n", i + 1, menMatches[i]);
    }
}