匈牙利算法 原理 python实现

发布时间:2024年01月23日
  • 例子

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

  • 算法流程

  • 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]]

文章来源:https://blog.csdn.net/zhuhuigege/article/details/135770414
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。