二分图匹配算法_能岗匹配原理的含义和内容

(4) 2024-05-27 15:23

Hi,大家好,我是编程小6,很荣幸遇见你,我把这些年在开发过程中遇到的问题或想法写出来,今天说一说二分图匹配算法_能岗匹配原理的含义和内容,希望能够帮助你!!!。

 

上一篇文章讲了二分图匹配的缘起,这篇文章就讲讲二分图匹配的算法详解


二分图的概念
二分图又称作二部图,是图论中的一种特殊模型。 
设G=(V, E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在X中,另一个在Y中,则称图G为二分图。

二分图匹配算法_能岗匹配原理的含义和内容_https://bianchenghao6.com/blog__第1张图1

二分图的性质
定理:当且仅当无向图G的每一个回路的次数均是偶数时,G才是一个二分图。如果无回路,相当于任一回路的次数为0,故也视为二分图。

二分图的判定
如果一个图是连通的,可以用如下的方法判定是否是二分图: 

  • 在图中任选一顶点v,定义其距离标号为0,然后把它的邻接点的距离标号均设为1,接着把所有标号为1的邻接点均标号为2(如果该点未标号的话),如图所示,以此类推。 
  • 标号过程可以用一次BFS实现。标号后,所有标号为奇数的点归为X部,标号为偶数的点归为Y部。 
  • 接下来,二分图的判定就是依次检查每条边,看两个端点是否是一个在X部,一个在Y部。 

如果一个图不连通,则在每个连通块中作判定。 

二分图匹配算法_能岗匹配原理的含义和内容_https://bianchenghao6.com/blog__第2张

二分图的匹配

给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。 

最大匹配:选择边数最大的子图称为图的最大匹配问题(maximal matching problem) 。
完全匹配:如果一个匹配中,图中的每个顶点都和图中某条边相关联。

可以把图1中X(黄色)看成打车的人,Y(黑色)看成司机,黄的和黑的之间可以有连接,也就是可以做匹配。实际生活中,一个点可能只和很少数量的对面节点有连接。比如如果我们把接单的范围限制在5公里以内,尽管北京市有10万辆车在跑,和你能产生连接的可能只有七八辆。 

在二分图中,黄黑节点之间没有直接的关系。图中的每一条连线都可以有一个权重,通常在各个应用中,它们是设计出来的成本函数,或者利润函数。这个函数的设计就体现各个公司的领域知识了。

二分图的最大匹配算法,它满足两个条件:第一是保证节点数量少的一边所有节点都有匹配,第二是让整个网络中找到的匹配权重达到最大。

增广路径

增广路径的定义:设M为二分图G已匹配边的集合,若P是图G中一条连通两个未匹配顶点的路径(P的起点在X部,终点在Y部,反之亦可),并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。 
增广路径是一条“交错轨”。也就是说,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有...最后一条边没有参与匹配,并且起点和终点还没有被选择过,这样交错进行。显然P有奇数条边

增广路径性质:

  1. P的路径长度必定为奇数,第一条边和最后一条边都不属于M,因为两个端点分属两个集合,且未匹配。
  2. P经过取反操作可以得到一个更大的匹配M。
  3. M为G的最大匹配当且仅当不存在相对于M的增广路径。
     

匈牙利算法

用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出) 
算法轮廓:

  1. 置M为空
  2. 找出一条增广路径P,通过取反操作获得更大的匹配M’代替M
  3. 重复2操作直到找不出增广路径为止

算法详细步骤可参考:用于二分图匹配的匈牙利算法

还是不太理解该算法的话,可以参考:趣写算法系列之--匈牙利算法,视频:SWPU-ACM每周算法讲堂-匈牙利算法

 

算法实现

操作实质:当前的匹配对象与上一步的匹配对象相同时,回溯上一步能否换另一个匹配对象,若不能换,则不换,反之换;即能妥协就妥协,不能妥协坚决不妥协;

下面算法实现以ACM二分图匹配 HDU2063为例:


/*
运行方法:将本代码复制保存为testjs,然后运行node test.js
将输入的数据转化为关系数组,行表示男士,列表示女生,1表示有关系
    1 1
    1 2
    1 3
    2 1
    2 3
    3 1
*/
var data = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 0, 0]
];


var used = [];  //记录是否访问过
var match = []; //记录匹配情况

function find(x) {
    for (var i = 0; i < data[x].length; i++) {
        if (data[x][i] == 1 && !used[i]) {  //如果x对i有好感且在这一个递归选取阶段没有被搜索过
            used[i] = 1;        //标记为搜索过
            if ((match[i] == -1) || (find(match[i]) == 1)) {    //未被匹配过或能找到一条增广路(他的归属者可以选择其它被选者)
                match[i] = x;   //匹配i,x(将归属定位x)
                console.log(x + 1, '->', i + 1);
                return 1;       //能找到新的匹配
            }
        }
    }
    return 0;
}

function hungarian() {
    //初始化match
    for(var n = 0; n < data.length; match[n++] = -1);

    var m = 0;
    for (i = 0; i < data.length; i++) {
        if (match[i] == -1) {
            used = [];
            console.log('开始匹配:', i + 1);
            m += find(i)
        }
    }
    console.log('匹配数:' + m);
    return m;
}

hungarian();

时空分析

时间复杂度: 
找一次增广路径的时间为: 

  • 邻接矩阵: O(n^2)
  • 邻接表:O(n+m)

总时间: 

  • 邻接矩阵:O(n^3)
  • 邻接表:O(nm)

空间复杂度: 

  • 邻接矩阵:O(n^2)
  • 邻接表: O(m+n)
     

今天的分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

上一篇

已是最后文章

下一篇

已是最新文章

发表回复