匈牙利算法:
python线性规划(linear programming)与分配问题(assignment problem)—— linear_sum_assignment的使用
python数学建模之用optimize.linear_sum_assignment解决模型优化之指派问题
遇到一个问题,有一个坐标列表A:[[10,20],[20,30],[42,41],[45,41]], 和一个坐标列表B:[[14,24],[41,42],[20,31],[42,41]],需要看这两个坐标列表之间谁与谁更匹配,这时候就可以使用匈牙利算法来实现
其中分别使用欧几里得距离以及曼哈顿距离作为损失函数
from scipy.optimize import linear_sum_assignment
import numpy as np
position_a = [[10,20],[20,30],[42,41],[45,41]]
position_b = [[14,24],[41,42],[20,31],[42,41]]
cost_martix = [[np.power((np.array(a)-np.array(b)),2).sum() for a in position_a] for b in position_b]
print(cost_martix)
row_ind, col_ind = linear_sum_assignment(cost_martix)
print(row_ind)
print(col_ind)
for x,y in zip(row_ind, col_ind):
print("列表B中的%s,应该与列表A中坐标%s匹配,距离消耗为%d"%(position_b[x],position_a[y],cost_martix[x][y]))
cost_martix2 = [[np.abs((np.array(a)-np.array(b))).sum() for a in position_a] for b in position_b]
print(cost_martix2)
row_ind2, col_ind2 = linear_sum_assignment(cost_martix2)
print(row_ind2)
print(col_ind2)
for x,y in zip(row_ind, col_ind):
print("列表B中的%s,应该与列表A中坐标%s匹配,距离消耗为%d"%(position_b[x],position_a[y],cost_martix2[x][y]))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)