匹配算法之 匈牙利算法详解

参考:

  1. 算法学习笔记(5):匈牙利算法
  2. 漫谈匈牙利算法
  3. 匈牙利算法、KM算法
  4. 匈牙利算法(二分图)
  5. 通俗易懂小白入门)二分图最大匹配——匈牙利算法
  6. 多目标跟踪之数据关联(匈牙利匹配算法和KM算法)
  7. 【小白学习笔记】(一)目标跟踪-匈牙利匹配

一、匈牙利算法基本概念

  • 匈牙利算法(Hungarian algorithm),即图论中寻找最大匹配的算法,暂不考虑加权的最大匹配(用KM算法实现)。
  • 匈牙利算法(Hungarian algorithm),主要用于解决一些与二分图匹配有关的问题。

1. 二分图

  • 二分图是图论中的一种特殊模型。若能将无向图G=(V,E)的顶点V划分为两个交集为空的顶点集,并且任意边的两个端点都分属于两个集合,则称图G为一个为二分图。
  • 二分图(Bipartite graph)是一类特殊的图,它可以被划分为两个部分,每个部分内的点互不相连。下图是典型的二分图。
    在这里插入图片描述
    可以看到,在上面的二分图中,每条边的端点都分别处于点集X和Y中。

2. 匹配

  • 图G的一个匹配由一组没有公共端点的不是圈的边构成的集合
    这里,我们用一个图来表示下匹配的概念:
    在这里插入图片描述
    如图所示,其中的三条边即该图的一个匹配。所以,匹配的两个重点:1. 匹配是边的集合;2. 在该集合中,任意两条边不能有共同的顶点
    那么,我们自然而然就会有一个想法,一个图会有多少匹配?有没有最大的匹配(即边最多的匹配呢)?

3. 最大匹配

  • 选择这样的边数最大的子集称为图的最大匹配问题。最大匹配的边数称为最大匹配

4. 完美匹配

  • 如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完美匹配(完全匹配),也称作完备匹配
  • 考虑部集为X={x1 ,x2, …}和Y={y1, y2, …}的二分图,一个完美匹配就是定义从X-Y的一个双射,依次为x1, x2, … xn找到配对的顶点,最后能够得到 n!个完美匹配

5. 最优匹配

  • 最优匹配又称为带权最大匹配,是指在带有权值边的二分图中,求一个匹配使得匹配边上的权值和最大
  • 一般X和Y集合顶点个数相同,最优匹配也是一个完备匹配,即每个顶点都被匹配。如果个数不相等,可以通过补点加0边实现转化。一般使用KM算法解决该问题。

6. 最小覆盖

  • 二分图的最小覆盖分为最小顶点覆盖最小路径覆盖

    最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联二分图的最小顶点覆盖数=二分图的最大匹配数

    最小路径覆盖也称为最小边覆盖,是指用尽量少的不相交简单路径覆盖二分图中的所有顶点二分图的最小路径覆盖数=|V|-二分图的最大匹配数

7. 最大独立集

  • 最大独立集是指寻找一个点集,使得其中任意两点在图中无对应边。对于一般图来说,最大独立集是一个NP完全问题,对于二分图来说:最大独立集=|V|-二分图的最大匹配数

8. 交替路

  • 从未匹配点出发,依次经过未匹配的边和已匹配的边,即为交替路,如Fig.3:3 -> 5 -> 1 -> 7 -> 4 -> 8
    在这里插入图片描述

9. 增广路(也称增广轨或交错轨)

  • 如果交替路经过除出发点外的另一个未匹配点,则这条交替路称为增广路,如交替路概念的例子,其途径点8,即为增广路。

  • 由增广路的定义推出下面三个结论(设P为一条增广路)
    1). P的路径长度一定为奇数,第一条边和最后一条边都是未匹配的边(根据要途经已匹配的边和要经过另一个未匹配点,这个结论可以理解成第一个点和最后一个点都是未匹配点,可以在Fig.3上的增广路观察到)

    2).对增广路径编号,所有奇数的边都不在M中,偶数边在M中

    3). P经过取反操作可以得到一个更大的匹配图,比原来匹配多一个(取反操作即,未匹配的边变成匹配的边,匹配的边变成未匹配的边,这个结论根据结论1).和交替路概念可得该结论)

    4). 当且仅当不存在关于图M的增广路径,则图M为最大匹配。所以匈牙利算法的思路就是:不停找增广路,并增加匹配的个数

二、匈牙利算法概述

  • 匈牙利算法主要用来解决两个问题:求二分图的最大匹配数和最小点覆盖数

1. 最大匹配问题

  • 看完上面讲的,相信读者会觉得云里雾里的:这是啥?这有啥用?所以我们把这张二分图稍微做点手脚,变成下面这样:
    在这里插入图片描述
    现在Boys和Girls分别是两个点集,里面的点分别是男生和女生,边表示他们之间存在“暧昧关系"。
  • 最大匹配问题相当于,假如你是红娘,可以撮合任何一对有暧昧关系的男女,那么你最多能成全多少对情侣?(数学表述:在二分图中最多能找到多少条没有公共端点的边
  • 现在我们来看看匈牙利算法是怎么运作的:
    • 我们从B1看起(男女平等,从女生这边看起也是可以的),他与G2有暧昧,那我们就先暂时把他与G2连接(注意这时只是你作为一个红娘在纸上构想,你没有真正行动,此时的安排都是暂时的)。
      在这里插入图片描述
    • 来看B2,B2也喜欢G2,这时G2已经“名花有主”了(虽然只是我们设想的),那怎么办呢?我们倒回去看G2目前被安排的男友,是B1,B1有没有别的选项呢?有,G4,G4还没有被安排,那我们就给B1安排上G4。
      在这里插入图片描述
    • 然后B3,B3直接配上G1就好了,这没什么问题。至于B4,他只钟情于G4,G4目前配的是B1。B1除了G4还可以选G2,但是呢,如果B1选了G2,G2的原配B2就没得选了。我们绕了一大圈,发现B4只能注定单身了,可怜。(其实从来没被考虑过的G3更可怜)
      在这里插入图片描述
  • 这就是匈牙利算法的流程,至于具体实现,我们来看看代码:
int M, N;            //M, N分别表示左、右侧集合的元素数量
int Map[MAXM][MAXN]; //邻接矩阵存图
int p[MAXN];         //记录当前右侧元素所对应的左侧元素
bool vis[MAXN];      //记录右侧元素是否已被访问过
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有边且未访问
        {
            vis[j] = true;                 //记录状态为访问过
            if (p[j] == 0 || match(p[j])) //如果暂无匹配,或者原来匹配的左侧元素可以找到新的匹配
            {
                p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循环结束,仍未找到匹配,返回匹配失败
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
        if (match(i))
            cnt++;
    }
    return cnt;
}

其实流程跟我们上面描述的是一致的。注意这里使用了一个递归的技巧,我们不断往下递归,尝试寻找合适的匹配

  • 注意:完美匹配一定是最大匹配,而最大匹配不一定是完美匹配

2. 最小点覆盖问题

  • 另外一个关于二分图的问题是求最小点覆盖:我们想找到最少的一些点,使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是,删除包含这些点的边,可以删掉所有边
    在这里插入图片描述
    这为什么用匈牙利算法可以解决呢?你如果以为我要长篇大论很久就错了,我们只需要一个定理:
    一个二分图中的最大匹配数等于这个图中的最小点覆盖数。

三、匈牙利算法核心

  • 匈牙利算法的核心就是不停的寻找增广路径来扩充匹配集合M
    我们给出实例来理解。
    在这里插入图片描述
    我们寻找如上图的最大匹配。

    (1)首先M集合为空(即没有边在里面),然后开始从X1寻找增广路,遵循上述原则我们只能在Yi中找,找到Y1,(X1,Y1 )这条路径,满足条件,取反,将(X1,Y1 )这条路径加入到M中。
    在这里插入图片描述
    (2)接着,我们找到X2点。遵循原则,找到Y1,Y1不是未覆盖点,这个时候我们有两种选择,一个是深度搜索,一个是广度搜索,我们采用深度优先,虽然Y1不是未覆盖点,(X2,Y1)不是增广路,但是Y1连着X1,X1又和Y3相连,我们考虑( X2,Y1,X1,Y3 )这条路径,奇数?左右交替?起终点未覆盖?奇路径不属于M偶路径属于?满足所有增广路条件,所以这是一条增广路径,然后取反,得到如下图。
    在这里插入图片描述
    (3)现在M集合中的路径有两条了,由于我们找到了增广路径,使得M中的边数量增加。所以增广路径是匈牙利算法的核心,每找到一条增广路径,意味这M集合中边的数量就会增加1,当找不到增广路径的时候,这个时候M中边的数量就是我们二部图的最大匹配数量。

    我们是怎样找到这条路径的呢,从X2开始寻找,我们先找到Y1,Y1不是未覆盖点,我们考虑Y1的原有匹配点X1,从X1开始寻找增广路,找到了Y3,当X1有增广路的时候,那么加上(X1,Y1)(X2,Y1)这两条路经,依然满足增广路条件。

    所以基于我们上面的理解可以给出寻找增广路的伪代码:

  while(找到Xi的关联顶点Yj){
          if(顶点Yj不在增广路径上){
                将Yj加入增广路
               if(Yj是未覆盖点或者Yj的原匹配点Xk能找到增广路径){ //扩充集合M
                      将Yj的匹配点改为Xi;
                      返回true
           }
      }
               返回false
}

从X2开始寻找是基于深度优先的,如果是基于广度优先呢?那么X2就会找到Y2。

四、匈牙利算法实现

  • 深度优先匈牙利算法C语言代码:
typedef struct tagMaxMatch{
    int edge[COUNT][COUNT];
    bool on_path[COUNT];
    int path[COUNT];
    int max_match;
}GRAPH_MATCH;

void outputRes(int *path){
    for (int i = 0 ; i<COUNT; i++) {
        printf("%d****%d\n",i,*(path+i));   //Yj在前 Xi在后
    }
}

void clearOnPathSign(GRAPH_MATCH *match){
    for (int j = 0 ; j < COUNT ; j++) {
        match->on_path[j] = false;
    }
   
}
//dfs算法
bool FindAugPath(GRAPH_MATCH *match , int xi){
    
    for (int yj = 0 ; yj < COUNT; yj++) {
        if ( match->edge[xi][yj] == 1 && !match->on_path[yj]) { //如果yi和xi相连且yi没有在已经存在的增广路经上
             match->on_path[yj] = true;
            if (match->path[yj] == -1 || FindAugPath(match,match->path[yj])) { // 如果是yi是一个未覆盖点或者和yi相连的xk点能找到增广路经,
                  match->path[yj] = xi; //yj点加入路径;
                  return true;
            }
        }
    }
    return false;
}

void Hungary_match(GRAPH_MATCH *match){
    for (int xi = 0; xi<COUNT ; xi++) {
          FindAugPath(match, xi);
          clearOnPathSign(match);
    }
    outputRes(match->path);
}

int main() {
    GRAPH_MATCH *graph = (GRAPH_MATCH *)malloc(sizeof(GRAPH_MATCH));
    for (int i = 0 ; i < COUNT ; i++) {
        for (int j = 0 ; j < COUNT ; j++) {
            graph->edge[i][j] = 0;
        }
    }
    graph->edge[0][1] = 1;
    graph->edge[0][0] = 1;
    graph->edge[1][1] = 1;
    graph->edge[1][2] = 1;
    graph->edge[2][1] = 1;
    graph->edge[2][0] = 1;
    graph->edge[3][2] = 1;
    
    for (int j = 0 ; j < COUNT ; j++) {
        graph->path[j] = -1;
        graph->on_path[j] = false;
    }
    
    Hungary_match(graph);   
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/19527.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

187页9万字企业大数据治理与云平台实施方案(word)

1 项目背景概述 1.1 项目背景理解 1.2 项目需求范围 2 项目技术方案 2.1 咨询研究服务方案 2.1.1 咨询研究服务内容 2.1.2 咨询服务方案 2.2 第三方独立评估 2.2.1 概述 2.2.2 管理办法 2.2.3 考核机制 2.3 安全咨询研究服务方案 2.3.1 安全咨询服务内…

【k8s】【ELK】日志环境部署【待写】

1、日志收集基本概念 k8s中pod的路径&#xff1a; containers log: /var/log/containers/*.log Pod log&#xff1a; /var/log/pods docker log: /var/lib/docker/containers/*/*.log如何收集日志 使用 EFKLogstashKafka 1、filebeat读取容器中的日志&#xff0c;然后写入K…

ChatGPT在小红书文案实践

今天聊一聊ChatGPT在小红书这个实际应用场景的案例。ChatGPT 以较低的门槛提高了使用者创作水平&#xff0c;有较高的下限&#xff0c;但如何创造更高质量的内容就要依靠使用者在领域的能力和AI使用技巧&#xff0c;作者无任何小红书推广和文案写作经验&#xff0c;文章内容来自…

快速排序、希尔排序、归并排序、堆排序、插入排序、冒泡排序、选择排序(递归、非递归)C语言详解

1.排序的概念及其运用 1.1排序的概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的记录&a…

python中使用opencv LED屏数字识别(可用做车牌识别,一样的原理)

应项目要求需要基于cpu的LED数字识别&#xff0c;为了满足需求&#xff0c;使用传统方法进行实验。识别传感器中显示的数字。因此使用opencv的函数做一些处理&#xff0c;实现功能需求。 首先读取图像&#xff0c;因为我没想大致得到LED屏幕的区域&#xff0c;因此将RGB转换为H…

postman处理各种请求数据

1、后台request接收postman参数 2、后台单个参数接收postman 3、后台RequestParam参数接收postman 注意事项&#xff1a;情况一&#xff1a;全部都是单个字符串的 情况二&#xff1a;有可能是一个json对象序列化成字符串过来的&#xff0c;那么需要在form-data中设置 …

鸿蒙Hi3861学习十-Huawei LiteOS-M(消息队列)

一、简介 消息队列&#xff0c;是一种常用于任务间通信的数据结构&#xff0c;实现了接收来自任务或中断的不固定长度的消息&#xff0c;并根据不同的接口选择传递消息是否存放在自己空间。任务能够从队列里面读取消息&#xff0c;当队列中的消息是空时&#xff0c;挂起读取任务…

国内免费cdn汇总2023最新

内容分发网络简称CDN&#xff0c;其原理大概是将网站内容分发至加速节点&#xff0c;让用户从就近的服务器节点上获取内容&#xff0c;从而提高网站的访问加载速度。大部分服务商&#xff08;如阿里云&#xff0c;腾讯云&#xff0c;京东云等&#xff09;的CDN服务是按使用量收…

【iOS】-- GET和POST(NSURLSession)

文章目录 NSURLSessionGET和POST区别 GET方法GET请求步骤 POSTPOST请求步骤 NSURLSessionDataDelegate代理方法AFNetWorking添加头文件GETPOST第一种第二种 NSURLSession 使用NSURLSession&#xff0c;一般有两步操作&#xff1a;通过NSURLSession的实例创建task&#xff1b;执…

STL配接器(容器适配器)—— stack 的介绍使用以及模拟实现。

注意 &#xff1a; 以下所有文档都来源此网站 &#xff1a; http://cplusplus.com/ 一、stack 的介绍和使用 stack 文档的介绍&#xff1a;https://cplusplus.com/reference/stack/stack/ 1. stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&…

预训练模型之BERT、Transformer-XL、XL-Net等

文章目录 预训练模型&#xff08;Pre-trained Models, PTMs&#xff09;前置知识BERTTransformer-XLXLNetTransformer-XL类似工作&#xff08;Scalable Transformer&#xff09;1. 《Scaling Transformer to 1M tokens and beyond with RMT》2. 《》 预训练模型&#xff08;Pre…

【Linux常见指令以及权限理解】基本指令(3)

写在前面 上一篇文章&#xff0c;我们学习了Linux的一些常用指令&#xff0c; 学习了如何理解Linux系统&#xff0c;介绍了对Linux系统的理解&#xff1a;Linux下一切皆文件 介绍了重定向还有管道相关的知识。这里是上一篇博客的链接&#xff1a;http://t.csdn.cn/2d6fc 接…

Vue组件化编程

2.1. 模块与组件、模块化与组件化 模块&#xff1a; 理解&#xff1a;向外提供特定功能的 js 程序&#xff0c;一般就是一个 js 文件为什么&#xff1a;js 文件很多很复杂作用&#xff1a;复用、简化 js 的编写&#xff0c;提高 js 运行效率 组件&#xff1a; 定义&#xff…

QT界面开发杂记(五)

QString转char* QString("name").toStdString().c_str() c_str()没有‘\0’结尾可能导致一些错误可以使用以下方法解决&#xff1a; QString xmlPath "path"; const char cXmlName[1024] {0}&#xff1b; memcpy((void*)cXmlName,xmlPath.toStdStri…

Prompt learning 教学[案例篇]:文生文案例设定汇总,你可以扮演任意角色进行专业分析

Prompt learning 教学[案例篇]&#xff1a;文生文案例设定汇总&#xff0c;你可以扮演任意角色进行专业分析 1.角色扮演 行为Prompt写法“牙医”““我想让你扮演一名牙医。我会向你提供有关寻找牙科服务&#xff08;例如 X 光、清洁和其他治疗&#xff09;的个人的详细信息。…

《编程思维与实践》1072.下一位妙数

《编程思维与实践》1072.下一位妙数 题目 思路 思路与最小不重复数基本一致,从最高位开始找到第一个出现9的位置,让其加1,后面全变为0即可. 只需要再加一个判定条件:不能被9整除. 由数学知识,一个数不能被9整除当且仅当各位数之和不能被9整除. 这里给出简单的证明: 不妨以三位…

工程化:vite4和vue3里面的命令式loading的封装及使用

用习惯了vue的组件使用方式,转到vue3里面发现没有了vue的原型,不能全局挂载方法了,我们要使用命令式调用组件该怎么做, 效果展示 代码演练 1.组件结构 2.基础的组件模板loading.vue <template><sectionclass="full-loading":class

多台电脑共享鼠标键盘软件

背景 最近接手了2个不同base的项目&#xff0c;由于2个base的不同代码加密管理&#xff0c;必须要用两台电脑进行分别开发。于是&#xff0c;我不大的办公桌上要摆上2个键盘和2个鼠标&#xff0c;一下子就显得桌面特别杂乱&#xff0c;办公心情都不舒畅了。 我跟朋友吐槽了这件…

华硕ROG|玩家国度魔霸新锐2023 Windows11原厂预装系统 工厂模式恢复安装带ASUSRecevory一键还原

华硕ROG|玩家国度魔霸新锐2023 Windows11原厂预装系统 工厂模式恢复安装带ASUSRecevory一键还原 文件地址&#xff1a;https://pan.baidu.com/s/1snKOsH3OMl3GZLqeAf-GLA?pwd8888 华硕工厂恢复系统 &#xff0c;安装结束后带隐藏分区以及机器所有驱动软件 需准备一个16G左右…

《小钊记》项目启动前期工作相关记录:VUE、powerdesigner建模、虚拟机密码重置、代码生成

目录 VUE镜像基本命令vue 不是内部或外部命令路径配置路由 powerdesigner 建模栏位添加注释id设置自增导出sql 虚拟机root密码重置&#xff08;centos7&#xff09;生成代码工具安装EasyCode插件连接数据库生成代码可以自定义模板复制现有的模板&#xff0c;在其基础上进行改造…
最新文章