python 中的匈牙利算法图

Question

我正在尝试在我的项目中实施匈牙利算法，但我不明白为什么它会出现无限循环...我已经尝试使用其他 bibartite 图并且它有效。所以我想知道我的图表有什么问题 G

 from hungarian_algorithm import algorithm
 G={
'agt2': {'Commentaire':200,'PhotoProfil': 8, 'PhotoSupp': 10, 'Prenom': 0}, 
'coco': {'Commentaire': 300, 'PhotoProfil': 200, 'PhotoSupp': 300, 'Prenom': 300}
 }
res=algorithm.find_matching(G,matching_type='max',return_type='list')
print(res)

Answer 1

图表很好，它可能是该包实现中的错误。正如我在评论中指出的那样，您可以改用 scipy.optimize.linear_sum_assignment from SciPy。

例如

import numpy as np
from scipy.optimize import linear_sum_assignment

# solve the assignment problem
G = np.array([[200, 8,   10,  0],
              [300, 200, 300, 300]])
row_indices, col_indices = linear_sum_assignment(G, maximize=True)

# print results
row_names = ['agt2', 'coco']
col_names = ['Commentaire', 'PhotoProfil', 'PhotoSupp', 'Prenom']
edges = [((row_names[r], col_names[c]), G[r, c]) for r, c in zip(row_indices, col_indices)]
print(edges)

打印

[(('agt2', 'Commentaire'), 200), (('coco', 'PhotoSupp'), 300)]

python 中的匈牙利算法图

hungarian algorithm's graph in python

python

hungarian-algorithm