scipy.optimize.

linear_sum_assignment#

scipy.optimize.linear_sum_assignment()#

Решить задачу линейного назначения с минимальной суммой.

Параметры:
cost_matrixмассив

Матрица стоимости двудольного графа.

максимизироватьbool (по умолчанию: False)

Вычисляет максимальное взвешенное соответствие, если истинно.

Возвращает:
row_ind, col_indмассив

Массив индексов строк и соответствующих индексов столбцов, дающий оптимальное назначение. Стоимость назначения может быть вычислена как cost_matrix[row_ind, col_ind].sum(). Индексы строк будут отсортированы; в случае квадратной матрицы затрат они будут равны numpy.arange(cost_matrix.shape[0]).

Смотрите также

scipy.sparse.csgraph.min_weight_full_bipartite_matching

для разреженных входных данных

Примечания

Задача линейного назначения [1] также известно как минимальное весовое сопоставление в двудольных графах. Экземпляр задачи описывается матрицей C, где каждый C[i,j] — это стоимость сопоставления вершины i первого долевого множества ('работник') и вершины j второго множества ('задача'). Цель — найти полное назначение работников задачам с минимальной стоимостью.

Формально, пусть X — булева матрица, где \(X[i,j] = 1\) тогда и только тогда, когда строка i назначена столбцу j. Тогда оптимальное назначение имеет стоимость

\[\min \sum_i \sum_j C_{i,j} X_{i,j}\]

где, в случае когда матрица X квадратная, каждая строка назначается ровно одному столбцу, а каждый столбец — ровно одной строке.

Эта функция также может решать обобщение классической задачи назначения, где матрица стоимостей прямоугольная. Если в ней больше строк, чем столбцов, то не каждая строка должна быть назначена столбцу, и наоборот.

Эта реализация представляет собой модифицированный алгоритм Йонкера-Волгенанта без инициализации, описанный в ссылке. [2].

Добавлено в версии 0.17.0.

Ссылки

[2]

DF Crouse. О реализации алгоритмов назначения для 2D прямоугольников. IEEE Transactions on Aerospace and Electronic Systems, 52(4):1679-1696, август 2016, DOI:10.1109/TAES.2016.140952

Примеры

>>> import numpy as np
>>> cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])
>>> from scipy.optimize import linear_sum_assignment
>>> row_ind, col_ind = linear_sum_assignment(cost)
>>> col_ind
array([1, 0, 2])
>>> cost[row_ind, col_ind].sum()
5
На этой странице