2025年GS 稳定匹配算法 Java实现

GS 稳定匹配算法 Java实现算法描述 给定 n 个男人 n 个女人 每个男人都有一张对所有女人的偏爱表 每个女人都有一张对所有的男人的偏爱表 要求设计一算法 产生一稳定匹配 匹配过程 初始化所有的男人和女人都是自由的 while 存在男人 m 是自由的且还没对每个女人都求过婚

大家好,我是讯享网,很高兴认识大家。

算法描述

给定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 
小讯
上一篇 2025-02-07 07:03
下一篇 2025-02-11 23:08

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/112400.html