Самый эффективный способ построения матрицы затрат для линейного назначения суммы?

Question

Предположим, что мы хотим решить линейное назначение суммы с помощью 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
])

Это выглядит тяжелым в вычислительном отношении и не очень эффективным. Есть ли какой-нибудь тупой / скучный способ сделать это лучше и быстрее?

---

Рабочий пример:

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

Answer 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)

Answer 2

Это может быть не самый эффективный способ, но итерация передается numpy, поэтому это может быть быстрее:

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)

W, T = np.meshgrid(w, t)
cost_matrix = abs(T-W)