《经典算法》稳定婚姻匹配

2023-11-21 17:50

本文主要是介绍《经典算法》稳定婚姻匹配,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

婚介所登记了N位男孩和N位女孩,每个男孩都对N个女孩的喜欢程度做了排序,每个女孩都对N个男孩的喜欢程度做了排序,你作为月老,能否给出稳定的牵手方案?

稳定的定义:如果男孩i和女孩a牵手,但男孩i对女孩b更喜欢,而女孩b的男朋友j拼不过男孩i,则没有力量阻碍男孩i和女孩b的私奔,这即是不稳定的。

思路:

   1962 年,美国数学家 David Gale 和 Lloyd Shapley 发明了一种寻找稳定婚姻的策略。不管男女各有多少人,不管他们各自的偏好如何,应用这种策略后总能得到一个稳定的婚姻搭配。换句话说,他们证明了稳定的婚姻搭配总是存在的。有趣的是,这种策略反映了现实生活中的很多真实情况。

    算法中采用了男生主动追求女孩的形式。

算法步骤描述:

    第一轮,每个男人都选择自己名单上排在首位的女人,并向她表白。这种时候会出现两种情况:

 (1)该女士还没有被男生追求过,则该女士接受该男生的请求。

 (2)若该女生已经接受过其他男生的追求,那么该女生会将该男士与她的现任男友进行比较,若更喜欢她的男友,那么拒绝这个人的追求,否则,抛弃其男友

    第一轮结束后,有些男人已经有女朋友了,有些男人仍然是单身。

    在第二轮追女行动中,每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个,并向她表白,不管她现在是否是单身。这种时候还是会遇到上面所说的两种情况,还是同样的解决方案。直到所有人都不再是单身。

package com.wyj.stable_marriage;

public class stableMarriage {
    private static final int num = 4;//赞记4对男女
    private static int[] match= {-1,-1,-1,-1};//-1表示还没有男朋友
    private static int[] man= {-1,-1,-1,-1};//-1表示单身
    private static int[][] BRefuseA = {{-1,-1,-1,-1},{-1,-1,-1,-1},{-1,-1,-1,-1},{-1,-1,-1,-1}};//-1表示未拒绝,0接受,1拒绝
    /**
     * A[][]:男生对女生满意度
     * B[][]:女生对男生满意度
     */
    private static int[][] A = {{0,3,2,1},{0,1,2,3},{0,2,3,1},{1,0,3,2}};
    private static int[][] B = {{2,3,1,0},{2,1,3,0},{0,2,3,1},{1,3,2,0}};
    public static void main(String[] args) {
        while(true) {//循环配对直到不存在单身男女为止
            //每个男人都选择自己名单上排在首位的女人,并向她表白
            int count=0;
            for(int i=0;i<num;i++) {
                //判断自己是否单身所以需要一个数组man
                if(!pdSingle(i)) {
                    count++;
                    continue;
                }
                //获取该男最中意女生是几号女嘉宾
                int girl_id = preferredGirl(A[i],i);
                //判断该女生单身或者更喜欢此时追求的男子则配对成功
                matchFun(girl_id,i);
            }
            if(count>=num) {
                break;
            }
        }
        printFun();
    }
    
    //获取未拒绝自己,且自己最中意的女孩号
    private static int preferredGirl(int[] arr,int boy_id){
        int xh = -1;
        int temp=-1;
        for(int i=0;i<arr.length;i++) {
            //因为要知道是否被拒绝所以需要一个二阶矩阵
            if(pdRefuse(i,boy_id)) {
                continue;
            }
            if(temp<arr[i]) {
                temp = arr[i];
                xh = i;
            }
        }
        return xh;
    }
    private static void matchFun(int girl_id,int boy_id) {
        //这里就发现需要一个数组存储该女孩的男友是谁
        if(match[girl_id]==-1) {
            match[girl_id] = boy_id;//女孩男朋友
            man[boy_id]=0;//男孩不单身了
            BRefuseA[girl_id][boy_id]=0;//接受男孩
        }else {
            int boyfirend_id = match[girl_id];
            if(B[girl_id][boyfirend_id]<B[girl_id][boy_id]) {//女孩更喜欢现在表白的男孩则抛弃现任男友
                match[girl_id] = boy_id;
                man[boy_id]=0;//男孩不单身了
                BRefuseA[girl_id][boy_id]=0;//接受男孩
                man[boyfirend_id]=-1;//男朋友又单身了
                BRefuseA[girl_id][boyfirend_id]=1;//前男友被拒绝了
            }else {
                BRefuseA[girl_id][boy_id]=1;//拒绝该男生
            }
        }
    }
    //判断单身
    private static boolean pdSingle(int i) {
        if(man[i]==-1) {
            return true;
        }
        return false;
    }
    //判断拒绝
    private static boolean pdRefuse(int girl_id,int boy_id) {
        if(BRefuseA[girl_id][boy_id]==-1) {
            return false;
        }
        return true;
    }
    //打印配对关系
    private static void printFun(){
        for(int i=0;i<match.length;i++) {
            System.out.println("女"+(i+1)+"的男朋友是男"+(match[i]+1));
        }
    }
}
每一步都有很详细的介绍,以及数组变量是怎么产生的,只要细心看应该可以理解。

这篇关于《经典算法》稳定婚姻匹配的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/404021

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.