精华内容
下载资源
问答
  • 稳定匹配算法实验

    2017-03-01 10:09:46
    稳定匹配算法实验 包含经典题目及算法伪代码 详情参见我的博客
  • 婚姻稳定匹配问题

    2020-07-20 22:09:32
    婚姻稳定匹配问题 算法 GS稳定匹配算法 稳定婚姻匹配问题可以由GS稳定匹配算法(盖尔-沙普利算法)来解决。 GS稳定匹配算法也称作“延迟接受算法”,是美国数学家David Gale和Lloyd Shapley在1962年提出的寻找稳定...

    婚姻稳定匹配问题

    通过算法实现,有小小的设计以便程序更加有趣,与大家分享但是请大家尊重代码中的设计,如需转载请务必声明原创,谢谢。

    算法

    GS稳定匹配算法

    稳定婚姻匹配问题可以由GS稳定匹配算法(盖尔-沙普利算法)来解决。
    GS稳定匹配算法也称作“延迟接受算法”,是美国数学家David Gale和Lloyd Shapley在1962年提出的寻找稳定婚姻的一种方法。

    特点

    算法的特点在于,只要男士和女士人数相等,并且心中都有自己的排名情况,无论需要配对的总人数多少,都可以得到一个稳定的婚姻。

    问题描述

    婚介中心登记了N位男士与N位女士的信息,每位男士按照他对女士的喜爱程度做了排名,每位女士按照她对男士的喜爱程度做了排名。我们将男士和女士进行配对,使得最后每一对的婚姻都是稳定的。
    在这里插入图片描述
    稳定的含义

    稳定的含义:
    如果男生1更喜欢女生2,但是他和女生1结婚了。同时男生2更喜欢女生1,但是他和女生2结婚了,这样的婚姻是不稳定的,会出现男生1和女生2或男生2和女生1私奔的情况。

    主要步骤

    主要思路就是使男士先拥有主动权,优先追求心中排位第一的女士。
    在判断女士是否已经有对象之后,如果没有,女士就先接受男士,两人配对成功。如果该女士有对象就判断其现任与追求者在女士心中的排位,如果现任较高,则男士被拒绝需要再次追求心中排位第二的女士并重复以上过程。如果追求者排位较高,则女士和现任分手,与追求者配对。现任恢复单身并再次追求心中下一排位女士,同样重复以上过程。
    直至所有男士女士配对成功,循环结束,任务完成即已达到稳定匹配。

    #include <stdio.h> 
    #include <iostream>
    using namespace std;
    bool finish_or_not(int, int *);
    bool current_male_is_better(int num, int *male_rank_in_female, int current, int chasing);
    int main(){
    	printf("\n");
    	printf("┌——————幸福的开端——————-┐\n");
    	printf("     欢迎来到“量身定做”婚介中心\n"); 
    	printf("      千里姻缘一线牵,珍惜这段缘\n"); 
        printf("│                                   │\n");
        printf("└—————————————————-┘\n");
        printf("\n");
    	int num = 2;int i,j;
    	//有几对需要配对
    	printf("请输入需要配对的对数:");
    	scanf("%d",&num);
    	int female_rank_in_male[num][num];//女士在男士心中的排位 
    	int male_rank_in_female[num][num];//男士在女士心中的排位 
    	for (int i = 0; i < num; i++){
       		printf("男士%d心中的女士排行:",i+1); 
           for (int j = 0; j < num; j++){
           		scanf("%d",&female_rank_in_male[i][j]);
           }
        }
        for (int i = 0; i < num; i++){
       		printf("女士%d心中的男士排行:",i+1); 
            for (int j = 0; j < num; j++){
            	scanf("%d",& male_rank_in_female[i][j]);
           }
        }
        //测试数组 
      // int female_rank_in_male[5][5] = { { 2, 1, 4, 5, 3 }, { 4, 2, 1, 3, 5 }, { 2, 5, 3, 4, 1 }, { 1, 4, 3, 2, 5 }, { 2, 4, 1, 5, 3 } };
       //int male_rank_in_female[5][5] = { { 5, 1, 2, 4, 3 }, { 3, 2, 4, 1, 5 }, { 2, 3, 4, 5, 1 }, { 1, 5, 4, 3, 2 }, { 4, 2, 5, 3, 1 } };
       //男士和女士目前已配对的对象
       int *date_of_male = new int[num];
       int *date_of_female = new int[num];
       for (int i = 0; i < num; i++){
           date_of_male[i] = 0;
           date_of_female[i] = 0;
       }
       //男士追求过的女士的数量
       int *num_of_chased_female = new int[num];
       for (int i = 0; i < num; i++){
           num_of_chased_female[i] = 0;
       }
       do{//如果有男士没有对象
           for (int i = 0; i < num; i++){//按序号遍历所有男士 
          		printf("检查男士%d是否有对象\n",i+1);
               if (date_of_male[i] == 0){//如果某男士没有对象
               		printf("男士%d没有对象,可追求心仪的女士!\n",i+1); 
                   //该男士准备追求的女士(该男士优先表中还没追求过的排名最高的女士)
                   int female_to_chase = female_rank_in_male[i][num_of_chased_female[i]];
                   //判断该男士准备追求的女士是否有现任
                   int date_of_female_to_chase = date_of_female[female_to_chase - 1];
                   printf("男士%d准备追女士%d\n",i+1,female_to_chase);
                   if (date_of_female_to_chase != 0){
                   		printf("女士的现任是%d\n", date_of_female_to_chase );
                   }
                   else{
                   		printf("女士现在是单身哦~\n"); 
                   }
                   if (date_of_female_to_chase == 0){//如果该男士准备追求的女士没有现任
                       date_of_male[i] = female_to_chase;//该男士的对象变成准备追求的女士 
                       date_of_female[female_to_chase - 1] = i + 1;//女士的对象变成该男士 
                       printf("这样子的话,男士%d和女士%d在一起咯!\n",i+1,female_to_chase);
                   }
    			   //如果该男士准备追求的女士的现任在女士心目中比该男士更好,则什么也不做 
                   else if (current_male_is_better(num, male_rank_in_female[female_to_chase - 1], date_of_female_to_chase, i + 1)){  
                       printf("所以!男士 %d 被女士 %d拒绝了!\n" ,i+1,female_to_chase);
                   }
                   else{//如果该男士比该男士准备追求的女士的现任在妹子心目中更好
                       date_of_male[date_of_female_to_chase - 1] = 0;//该男士准备追求的女士的现任回到单身状态
                       date_of_male[i] = female_to_chase;//该男士的对象变成准备追求的女士 
                       date_of_female[female_to_chase - 1] = i + 1;//女士的对象变成该男士
                       printf("所以,男生%d和妹子%d在一起了!\n",i+1,female_to_chase);
                       printf("与此同时,不幸的是,男生 %d 变成单身狗了~~~\n",date_of_female_to_chase); 
                   }
    
                   num_of_chased_female[i]++;//该男生追求过的妹子数量加1
                    }
               else{
               		printf("男士%d已经跟女士%d在一起了呢~~下一个吧~~~\n",i+1,date_of_male[i]);
               }
           }
       } while (finish_or_not(num, date_of_male) == false);
       printf("\n");
       printf("┌——————幸福的结局——————-┐\n");
       printf("│                                   │\n");
       for (int i=0; i<num;i++){
       		printf("            男士%d - 女士%d       \n",i+1,date_of_male[i]);
       }
       printf("│                                   │\n");
       printf("└—————————————————-┘\n");
       delete[] date_of_male;
       delete[] date_of_female;
       delete[] num_of_chased_female;
       system("pause");//清空缓存 
       return 0;
    }
    bool finish_or_not(int num, int *date_of_male){
    
       for (int i = 0; i < num; i++){
           if (date_of_male[i] == 0){//判断是否全部完成配对 
           	printf("还有单身狗......再来~~\n");
               return false;
           }
       }
       printf("耶!稳定配对完成!已全部脱离单身狗行列!!!\n");
       return true;
    }
    //比较某女士现在的对象和追求者哪个在她心目中排行更高
    //数组参数是一维(是一位女士的优先表而不是所有女士的优先表)
    bool current_male_is_better(int num, int *male_rank_in_female, int current, int chasing){
       int rank_of_current, rank_of_chasing;//现任排行与追求者排行 
       for (int i = 0; i < num; i++){
           if (male_rank_in_female[i] == current){
               rank_of_current = i+1;
           }
           if (male_rank_in_female[i] == chasing){
               rank_of_chasing = i+1;
           }
       }
       printf("在女士心目中现任排名是: %d,而追求者排名则是: %d\n",rank_of_current,rank_of_chasing);
       if (rank_of_current < rank_of_chasing)
           return true;
       else
           return false;
    }
    

    测试

    简单最优完全配对测试

    如果恰巧男士i的首选为女士i;女士i的首选为男士i,则属于最优情况,即完全配对。
    在这里插入图片描述
    简单不完全配对测试

    测试目的为检验整个算法的每个步骤是否出错,即最初不是最优,则需要判断被追求女士的现任与追求者的排位并进行被淘汰的那个男士再次追求心中下一排行的女士。由于只有两对,因此较为简单。
    在这里插入图片描述
    复杂不完全配对测试

    在对数比较少的简单测试之后,增加对数,提升复杂性。以下展示的为5对情况下的,无论增加为多少对,在系统可承受范围内都可实现。
    在这里插入图片描述在这里插入图片描述

    展开全文
  • 稳定匹配问题

    2020-01-03 14:10:29
    稳定匹配问题有多种叙述方式: 医院和医学院毕业生的分配问题。 一组男性和一组女性的恋爱关系的分配问题。 问题的关键在于不出现不稳定对既A更倾向于B,B亦更倾向于A,但是A和B却没有配对。 下面列举一下匹配算法...

    稳定匹配问题有多种叙述方式:

    • 医院和医学院毕业生的分配问题。
    • 一组男性和一组女性的恋爱关系的分配问题。

    问题的关键在于不出现不稳定对既A更倾向于B,B亦更倾向于A,但是A和B却没有配对。

    下面列举一下匹配算法(以婚姻配对问题为例):
    此算法为
    此算法为男性优先算法,简单证明是每次都是由男性按照自己喜欢的女性列表从高到低进行表白,而女性只能选择接受与否。在这种情况下,女性一旦有了配偶就不可能恢复单身,而男性则可能因为女性选择了自己更加喜欢的男性而被单身。

    此算法最坏时间复杂度为O(n²)。

    展开全文
  • 保证最低要求的频谱市场稳定匹配
  • stableMatch 稳定匹配的javacode
  • 给定N个男人和N个女人,以及他们每个人对异性成员的偏好,稳定匹配是N个男人和女人之间的匹配,使得没有男人和女人更喜欢彼此伙伴。 Gale-Shapley 算法确定了这种稳定的匹配。 根据配方,它提供男性最佳或女性最佳...
  • 空间众包平台的三维稳定匹配问题
  • 从纳什、均衡的角度出发,考虑图论中的稳定匹配问题,发现稳定匹配可以用纳什均衡理论进行直观解释.对GS算法进行编程和运用,并且列举一个匹配问题,运用Matlab编程求解最优稳定匹配.最后考虑的着色和最短路径问题...
  • 算法(一)稳定匹配

    2021-01-25 10:33:43
    stable matching稳定匹配稳定匹配问题完美匹配与稳定配对不稳定配对同桌问题婚姻问题 稳定匹配 根据医院和医学院学生的一系列偏好,设计一套自我执行的入学程序。 非稳定配对: 若x更喜欢 y 而不是指定的医院。或者y...

    稳定匹配

    根据医院和医学院学生的一系列偏好,设计一套自我执行的入学程序。
    非稳定配对: 若x更喜欢 y 而不是指定的医院。或者y更喜欢 x 而不是其入院的学生,则x和 医院 y 是不稳定的:
    稳定分配。没有非稳定配对的分配。

    稳定匹配问题

    参与者对异性成员的评价
    每个男人按照优先顺序从最好到最坏的顺序列出女人。
    每个女人按照优先顺序从最好到最坏的顺序列出男人
    在这里插入图片描述

    完美匹配与稳定配对

    完美匹配 perfect matching

    • 指一个表中的每个条目都恰好匹配另一个表中的一个条目,反之亦然。在课堂上的例子中,这意味着每个男人和一个女人匹配,每个女人和一个男人匹配。

    稳定匹配 stable matching

    • 是没有不稳定对的完美匹配。换句话说,这既要求与某项匹配的条目数量(仅为1比1),也要求不能有一对(X,Y)使得X在当前匹配中更喜欢Y,而Y在当前匹配中更喜欢X。

    所以完美匹配只是说可以匹配的元素的数量,但它没有说匹配需要是稳定的。

    不稳定配对

    在这里插入图片描述

    同桌问题

    在同桌问题中,稳定匹配不总是成立
    在这里插入图片描述

    婚姻问题

    在这里插入图片描述

    展开全文
  • 稳定婚姻匹配 算法作业
  • 这篇文章将会对稳定匹配算法进行介绍及Python代码的实现,第一部分会针对稳定匹配的Gale-Shapley算法进行解析,第二部分就是用Python对该算法进行实现。 一、稳定匹配算法原理 1.1 介绍 稳定匹配(Stable ...

    这篇文章将会对稳定匹配算法进行介绍及Python代码的实现,第一部分会针对稳定匹配的Gale-Shapley算法进行解析,第二部分就是用Python对该算法进行实现。

    一、稳定匹配算法原理

    1.1 介绍

    稳定匹配(Stable Matching)问题就是假设现在有N个男生和N个女生跳舞选择伴侣,然后最开始的时候男、女生按照下面情况对彼此进行排序选择舞伴(见图1):

    • 每个男生都对女生按照最喜欢到最不喜欢进行排序;
    • 同样的,女生也是按照最喜欢的到最不喜欢对男生进行排序。

    算法目标:每个男都找到唯一一个女舞伴,反之亦如此,从而达到了所谓的稳定匹配。

    演示步骤:

    1.2 伪代码(Gale-Shapley Algorithm)

     1 # 首先初始化所有男生的状态为自由
     2 initialize each person to be free
     3 
     4 # 当男生没有未曾被匹配过并且也没有向所有其他女生寻求舞伴过时不断循环
     5 while some man m is not yet matched:
     6     # 每个男生按照对女生的喜欢程度选择舞伴
     7     w := m's most favroite woman to whom he has not yet proposed
     8     # 如果女生未被匹配到,则与男生进行配对
     9     if w is also not yet matched:
    10         w and m are paired
    11     # 如果女生与已匹配的男生相比更喜欢当前的这个男生,则拆散重新匹配
    12     elif w favors m to her current matched m':
    13         w and m are paired and m' is dis-matched
    14     # 否则该女生拒绝成为男生的舞伴
    15     else:
    16         w rejects m
    17 # 返回所有匹配成功的舞伴对
    18 return matched pairs

    二、Python代码实现

     

    # -*- encoding: UTF-8 -*-
    import copy
     
     
    # 男的所期望的对象
    manPrefers = dict((m, prefs.split(', ')) for [m, prefs] in (line.rstrip().split(': ')
                                    for line in open('men.txt')))
    # 女的所期望的对象
    womenPrefers = dict((m, prefs.split(', ')) for [m, prefs] in (line.rstrip().split(': ')
                                    for line in open('women.txt')))
     
    men = sorted(manPrefers.keys())
    women = sorted(womenPrefers.keys())
    
    # 定义检测函数检测匹配的伴侣是否稳定
    def check(engaged):
        inverseengaged = dict((v,k) for k,v in engaged.items())
        for w, m in engaged.items():
            shelikes = womenPrefers[w]
            shelikesbetter = shelikes[:shelikes.index(m)]
            helikes = manPrefers[m]
            helikesbetter = helikes[:helikes.index(w)]
            for man in shelikesbetter:
                womenOftheMan = inverseengaged[man]
                manLoves = manPrefers[man]
                if manLoves.index(womenOftheMan) > manLoves.index(w):
                    print("%s 和 %s 更喜欢彼此相比起他们当前的伴侣: %s 和 %s" % (w, man, m, womenOftheMan))
                    return False
            for woman in helikesbetter:
                manOfTheWomen = engaged[woman]
                womanLoves = womenPrefers[woman]
                if womanLoves.index(manOfTheWomen) > womanLoves.index(m):
                    print("%s 和 %s 更喜欢彼此相比起他们当前的伙伴:%s 和 %s" % (m, woman, w, manOfTheWomen))
                    return False
        return True
     
    def stableMatching():
        free_men = men[:]
        engaged  = {}
        manPref_temp = copy.deepcopy(manPrefers)
        womenPref_temp = copy.deepcopy(womenPrefers)
        while free_men:
            man = free_men.pop(0)
            manList = manPref_temp[man]
            woman = manList.pop(0)
            fiance = engaged.get(woman)
            if not fiance:
                engaged[woman] = man
                print("  %s 和 %s 成为伴侣" % (man, woman))
            else:
                womenList = womenPref_temp[woman]
                if womenList.index(fiance) > womenList.index(man):
                    engaged[woman] = man
                    print("  %s 舍弃 %s 而和 %s 成为伴侣" % (woman, fiance, man))
                    if manPref_temp[fiance]:
                        free_men.append(fiance)
                else:
                    if manList:
                        free_men.append(man)
        return engaged
     
    if __name__ == '__main__':
        print('\n伴侣匹配:')
        engaged = stableMatching()
     
        print('\n伴侣匹配:')
        print('  ' + ',\n  '.join('%s 和 %s 成为伴侣' % couple for couple in sorted(engaged.items())))
        print()
        print('伴侣稳定性检测通过' if check(engaged) else '伴侣稳定性检测不通过')
     
        print('\n\n因交换而产生伴侣搭配错误')
        engaged[women[0]], engaged[women[1]] = engaged[women[1]], engaged[women[0]]
        for woman in women[:2]:
            print('  %s 现在和 %s 成为伴侣' % (woman, engaged[woman]))
        print()
        print('伴侣稳定性检测通过' if check(engaged) else '伴侣稳定性检测不通过')
    

      

    转载于:https://www.cnblogs.com/jielongAI/p/9463029.html

    展开全文
  • 稳定匹配学习小计

    2021-05-05 08:28:15
    稳定匹配:特殊的二分图匹配,不妨假设X部和Y部称为男和女,那么每一个男的对于所有女的有一个优先级,每一个女的也对于男的有优先级,一组匹配是不稳定的即为存在一男一女他们认为对方比自己当前的对象优(那么他们...
  • C++实现稳定匹配算法代码,读取文本中的10名男生女生的喜好列表,然后为每个那女生进行匹配。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
  • 用于单ISA异构多核处理器的稳定匹配调度程序
  • 介绍了稳定性双边匹配的概念,概括了Gale-Sharply 和H-R 算法求解1-1 和1-k 的计算过程.考虑商品的多属性,给出了交易者按综合满意程度对满足自己约束对方的排序计算方法.将Gale-Sharply 和H-R 算法从理论上扩展到"p-k...
  • 然后,给出了基于可能度的弱稳定匹配、α-稳定匹配、强稳定匹配和超稳定匹配的定义,并分析了各种稳定匹配之间的关系;在此基础上,分别构建了获得弱稳定匹配、α-稳定匹配、强稳定匹配和超稳定匹配的多目标优化模型...
  • 稳定匹配代码

    2018-03-31 10:22:22
    算法设计经典练习算法匹配问题 附代码 简单易懂 适合初学者用来理解参考 建议阅读书籍算法设计 清华大学出版社
  • 男女稳定匹配算法 C

    2021-03-06 11:46:08
    男女稳定匹配算法 C代码 代码 #include<stdio.h> #include <windows.h> #define N 5 int Compared(int a, int b, int value); void chushi(); int * suiji(int min, int max); void pipei(); //void ...
  • 分层认知无线电网络中基于稳定匹配的资源分配算法
  • 针对现有双边匹配决策要求主体给出另一方全体... 进一步以双方主体满意度最大为目标, 同时考虑稳定匹配约束条件, 建立单目标优化模型并求解获得匹配方案; 最后, 通过算例分析表明了所提出方法的可操作性和有效性.</p>
  • Stable Matching稳定匹配

    千次阅读 2016-09-17 20:01:15
    一、稳定匹配婚姻问题 有n个男生n个女生,每个男生依照喜欢程度对n个女生进行了排序,同理每个女生也依照喜欢程度对n个男生进行了排序,现要将他们一一配对,要求所有的配对是稳定的,即不会出现一个女生相对自己...
  • G-S稳定匹配算法详解

    千次阅读 2020-03-02 17:03:31
    G-S稳定匹配算法详解 GS算法是解决稳定匹配问题(stable matching)的一个优秀的算法。 下面以男女配对的例子来介绍稳定匹配问题并阐述GS算法的具体步骤。 GS算法,全称Gale-Shapley算法。 一、问题描述及假设 有n...
  • 基于能量收集的设备间通信中的资源分配高效节能稳定匹配
  • 图片源自:美剧《How I met your mother》****本代码带有详细的注释,并在控制台输出时详细地说明了算法的过程,非常有助于新手理解稳定匹配问题和稳定婚姻算法的设计思路。****#include using namespace std;...
  • 稳定匹配算法 C 语言实现 - 框架

    千次阅读 2017-02-28 22:11:27
    稳定匹配算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,430
精华内容 1,372
关键字:

稳定匹配