GS 稳定匹配算法 Java实现

时间：2022-02-23 00:35:02

算法描述

给定n个男人，n个女人，每个男人都有一张对所有女人的偏爱表，每个女人都有一张对所有的男人的偏爱表，要求设计一算法，产生一稳定匹配。

匹配过程

初始化所有的男人和女人都是*的
while （存在男人m是*的且还没对每个女人都求过婚）
    选择这样一个男人m
    令w是m的优先表中m还没求过婚的最高排名的女人
if w是*的
            (m,v)变成约会状态
else w当前与m’约会
if w更爱m’（对比m）
                m保持*
else w更爱m （对比m’）
                (m,v)变成约会状态
                m’变成*
endif
endif

Java代码实现如下

GS类

import java.util.Arrays;

public class GS {

static int num = 4;

static Woman women[] = new Woman[num];
static Man men[] = new Man[num];

public static void main(String[] args) {

// 男女优先表
int menArray[][] = { { 2, 3, 1, 0 }, { 2, 1, 3, 0 }, { 0, 2, 3, 1 }, { 1, 3, 2, 0 } };
int womenArray[][] = { { 0, 3, 2, 1 }, { 0, 1, 2, 3 }, { 0, 2, 3, 1 }, { 1, 0, 3, 2 } };

        System.out.println("男生的优先表");
for (int i = 0; i < num; i++) {
            Man m = new Man();
int a[] = {0,0,0,0};
for(int j=0; j<num; j++)
                a[j]=menArray[i][j];
            System.out.println(Arrays.toString(a));
            m.setRank(a);
            m.setId(i);
            men[i] = m;
        }

        System.out.println("女生的优先表");
for (int i = 0; i < num; i++) {
            Woman w = new Woman();
int a[] = {0,0,0,0};
for(int j=0; j<num; j++)
                a[j]=womenArray[i][j];
            System.out.println(Arrays.toString(a));
            w.setRank(a);   
            w.setId(i);
            women [i]= w;
        }
        System.out.println("——————————————————");

        Man theMan = null;
while ((theMan = findMan(men)) != null) {           
            pursue(theMan, women);
for (int i = 0; i < num; i++) {
                System.out.println("男生" + i + "&" + "女生" + men[i].getPresent());
            }
            System.out.println("——————————————————");
        }
        System.out.println("GS finished");
    }

static Man findMan(Man[] men) {
for (int i = 0; i < men.length; i++) {
if (!men[i].isDate()) {
                System.out.println("单身男生" + i);
return men[i];
            }
        }
        System.out.println("没有单身男生");
return null;
    }

static void pursue(Man m, Woman[] women) {
        Woman w = women[m.rank[m.getBetter()]];
        System.out.println("想追女生" + w.getId());
if (!w.isDate()) {
            System.out.println("女生没有对象");
            date(m, w);
            System.out.println("在一起");
        } else {
            System.out.println("女生有对象");
if (pk(m, w)) {
                System.out.println("换男友");
                date(m, w);
            } else {
                System.out.println("不换男友");
                m.setBetter(m.getBetter() + 1);
            }
        }
    }

static void date(Man m, Woman w) {
if (!w.isDate()) {
            m.setDate(true);
            m.setPresent(w.getId());
            w.setDate(true);
            w.setPresent(m.getId());
        } else {
            m.setDate(true);
            m.setPresent(w.getId());
            men[w.getPresent()].setDate(false);
            men[w.getPresent()].setPresent(100);
            w.setPresent(m.getId());
        }
    }

static boolean pk(Man m, Woman w) {
        System.out.println("优先表"+Arrays.toString(w.getRank()));
int former = 100;
for (int i = 0; i < num; i++) {
if (w.getRank()[i] == w.getPresent()) {
                former = i;
break;
            }
        }
int later = 100;
for (int i = 0; i < num; i++) {
if (w.getRank()[i] == m.getId()) {
                later = i;
break;
            }
        }
        System.out.println("前任排行" + former + " vs 挑战者排行" + later);
if (later < former) {
return true;
        } else {
return false;
        }
    }
}

Man类


public class Man {

private int id;
private int better = 0; // 追求过几位女生
int[] rank = {0,0,0,0};
private boolean date = false;
private int present = 100;

public int getId() {
return id;
    }

public void setId(int id) {
this.id = id;
    }

public int getBetter() {
return better;
    }

public void setBetter(int better) {
this.better = better;
    }

public int[] getRank() {
return rank;
    }

public void setRank(int[] rank) {
this.rank = rank;
    }

public boolean isDate() {
return date;
    }

public void setDate(boolean date) {
this.date = date;
    }

public int getPresent() {
return present;
    }

public void setPresent(int present) {
this.present = present;
    }

}

Woman类


public class Woman {
private int id;
int[] rank = {0,0,0,0};
private boolean date = false;
private int present = 100;

public int getId() {
return id;
    }

public void setId(int id) {
this.id = id;
    }

public int[] getRank() {
return rank;
    }

public void setRank(int[] rank) {
this.rank = rank;
    }

public boolean isDate() {
return date;
    }

public void setDate(boolean date) {
this.date = date;
    }

public int getPresent() {
return present;
    }

public void setPresent(int present) {
this.present = present;
    }
}

运行结果如下

男生的优先表
[2, 3, 1, 0]
[2, 1, 3, 0]
[0, 2, 3, 1]
[1, 3, 2, 0]
女生的优先表
[0, 3, 2, 1]
[0, 1, 2, 3]
[0, 2, 3, 1]
[1, 0, 3, 2]
——————————————————
单身男生0
想追女生2
女生没有对象
在一起
男生0&女生2
男生1&女生100
男生2&女生100
男生3&女生100
——————————————————
单身男生1
想追女生2
女生有对象
优先表[0, 2, 3, 1]
前任排行0  vs  挑战者排行3
不换男友
男生0&女生2
男生1&女生100
男生2&女生100
男生3&女生100
——————————————————
单身男生1
想追女生1
女生没有对象
在一起
男生0&女生2
男生1&女生1
男生2&女生100
男生3&女生100
——————————————————
单身男生2
想追女生0
女生没有对象
在一起
男生0&女生2
男生1&女生1
男生2&女生0
男生3&女生100
——————————————————
单身男生3
想追女生1
女生有对象
优先表[0, 1, 2, 3]
前任排行1  vs  挑战者排行3
不换男友
男生0&女生2
男生1&女生1
男生2&女生0
男生3&女生100
——————————————————
单身男生3
想追女生3
女生没有对象
在一起
男生0&女生2
男生1&女生1
男生2&女生0
男生3&女生3
——————————————————
没有单身男生
GS finished

更多细节请参考：
http://download.csdn.net/detail/qq_32962727/9766885
标签：

相关文章