匈牙利算法 原理 python实现

• 例子

用男女配对问题来解释，背景是：你是一个红娘，需要对图中的男女进行配对，其中男女之间有线就表示他们之间有暧昧，可以牵红线。

• 算法流程

• B1，他与G2有暧昧，那我们就先暂时把他与G2连接（此时的安排都是暂时的，不一定是最终的结果）
• B2，B2也喜欢G2，这时G2已经“名花有主”了（虽然只是我们设想的），那怎么办呢？我们倒回去看G2目前被安排的是B1，B1有没有别的选项呢？有的，是G4，G4还没有被安排，那我们就给B1安排上G4。
• B3，B3直接配上G1就好了，按理说G3也可以，但是只能安排一个
• B4，他只钟情于G4，G4目前配的是B1。B1除了G4还可以选G2，但是呢，如果B1选了G2，G2的原配B2就没得选了。我们绕了一大圈，发现B4只能注定单身了，可怜。（其实从来没被考虑过的G3更可怜）

?? ? ? ??? ? ? ?

• Python代码

import numpy as np
def match(i,mapArray,vis,p):
    M,N = mapArray.shape[0:2]
    for j in range(N):
        if mapArray[i][j] and vis[j]==0:
            vis[j]=1
            if p[j]==-1 or match(p[j],mapArray,vis,p):
                p[j] = i
                return 1
    return 0


def Hungarian(mapArray):
    cnt = 0
    
    M,N = mapArray.shape[0:2]
    p=np.zeros(N,dtype=np.int8)
    p[:]=-1 #//记录当前右侧元素所对应的左侧元素
    for i in range(M):
        vis=np.zeros(N,dtype=np.int8)#//记录右侧元素是否已被访问过
        if match(i,mapArray,vis,p):
            cnt+=1
    xCoord = np.where(p!=-1)[0].tolist()
    pos = [[i,p[i]]for i in xCoord]
    return cnt,pos
    
if __name__ == "__main__":
    mapArray = np.zeros((4,4))
    # 0,1,0,1
    # 0,1,0,0
    # 1,0,1,0
    # 0,0,0,1
    data = [[0,1,0,1],[0,1,0,0],[1,0,1,0],[0,0,0,1]]
    mapArray = np.array(data)#//邻接矩阵存图
    res = Hungarian(mapArray)
    print(res)    # 3, [[0, 2], [1, 1], [3, 0]]