linear_sum_assignment给出不正确的结果
linear_sum_assignment给出不正确的结果
提问于 2022-03-19 23:47:23
当我尝试使用scipy.optimize.linear_sum_assignment时，它给出了总成本为15的赋值向量[0 2 3 1]。
但是，从成本矩阵c中可以看到，对于第二个任务，第5个代理的成本为1。因此，预期的任务应该是[0 3 None 2 1] (总成本9)。
为什么linear_sum_assignment不返回最佳作业？
from scipy.optimize import linear_sum_assignment
c = [
[1, 5, 9, 5],
[5, 8, 3, 2],
[3, 2, 6, 8],
[7, 3, 5, 4],
[2, 1, 9, 9],
]
results = linear_sum_assignment(c)
print(results[1]) # [0 2 3 1]回答 1
Stack Overflow用户
发布于 2022-03-20 00:22:38
linear_sum_assignment返回两个数组的元组。这些是赋值的行索引和列索引。对于您的示例(将c转换为numpy数组)：
In [51]: c
Out[51]:
array([[1, 5, 9, 5],
[5, 8, 3, 2],
[3, 2, 6, 8],
[7, 3, 5, 4],
[2, 1, 9, 9]])
In [52]: row, col = linear_sum_assignment(c)
In [53]: row
Out[53]: array([0, 1, 3, 4])
In [54]: col
Out[54]: array([0, 2, 3, 1])来自row和col的相应索引对给出了所选条目。也就是说，所选条目的索引是(0，0)，(1，2)，(3，3)和(4，1)。正是这些对是“作业”。
与这一转让有关的总额为9：
In [55]: c[row, col].sum()
Out[55]: 9在问题的原始版本中(但自编辑后)，您似乎想知道每一列的行索引，因此您希望得到0、4、1、3。您想要的值是row，但顺序不是您所期望的，因为col中的索引并不是简单的0、1、2、3。要以预期的形式得到结果，必须根据col中索引的顺序重新排序row中的值。有两种方法可以做到这一点。
第一：
In [56]: result = np.zeros(4, dtype=int)
In [57]: result[col] = row
In [58]: result
Out[58]: array([0, 4, 1, 3])第二：
In [59]: result = row[np.argsort(col)]
In [60]: result
Out[60]: array([0, 4, 1, 3])请注意，linear_sum_assignment文档字符串中的示例可能具有误导性；因为它只在python会话中显示col_ind，它给人的印象是col_ind是“答案”。但是，通常情况下，答案涉及两个返回的数组。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71542970
复制相关文章
相似问题
腾讯云开发者
