java - Gale-Shapley 算法

Question

我想编写一个程序，将 n 个男人 [0,1,2,...,n-1] 匹配到 n 个女人 [0,1, 2,...,n-1] 根据自己的喜好。这些偏好由 n x n 矩阵表示，一个用于男性，一个用于女性。

            [ 0 2 1 ]
  E.g. men: [ 1 0 2 ]. The rows represent each man from 0 to 2, and per row we see a man's 'top 3'.
            [ 1 2 0 ]
  In this example: man 0 prefers woman 0 over woman 2; woman 1 is both man1's and man2's most prefered partner.

现在，我想确保匹配尽可能理想。这可以通过使用 Gale-Shapley 算法来完成。

我有两个问题:

• 假设 m0 和 m1 都将 w0 作为他们的首选。然后，我们必须查看 w0 的偏好:假设 m0 排名较高，则 (m0,w0) 是一个(临时)匹配。接下来我该怎么办？我是先将 m2 匹配到他的第一个选择，还是——因为 m1 仍然空闲——我将 m1 匹配到他的第二个选择？

• 我已经实现了一个如下所示的算法:

基本上，输入由男性和女性的偏好矩阵组成。结果应该是一个类似 res = [2,0,1] 的数组，这意味着男人 2 与女人 0 匹配，m0 与 w1 匹配，m1 与 w2 匹配。

    public int[] match(int[][] men, int[][] women) {

    int n = men.length;
    boolean[] menFree = new boolean[n];
    Arrays.fill(menFree, true);
    int[] res = new int[n];
    Arrays.fill(res, -1);
    int free = n;
    int m = 0;
    while (free > 0 && m<n) { 
        for (int i = 0; i < n; i++) {
            if(menFree[i]){
                int w = men[i][m];
                if(res[w]==-1){
                    res[w]=i;
                    menFree[i]=false;
                    free--;
                } else {
                    int c = res[w];
                    int colI = 0;
                    int colC = 0;
                    for(int j=0;j<n;j++){ 
                        if(women[w][j]==i){
                            colI = j;
                        } else if(women[w][j]==c){
                            colC = j;
                        }
                    }
                    if(colI<colC){
                        res[w]=i;
                        menFree[c]=true;
                        menFree[i]=false;
                    } else {
                        //do nothing or change column here, depending on answer to my first question.
                    }
                }
            }
        }
        m++; 
    }
    return res;
    }

如您所见，当一个人(=M 的)竞争对手的位置高于 M 自己的位置时，我不确定如何处理 else 部分。另外，如果事实证明我应该在那个时候寻找 M 的第二顺位，我该怎么做？还是有可能要回到M之后男主的第一顺位。

谢谢你帮助我。

Answer 1

我读了wiki .而且我自己实现了。我觉得我明白了，但是我的程序并不漂亮。仅供交流。

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class GaleShapley {

    public static void main(String[] args) {
        int[][] men = {{1, 2, 0}, {0, 1, 2}, {2, 1, 0}};
        int[][] women = {{1, 2, 0}, {0, 1, 2}, {2, 1, 0}};
        int[] res = match(men, women);
        for (int i : res)
            System.out.println(i);
    }

    static int[] match(int[][] men, int[][] women) {
        Map<Integer, Integer> temp = new HashMap<>();
        int size = men.length;
        boolean[] menFree = new boolean[size];
        boolean[] womenFree = new boolean[size];
        Arrays.fill(menFree, true);
        Arrays.fill(womenFree, true);
        ArrayList<Integer> stillFree = new ArrayList<>();

        while (stillFree.size() + temp.size() < size) {
            for (int i = 0, j = 0; i < size; i++, j = 0) {
                if (menFree[i]) {
                    for (; j < size; j++) {
                        //if the woman is free,make them a pair
                        if (womenFree[men[i][j]]) {
                            // make woman and man i pair, the woman's index is men[i][j]
                            temp.put(men[i][j], i);
                            menFree[i] = false;
                            womenFree[men[i][j]] = false;
                            break;
                        } else {
                            // the woman is not free,check her pair is whether stable
                            int pairMan = temp.get(men[i][j]);
                            boolean stable = checkStable(pairMan, i, men[i][j], women);
                            // not stable break them and make new pair
                            if (!stable) {
                                temp.put(men[i][j], i);
                                menFree[i] = false;
                                menFree[pairMan] = true;
                                break;
                            }
                        }
                    }
                    // if man i is still free , it means that he can't find a woman
                    if (menFree[i])
                        stillFree.add(i);
                }
            }
        }
        int[] stablePair = new int[2 * temp.size()];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : temp.entrySet()) {
            stablePair[i] = entry.getValue();
            i++;
            stablePair[i] = entry.getKey();
            i++;
        }
        return stablePair;
    }

    static boolean checkStable(int pairMan, int currentMan, int woman, int[][] women) {
        // index of pairMan and currentMan
        int p = 0, c = 0;
        for (int i = 0; i < women.length; i++) {
            if (women[woman][i] == pairMan)
                p = i;
            else if (women[woman][i] == currentMan)
                c = i;
        }
        // p<c : the woman love p more than c, they are stable
        return p < c;
    }
}