python - 为线性总和分配构建成本矩阵的最有效方法?
问题描述
假设我们想用 scipy 解决线性求和分配,并且分配的成本可以从欧几里德距离构建。
因此,在m
工人W=[j_1, ..., j_m]
和n
任务T=[t_1, ..., t_n]
中,成本矩阵由下式给出
cost_matrix = np.array([
[np.linalg.norm(x - y) for x in W] for y in T
])
这看起来计算量很大,效率不高。有没有一种 numpy/scipy 方法可以更好更快地做到这一点?
工作示例:
import numpy as np
from scipy.optimize import linear_sum_assignment
np.random.seed(0)
# define tasks
t = np.random.rand(5)
# define workers
w = np.random.rand(3)
cost_matrix = np.array([[np.linalg.norm(x-y) for x in w] for y in t])
>>> linear_sum_assignment(cost_matrix)
(array([1, 2, 4]), array([2, 0, 1]))
解决方案
我相信您正在寻找的是cdist
. Scipy cdist
Y = cdist(XA, XB, 'euclidean')
这是您的工作代码示例:
import numpy as np
from scipy.optimize import linear_sum_assignment
from scipy.spatial.distance import cdist
np.random.seed(0)
# define tasks
t = np.random.rand(5)
# define workers
w = np.random.rand(3)
# cost_matrix = np.array([[np.linalg.norm(x-y) for x in w] for y in t])
cost_matrix = cdist(np.array([t]).T, np.array([w]).T, 'euclidean')
linear_sum_assignment(cost_matrix)
推荐阅读
- c# - 刚性物体从侧面进入盒子对撞机的问题
- javascript - 我正在尝试在我的 React Hangman App 中为一组字母设置动画
- networking - ngrok 连接线的含义
- android - 使用 frida 和 java 脚本挂钩受保护的 APK 遇到 attach() 错误
- c++ - 带有 CMake 的 Swig 无法找到标头包含
- c# - 如何根据 MVC 中的选择下拉列表在表格上显示特定项目?
- pandas - 将 href 链接添加到 pandas 数据框
- flutter - 提供者在 Flutter 中未从 StreamProvider 中找到提供者
- excel - 如何在值上自动插入 SUM 公式
- ios - 自定义视图不想加载覆盖 loadView