精华内容
下载资源
问答
  • 2018-08-14 23:45:33

    匈牙利算法和KM算法

    这两天学了匈牙利算法和KM算法,全部都是网上找大神们的博客学的 先通过一些图了解KM算法到底是什么情况,但是要搞清楚KM算法又不得不提到匈牙利算法,要 想搞清楚匈牙利算法又不得不搞清楚二分图是个什么玩意儿,这是一个我们熟悉的递归啊~
    二分图是个什么东西,要想搞清楚,不得不看图,我从这位高手的博客有了个了解

    二分图附图讲解

    有了感性的认识后,还是要对概念搞清楚,啥子最大匹配、最小边覆盖、最小点覆盖、 最有匹配。。。

    二分图及相关概念

    然后就是匈牙利算法,还是先来有图的一目了然,先不管三七二十一,不管为啥子有这个算法, 这个算法有啥子用,这个算法为啥子要这样设计。。。。先搞清楚这个算法的流程再说,这位仁 兄非常幽默通俗的讲解了

    趣味匈牙利

    其实他说的那个 “ 腾 ” 我感觉应该就是增广路径的本质,就是 “ 腾 ” 除了位置,才好找 到最大匹配,也说清楚了匈牙利算法的本质

    然后就是KM算法,还是老规矩,先看有图的讲解

    KM算法入门

    看了过后虽然有了个大概的认识,但还是昏的,然后我就配合这两篇还有代码

    KM算法
    KM算法理解

    最后加一个百度百科上的KM算法代码
    const int N = 20, inf = 2147483647;
    int w[N][N], linky[N], visx[N], visy[N], lack;
    int lx[N] = {0}, ly[N] = {0}; //顶标
    bool find(int x) {
        visx[x] = true;
        for (int y = 0; y < N; ++y) {
            if (visy[y]) continue;
            int t = lx[x] + ly[y] - w[x][y];
            if (!t) {
                visy[y] = true;
                if (!~linky[y] || find(linky[y])) {
                    linky[y] = x;
                    return true;
                }
            } else lack = min(lack, t);
     
        }
        return false;
    }
    void km() {
        memset(linky, -1, sizeof(linky));
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                lx[i] = max(lx[i], w[i][j]); //初始化顶标
        for (int x = 0; x < N; ++x)
            for (; ;) {
                memset(visx, 0, sizeof(visx));
                memset(visy, 0, sizeof(visy));
                lack = inf;
                if (find(x)) break;
                for (int i = 0; i < N; ++i) {
                    if (visx[i]) lx[i] -= lack;
                    if (visy[i]) ly[i] += lack;
                }
            }
    }
    
    更多相关内容
  • 带权重的匈牙利KM算法 Kuhn-Munkras算法为带权重的匈牙利算法 参考视频链接:https://www.bilibili.com/video/BV16K4y1X7Ph?spm_id_from=333.337.search-card.all.click 1.得到4*4的矩阵 从最大matching转换到min ...

    带权重的匈牙利KM算法

    Kuhn-Munkras算法为带权重的匈牙利算法

    参考视频链接:https://www.bilibili.com/video/BV16K4y1X7Ph?spm_id_from=333.337.search-card.all.click

    1.得到4*4的矩阵 从最大matching转换到min cost match问题

    2. 每一行减去最小值

    每一行减去最小值:

    每一列减去最小值:

    4.用最少横纵线cover掉所有的0 目前三条线

    !!!截止条件:最小线=n 此处n为4,小于4则循环

    5. 找到没有覆盖的部分最小值 k=2,没被覆盖部分全部减去2

    6.红线交叉地方加上k=2

    7.完成第一轮循环

    8. 需要四条红线覆盖所有的0,循环终止

    9. 第一行只有一个0保证u1->v3匹配

    10.最后一行只有一个0,u4->v2匹配

    11.第一种匹配方式 u2->v1, u3->v2

    12 result

    第一种组合方式:
    第二种组合方式:
    展开全文
  • 文章目录1 二分图相关概念2 匈牙利算法求解无权二分图最大匹配2.1 相关概念2.2 算法原理2.3 匈牙利算法代码3 KM算法求解加权二分图最优匹配3.1 相关概念3.3 KM代码示例 1 二分图相关概念 二分图定义: 二分图又称双...

    1 二分图相关概念

    二分图定义:
    二分图又称双分图、二部图、偶图,指顶点可以分成两个不相交的集U和V(U和V皆为独立集(Independent Sets)),使得在同一个集内的顶点不相邻(没有共同边)的图。
    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

    我们定义匹配点、匹配边、未匹配点、非匹配边。如图3中,1、4、5、7为匹配点,其他顶点为未匹配点;1-5、4-7为匹配边、其他边为非匹配边。

    **匹配(matching)😗*二分图的一个“匹配”是指一些边的集合,任意两条边没有公共点。例如,图3、图4中红色的边就是图2的匹配。

    **最大匹配(maximum matching):**二分图的“最大匹配”,值的是二分图的所有匹配中边数最多的匹配。图4是一个最大匹配。它包含4条匹配边。

    **完美匹配(perfect matching):**二分图的一个“完美匹配”,是指所有点都在这个匹配中的一个匹配。也就是说这个匹配里的所有边刚好经过所有点一次。图4是一个完美匹配,显然,完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突)。
    但并非每个图都存在完美匹配。

    2 匈牙利算法求解无权二分图最大匹配

    2.1 相关概念

    在这里插入图片描述
    **交替路:**从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

    **增广路:**从一个未匹配点出发,走交替路,如果以另一个未匹配点(出发的点不算)为结尾,则这条交替路称为增广路(agumenting path)。例如,图 5 中的一条增广路如图 6 所示(图中的匹配点均用红色标出):
    在这里插入图片描述
    增广路有一个重要特点:非匹配边比匹配边多一条。因此,研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边,所以这样做不会破坏匹配的性质。交换后,图中的匹配边数目比原来多了 1 条。

    我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到最大匹配(这是增广路定理)。匈牙利算法正是这么做的。

    **增广路定理:**任意一个非最大匹配的匹配一定存在增广路。

    匈牙利树一般由BFS构造(类似于BFS树)。从一个未匹配点出发运行BFS(唯一的限制是,必须走交替路),直到不能再扩展为止。例如,由图7,可以得到如图8的一棵 BFS 树:
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    这棵树存在一个叶子节点为非匹配点(7 号),但是匈牙利树要求所有叶子节点均为匹配点,因此这不是一棵匈牙利树。如果原图中根本不含 7 号节点,那么从 2 号节点出发就会得到一棵匈牙利树。这种情况如图 9 所示(顺便说一句,图 8 中根节点 2 到非匹配叶子节点 7 显然是一条增广路,沿这条增广路扩充后将得到一个完美匹配)。

    2.2 算法原理

    注意前面增广路的定义:“从一个未匹配点出发,走交替路,以另一个未匹配点为结尾”,首尾都是未匹配点,说明首尾的边都是非匹配边。而又是交替路,也就是说非匹配边比匹配边多一条。那么我们完全可以把这条增广路里的匹配边和非匹配边互换(称为“交换匹配”),那么匹配边就会多出 1 条,实现了“增广”的意义。并且这样做并不会对其他边造成影响,也不破坏二分图的性质。

    那么我们就可以一直找增广路,不断交换匹配。根据增广路定理,如果找不到了,就说明已经达到最大匹配。

    同样可以证明,已经匹配的点永远不会退出匹配,只会更换匹配。

    这就是匈牙利算法最核心的部分了:一直找增广路,不断交换匹配。

    可能看完上面的叙述,还是有点困惑。一直找增广路,不断交换匹配到底应该怎么做?以下我举一个便于理解例子:
    在这里插入图片描述
    现在Boys和Girls分别是两个点集,里面的点分别是男生和女生,边表示他们之间存在“暧昧关系”。最大匹配问题相当于,假如你是红娘,可以撮合任何一对有暧昧关系的男女,那么你最多能成全多少对情侣?(数学表述:在二分图中最多能找到多少条没有公共端点的边)

    现在我们来看看匈牙利算法是怎么运作的:

    我们从B1看起(男女平等,从女生这边看起也是可以的),他与G2有暧昧,那我们就先暂时把他与G2连接(注意这时只是你作为一个红娘在纸上构想,你没有真正行动,此时的安排都是暂时的)。
    在这里插入图片描述
    来看B2,B2也喜欢G2,这时G2已经“名花有主”了(虽然只是我们设想的),那怎么办呢?我们倒回去看G2目前被安排的男友,是B1,B1有没有别的选项呢?有,G4,G4还没有被安排,那我们就给B1安排上G4。
    在这里插入图片描述
    我们来细看这一过程:

    开始是B1——G2;

    由于B2的加入,有增广路G4——B1——G2——B2;

    然后交换匹配,成为G4——B1——G2——B2;

    这是不是正是前面提到的一直找增广路,不断交换匹配。

    我们继续,B3直接配上G1就好了,这没什么问题。至于B4,他只钟情于G4,G4目前配的是B1。B1除了G4还可以选G2,但是呢,如果B1选了G2,G2的原配B2就没得选了。我们绕了一大圈,发现B4只能注定单身了,可怜。(其实从来没被考虑过的G3更可怜)
    最终结果:
    在这里插入图片描述

    2.3 匈牙利算法代码

    //---------------------DFS---------------------------------  
    #include<iostream>  
    #include<memory.h>  
    using namespace std;  
      
    #define MAXN 10  
    int graph[MAXN][MAXN];  
    int match[MAXN];  
    int visitX[MAXN], visitY[MAXN];  
    int nx, ny;  
      
    bool findPath( int u )  
    {  
        visitX[u] = 1;  
        for( int v=0; v<ny; v++ )  
        {  
            if( !visitY[v] && graph[u][v] )  
            {  
                visitY[v] = 1;  
                if( match[v] == -1 || findPath(match[v]) )  
                {  
                    match[v] = u;  
                    return true;  
                }  
            }  
        }  
        return false;  
    }  
      
    int dfsHungarian()  
    {  
        int res = 0;  
        memset( match, -1, sizeof(match) );  
        for( int i=0; i<nx; i++ )  
        {  
            memset( visitX, 0, sizeof(visitX) );  
            memset( visitY, 0, sizeof(visitY) );  
            if( findPath(i) )  
                res++;  
        }  
        return res;  
    }  
      
    //-----------------------------BFS-------------------------------  
    #include<iostream>  
    #include<memory.h>  
    using namespace std;  
      
    #define MAXN 10  
    int graph[MAXN][MAXN];  
    //在bfs中,增广路径的搜索是一层一层展开的,所以必须通过prevX来记录上一层的顶点  
    //chkY用于标记某个Y顶点是否被目前的X顶点访问尝试过。  
    int matchX[MAXN], matchY[MAXN], prevX[MAXN], chkY[MAXN];  
    int queue[MAXN];  
    int nx, ny;  
      
    int bfsHungarian()  
    {  
        int res = 0;  
        int qs, qe;  
        memset( matchX, -1, sizeof(matchX) );  
        memset( matchY, -1, sizeof(matchY) );  
        memset( chkY, -1, sizeof(chkY) );  
      
        for( int i=0; i<nx; i++ )  
        {  
            if( matchX[i] == -1 )   //如果该X顶点未找到匹配点,将其放入队列。  
            {  
                qs = qe = 0;  
                queue[qe++] = i;  
                prevX[i] = -1;  //并且标记,它是路径的起点  
                bool flag = 0;  
      
                while( qs<qe && !flag )  
                {  
                    int u = queue[qs];  
                    for( int v=0; v<ny&&!flag; v++ )  
                    {  
                        if( graph[u][v] && chkY[v]!=i ) //如果该节点与u有边且未被访问过  
                        {  
                            chkY[v] = i;    //标记且将它的前一个顶点放入队列中,也就是下次可能尝试这个顶点看能否为它找到新的节点  
                            queue[qe++] = matchY[v];  
                            if( matchY[v] >= 0 )  
                                prevX[matchY[v]] = u;  
                            else    //到达了增广路径的最后一站  
                            {  
                                flag = 1;  
                                int d=u, e=v;  
                                while( d!=-1 )  //一路通过prevX找到路径的起点  
                                {  
                                    int t = matchX[d];  
                                    matchX[d] = e;  
                                    matchY[e] = d;  
                                    d = prevX[d];  
                                    e = t;  
                                }  
                            }  
                        }  
                    }  
                    qs++;  
                }  
                if( matchX[i] != -1 )  
                    res++;  
            }  
        }  
        return res;  
    }  
    

    3 KM算法求解加权二分图最优匹配

    3.1 相关概念

    完备匹配:定义 设G=为二部图,|V1|≤|V2|,M为G中一个最大匹配,且|M|=|V1|,则称M为V1到V2的完备匹配。也就是说把一个集合中的点全部匹配到另一个集合中。在上述定义中,若|V2|=|V1|,则完备匹配即为完美匹配,若|V1|最大匹配。

    二分图最优匹配:对于二分图的每条边都有一个权(非负),要求一种完备匹配方案,使得所有匹配边的权和最大,记做最优完备匹配。(特殊的,当所有边的权为1时,就是最大完备匹配问题)

    二分图带权匹配与最优匹配:什么是二分图的带权匹配?二分图的带权匹配就是求出一个匹配集合,使得集合中边的权值之和最大或最小,这个匹配集合比一定是完备匹配。而二分图的最优匹配则一定为完备匹配,在此基础上,才要求匹配的边权值之和最大或最小。二分图的带权匹配与最优匹配不等价,也不互相包含。

    顶标:每个节点与另一个集合中节点之间的最大权值

    可行顶标(标杆):对于原图中的任意一个节点,给定一个函数 求出节点的顶标值。我们用数组 记录集合 中的节点顶标值,用数组 记录集合 中的节点顶标值。并且,对于原图中任意一条边 ,都满足 。

    相等子图:设 G(V,E) 为二部图, G’(V,E’) 为二部图的子图。如果对于 G’ 中的任何边 满足, ,我们称 G’(V,E’) 为 G(V,E) 的等价子图或相等子图(是G的生成子图)。

    3.2 核心思想

    对二分图G和一组可行标,满足可行标边界条件(lx[i]+ly[j]=w[i,j])的所有边构成的生成子图(需要包含所有顶点),称为其等价子图(相等子图),在这个等价子图上,寻找其完备匹配,如果完备匹配存在,则这个完备匹配M就是图G的最大权匹配,最大权等于所有可行标的和; 如果完备匹配不存在,则修改可行标,用贪心的思想,将最优的边加入等价子图. KM算法就是一种逐次修改可行顶标的方法,使之对应的等价子图逐次增广(增加边),最后出现完备匹配.

    3.3 KM代码示例

    /******************************************************
    二分图最佳匹配 (kuhn munkras 算法 O(m*m*n)).
    邻接矩阵形式 。  返回最佳匹配值,传入二分图大小m,n
    邻接矩阵 mat ,表示权,match1,match2返回一个最佳匹配,为匹配顶点的match值为-1,
    一定注意m<=n,否则循环无法终止,最小权匹配可将全职取相反数。
    初始化:  for(i=0;i<MAXN;i++)
                 for(j=0;j<MAXN;j++) mat[i][j]=-inf;
    对于存在的边:mat[i][j]=val;//注意不能负值 
    ********************************************************/
    #include<string.h>
    #define MAXN 310
    #define inf 1000000000 
    #define _clr(x) memset(x,-1,sizeof(int)*MAXN)
    int KM(int m,int n,int mat[][MAXN],int *match1,int *match2)
    {
            int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN];
        int p,q,i,j,k,ret=0;
        for(i=0;i<m;i++)
        {
            l1[i]=-inf;
            for(j=0;j<n;j++)
                l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
            if(l1[i]==-inf)  return -1;
        } 
        for(i=0;i<n;i++)
            l2[i]=0;
        _clr(match1);
        _clr(match2);
        for(i=0;i<m;i++)
        {
            _clr(t);
            p=0;q=0;
            for(s[0]=i;p<=q&&match1[i]<0;p++)
            {
                for(k=s[p],j=0;j<n&&match1[i]<0;j++)
                {
                    if(l1[k]+l2[j]==mat[k][j]&&t[j]<0)
                    {
                        s[++q]=match2[j];
                        t[j]=k;
                        if(s[q]<0)
                        {
                            for(p=j;p>=0;j=p)
                            {
                                match2[j]=k=t[j];
                                p=match1[k];
                                match1[k]=j;
                            }    
                        }    
                    }    
                }    
            } 
            if(match1[i]<0)
            {
                i--;
                p=inf;
                for(k=0;k<=q;k++)
                {
                    for(j=0;j<n;j++)
                    {
                        if(t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
                           p=l1[s[k]]+l2[j]-mat[s[k]][j];
                    }    
                }  
                for(j=0;j<n;j++)
                   l2[j]+=t[j]<0?0:p;
                for(k=0;k<=q;k++)
                   l1[s[k]]-=p;  
            }       
        } 
        for(i=0;i<m;i++)
            ret+=mat[i][match1[i]];
        return ret;      
    }
    

    给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

    极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

    如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。完美匹配:如果所有点都在匹配边上,称这个最大匹配是完美匹配。

    求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

    如果G为加权二分图,则权值和最大的完备匹配称为最佳匹配,求一个二分图的最佳匹配的普遍算法是KM(Kuhn-Munkres)算法。

    KM算法的基本思想是,把权值转化为可行顶标,再用匈牙利算法求出一组完备匹配,如果无法求出完备匹配,则修改可行顶标,直至找到完备匹配为止,这时的完备匹配为最佳匹配。

    Kuhn-Munkras算法流程:

    (1)初始化可行顶标的值

    (2)用匈牙利算法寻找完备匹配

    (3)若未找到完备匹配则修改可行顶标的值

    (4)重复(2)(3)直到找到相等子图的完备匹配为止

    参考文献:
    [1]https://blog.csdn.net/weixin_29903713/article/details/112778495
    [2]https://blog.csdn.net/weixin_43093481/article/details/84558029
    [3]https://www.cnblogs.com/kuangbin/archive/2012/08/19/2646535.html
    [4]https://www.cnblogs.com/logosG/p/logos.html
    [5]https://my.oschina.net/husthang/blog/840806?tdsourcetag=s_pcqq_aiomsg
    [6]https://blog.csdn.net/qq_25379821/article/details/83750678

    展开全文
  • 匈牙利算法(Hungarian Algorithm)与KM算法(Kuhn-Munkres Algorithm)是做多目标跟踪的小伙伴很容易在论文中见到的两种算法。他们都是用来解决多目标跟踪中的数据关联问题。 二级目录 三级目录 ...

    一、匈牙利算法

    1、算法背景及思想

    匈牙利算法,是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,由匈牙利数学家Edmonds于1965年提出,因而得名。

    匈牙利算法(Hungarian Algorithm)与KM算法(Kuhn-Munkres Algorithm)做多目标跟踪很容易在论文中见到的两种算法。他们都是用来解决多目标跟踪中的数据关联问题。

    上述利用增广路找最大匹配的算法,就叫做匈牙利算法。

    2、最大匹配

    结合情侣配对问题,男生女生之间互生情愫的有很多,甚至有的人对多个人都有意向,因此潜在的情侣组合方式有很多种。所谓的“任意两条边都不依附于同一个顶点”,意思就是只要我们撮合的时候,不要给某个人安排两个对象就行。作为牵线人,我们可以撮合一对,也可以撮合两对,这样每一种撮合方式,都叫一个匹配。撮合成功的这些情侣就是所谓的子图M。

    按照上面的匹配方式,我们既不能把没有意向的两个人撮合在一起,有的人又对多个人有意向,因此可以花一点心思,尽可能地协调一下大家的意向,做到多撮合成功几对。这样,成功撮合的情侣最多的这种撮合方式,就叫最大匹配。

    3、最优匹配/完美匹配

    解释:如果非常幸运,在我们的安排下,每个人都找到了自己心仪的对象。这种撮合方式,叫做最优匹配或完美匹配。

    4、增广路径

    (非匹配边) (匹配边) (非匹配边)

    B--------------a----------------A-----------------c

    B和c都是没有被匹配过的点,而它又是这条交替路的起点和终点。这条交替路就是增广路。

    5、代码实现

    匈牙利算法有一个很明显的问题,按它的思路找到的最大匹配往往不是我们心中的最优。匈牙利算法将每个匹配对象的地位视为相同,在这个前提下求解最大匹配。这个和我们研究的多目标跟踪问题有些不合,因为每个匹配对象不可能是同等地位的,总有一个真实目标是我们要找的最佳匹配,而这个真实目标应该拥有更高的权重,在此基础上匹配的结果才能更贴近真实情况。

    bool find(int x){
    	int i,j;
    	for (j=1;j<=m;j++){    //扫描每个妹子
    		if (line[x][j]==true && used[j]==false)      
    		//如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题,但是没有成功,所以就不用瞎费工夫了)
    		{
    			used[j]=1;
    			if (girl[j]==0 || find(girl[j])) { 
    				//名花无主或者能腾出个位置来,这里使用递归
    				girl[j]=x;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    class graph:
        def __init__(self,gi,bo): # 输入二部图两个顶点集合的数目,每个集合的顶点均用1, ... , n表示
            self.numg=gi # 女孩数量
            self.numb=bo # 男孩数量
            self.boy={i:[]for i in range(1,bo+1)} # 男孩的可连接对象,建图
            self.viag=[0 for i in range(gi+1)] # 记录当前匹配女孩的对象
            self.use=[0 for i in range(gi+1)] # 检查女孩是否被搜索过
        def add(self,u,v):
            self.boy[v].append(u)
        def find(self,j): # 寻找 j 男孩起始的增广路
            if j==0:
                return 1
            for i in self.boy[j]:
                if self.use[i]==0: # 女孩没有被搜索过
                    self.use[i]=1
                    if self.find(self.viag[i]): # 检查 j 匹配女孩后,女孩原男友是否有其它的女友,有则表示存在增广路
                        self.viag[i]=j
                        return 1
            return 0
        def Hungarian(self):
            sum=0
            for i in range(1,self.numb+1): # 检查每个男孩是否能找到女有
                self.use = [0 for i in range(self.numg + 1)] # 初始化为0
                if self.find(i):
                    sum+=1
            return sum,self.viag[1:]
    
    if __name__=="__main__":
        n,girlnum,boynum = map(int, input().split())
        dic = graph(girlnum,boynum)
        for i in range(n):
            a, b = map(int, input().split())
            dic.add(a,b)
        print(dic.Hungarian())
    

    6、匈牙利算法总结

    6.1、深度优先

    每个点从另一个集合里挑对象,没冲突的话就先安排上,要是冲突了就用增广路径重新匹配。重复上述思路,直到所有的点都找到对象,或者找不到对象也找不到增广路。

    上述是深度优先匈牙利算法。就是冲突了立刻用增广路来解决。

    6.2、 广度优先

    另外一种是广度优先匈牙利算法。思路是,冲突了就换一个心仪对象,看另一个心仪对象是不是也配对了,要是都配对了,再用增广路来解决

    广度优先的流程是这样的:

    (1)A和a连上。

    (2)B也想连a,但是a被连了,就找下一个心仪对象b

    (3)b没有被连上,B和b就连在一起。

    (4)轮到C的时候,C找心仪对象c。

    (5)c也没被连上,所以C和c连一起。

    二、KM算法思想及局限性

    KM算法解决的是带权二分图的最优匹配问题。

    匈牙利算法得到的最大匹配并不是唯一的,预设匹配边、或者匹配顺序不同等,都可能会导致有多种最大匹配情况,所以有一种替代KM算法的想法是,我们只需要用匈牙利算法找到所有的最大匹配,比较每个最大匹配的权重,再选出最大权重的最优匹配即可得到更贴近真实情况的匹配结果。但这种方法时间复杂度较高,会随着目标数越来越多,消耗的时间大大增加,实际使用中并不推荐。

    代码示例

    1、定义KM方法类

    import numpy as np
    
    class KM_Algorithm_4:
    
        def __init__(self, Bipartite_Graph):
    
            self.Bipartite_Graph = Bipartite_Graph
    
            # 左右结点数量记录
            self.left = self.Bipartite_Graph.shape[0]  # 以左边为主
            # print(self.Bipartite_Graph)
            # print(self.Bipartite_Graph[0])
            self.right_true = self.Bipartite_Graph.shape[1]
            self.right = self.Bipartite_Graph.shape[1] + self.left
    
            self.reshape_graph()
    
            # 初始化顶标
            self.label_left = np.max(self.Bipartite_Graph, axis=1)  # 设置左边顶标为权重最大值(每行的最大值)
    
            self.label_right = np.zeros(self.right)  # 右边集合的顶标设置为0
    
            # 初始化辅助变量——是否已匹配
            self.visit_left = np.zeros(self.left, dtype=bool)
            self.visit_right = np.zeros(self.right, dtype=bool)
    
            # 初始化右边的匹配结果.如果已匹配就会对应匹配结果
            self.match_right = np.empty(self.right) * np.nan
    
            # 用inc记录需要减去的权值d,不断取最小值故初始化为较大值。权值都为负数,应该不用很大也行
            self.inc = 1000*1000*1000
    
            self.fail_boy = list()  # 每次匹配重新创建一个二分图匹配对象,所以这个也不用手动重置了
    
        def reshape_graph(self):
            new = np.ones((self.left, self.left)) * 0
            self.Bipartite_Graph = np.column_stack((self.Bipartite_Graph, new))
            # print(self.Bipartite_Graph)
    
        def match(self, boy):
            # print("---------------我是boy%d----------------------" % boy)
            boy = int(boy)
            # 记录下这个boy已经被寻找
            self.visit_left[boy] = True
            for girl in range(self.right):
                # 如果这个女生还没访问过
                if not self.visit_right[girl] and self.Bipartite_Graph[boy][girl] >= 0:  # 女孩仍未匹配并且男女之间存在匹配的可能性(不可匹配的点设置为负数,取反后变正数,故正数不可取)
                    gap = self.label_left[boy] + self.label_right[girl] - self.Bipartite_Graph[boy][girl]  # gap也不会取到不能匹配的那条边
                    if gap == 0:   # 差值为0,是可行的替换。所以可以直接尝试替换。后面不行再去将这个一起减去gap。这个列表是记录希望匹配的
                        self.visit_right[girl] = True
                        # 女生未被匹配,或虽然已被匹配,但是已匹配对象(男生)有其他可选备胎。这里那些是否已访问的列表不需要重置,因为不改变前面的尝试匹配
                        if np.isnan(self.match_right[girl]) or self.match(self.match_right[girl]):
                            self.match_right[girl] = boy
                            # print(self.match_right)
                            # 递归匹配,匹配成功
                            return 1
    
                    # 找到权值最小的差距
                    elif self.inc > gap:
                        self.inc = gap  # 等于0的gap不会存在这,所以只要存在可能匹配的情况,gap就不会等于原来的inc
    
            return 0
    
        def Kuh_Munkras(self):
    
            self.match_right = np.empty(self.right) * np.nan
            # 寻找最优匹配
            for man in range(self.left):
                while True:
                    self.inc = 1000*1000  # the minimum gap
                    self.reset()  # 每次寻找过的路径,所有要重置一下
    
                    # 可找到可行匹配
                    if self.match(man):
                        break
                    # 不能找到可行匹配
                    # (1)将所有在增广路中的boy方点的label全部减去最小常数
                    # (2)将所有在增广路中的girl方点的label全部加上最小常数
                    for k in range(self.left):
                        if self.visit_left[k]:
                            self.label_left[k] -= self.inc
                    for n in range(self.right):
                        if self.visit_right[n]:
                            self.label_right[n] += self.inc
    
            return self.fail_boy
    
        def calculateSum(self):
            sum = 0
            boys_girls = []
            self.fail_boy = [i for i in range(self.left)]
            for i in range(self.right_true):
                if not np.isnan(self.match_right[i]):
                    sum += self.Bipartite_Graph[int(self.match_right[i])][i]
                    boy_girl = (int(self.match_right[i]), i)
                    boys_girls.append(boy_girl)
                    self.fail_boy.remove(int(self.match_right[i]))
            print("最短路径:", sum)
    
            return boys_girls, self.fail_boy
    
        def getResult(self):
            return self.match_right
    
        def reset(self):
            self.visit_left = np.zeros(self.left, dtype=bool)
            self.visit_right = np.zeros(self.right, dtype=bool)
    

    2、定义权重数值,执行主函数

    # 定义权重数值
    def data():
        graph = [[8,6,-1,-1],
                [-1,3,9,-1],
                [9,8,-1,-1],
                [-1,-1,2,-1]]
        #print(graph)
        km = KM_Algorithm_4(np.array(graph))
    
        km.Kuh_Munkras()  # 匹配
    
        boys_girls, fail_boys = km.calculateSum()  # 匹配结果元组,以及失败的男孩们
    
        print("匹配男女列表", boys_girls)
        print("失败男孩列表", fail_boys)
    
    
    if __name__ == '__main__':
        data()
    

    参考文献

    https://blog.csdn.net/dark_scope/article/details/8880547
    https://zhuanlan.zhihu.com/p/208596378
    https://aistudio.baidu.com/aistudio/projectdetail/2040378

    展开全文
  • 匈牙利算法 & KM算法

    2021-11-04 20:00:00
    KM算法 算法学习笔记(5):匈牙利算法 匈牙利算法(Hungarian Algorithm)与 KM 算法(Kuhn-Munkres Algorithm)主要用于解决一些与二分图匹配有关的问题,这种问题在解决多目标跟踪中的数据关联时会比较常见。 二分...
  • 匈牙利算法 二分图的最大匹配可以转换为一个网络流的问题,但是我们一般使用匈牙利算法,这种算法更易于理解,方便编写。 介绍这个算法之前,首先要介绍一些必要的概念。 交错路 : 从一个未匹配点出发,依次遍历未...
  • 目录匈牙利算法匈牙利算法代码小结参考 匈牙利算法 匈牙利算法代码 小结 参考
  • 匈牙利算法 # -*- coding: utf-8 -*- """ 匈牙利算法 O(E*V) """ def Hungarian(l_node, visited): for r_node in graph[l_node]: if r_node not in T: S[l_node] = r_node T[r_node] = l_node return True ...
  • 后来通过实习和查阅论文等渠道了解到了多目标跟踪领域经典的Sort和DeepSort算法,其中都使用到了匈牙利算法解决匹配问题,因此开此贴记录一下算法的学习过程。 指派问题概述 首先,对匈牙利算法解决的问题进行概述:...
  • 带你入门多目标跟踪(三)匈牙利算法&KM算法

    万次阅读 多人点赞 2019-07-02 19:30:41
    匈牙利算法(Hungarian Algorithm)与KM算法(Kuhn-Munkres Algorithm)是做多目标跟踪的小伙伴很容易在论文中见到的两种算法。他们都是用来解决多目标跟踪中的数据关联问题。 对理论没有兴趣的小伙伴可以先跳过...
  • 匈牙利算法与KM算法

    2019-06-18 15:12:00
    一、匈牙利算法(Hungary Algorithm) ...二、KM算法(Kuhn–Munkres Algorithm) [https://www.cnblogs.com/logosG/p/logos.html] 转载于:https://www.cnblogs.com/How-Come/p/11045...
  • LeetCode第280场周赛 - 数组的最大与和 - 匈牙利算法/KM算法 题目: LeetCode「美团 & 力扣」联合主办 第 280 场周赛 第四题 《数组的最大与和》 解题思路: 题目的本质是将数组nums中的n个数字分配到不同的...
  • 二分图(匈牙利,KM算法详解).pptx
  • 二分图匹配 匈牙利算法和KM算法简介.ppt
  • 二分图匹配:匈牙利算法和KM算法

    千次阅读 2020-09-01 13:20:33
    这个关联算法一般使用匈牙利KM算法。算法的本质是一个二分图匹配问题:给定U,V两个集合,在MOT问题中这两个集合表示上一帧的检测框集合,以及当前帧的检测框集合,其目的是为当前帧的每个目标框和上一帧的做关联...
  • 更具体的讲解看 从匈牙利算法到KM算法 - 知乎,讲得非常清晰了。 注意:KM算法需要从少端点侧出发试探,逐一匹配多端点侧。否则会死循环,失败。 class KM_Algorithm: def __init__(self, Net): #Net = [[3,4,6,4,9...
  • 二分图匹配——匈牙利算法和KM算法

    千次阅读 2018-11-08 10:02:15
    求二分图的最佳匹配有一个非常优秀的算法,可以做到O(N^3),这就是KM算法。该算法描述如下: 1.首先选择顶点数较少的为X部,初始时对X部的每一个顶点设置顶标,顶标的值为该点关联的最大边的权值,Y部的顶点顶标为0...
  • 做为一个算法工程师,除了了解各种NN网络结构,调的一手好参数,传统算法这一部分也不能拉下。因此着手写这个系列,一方面加深自己对算法的理解,另一方面探讨在实际业务中的应用,毕竟AC不是目的,融汇贯通的应用才...
  • 传统的数据关联方法多为运筹学方法,比较经典的即为匈牙利匹配算法和KM算法,接下来详细介绍这两种算法。 在介绍匈牙利匹配算法和KM算法之前,我们需要了解一个“二分图”的概念。简单来说就是,两组集合U和V,U和V...
  • 二分图匹配匈牙利算法和KM算法简介.pptx
  • 最近接触的匹配算法有三种:Gale-Shapley算法,匈牙利算法和KM算法 。 Gale-Shapley算法: 是用来求得一个稳定匹配使用的,它又称为 “ 求婚-拒绝算法 ”,可以说这个算法的名字起得也是非常知名达意了。 就拿...
  • KM算法PPT讲解分析

    2020-07-14 13:34:23
    这种问题被称为带权二分图的最优匹配问题,可由KM算法解决。 比如上图,A做工作a的效率为3,做工作c的效率为4......以此类推。 不了解KM算法的人如何解决这个问题?我们只需要用匈牙利算法找到所有的最大匹配,...
  • 二分图匹配-匈牙利算法和KM算法简介.pptx
  • 二分图匹配,匈牙利算法和KM算法简介 二分图匹配,匈牙利算法和KM算法简介 二分图匹配,匈牙利算法和KM算法简介 二分图匹配,匈牙利算法和KM算法简介 二分图匹配,匈牙利算法和KM算法简介 用增广路求最大匹配(称作...

空空如也

空空如也

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

匈牙利km算法