scipy.sparse.csgraph.

min_weight_full_bipartite_matching#

scipy.sparse.csgraph.min_weight_full_bipartite_matching(биадъютансность, максимизировать=False)#

Возвращает минимальное весовое полное соответствие двудольного графа.

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

Параметры:

биадъютансностьразреженный массив или матрица: Биассоциированная матрица двудольного графа: разреженный массив в формате CSR, CSC или COO, строки которого представляют одну долю графа, а столбцы представляют другую долю. Ребро между двумя вершинами указывается соответствующим элементом в матрице, а вес ребра задаётся значением этого элемента. Это не следует путать с полной матрицей смежности графа, так как нам нужна только подматрица, определяющая двудольную структуру.
максимизироватьbool (по умолчанию: False): Вычисляет максимальное взвешенное соответствие, если истинно.

Возвращает:

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

Примечания

Пусть \(G = ((U, V), E)\) должен быть взвешенным двудольным графом с ненулевыми весами \(w : E \to \mathbb{R} \setminus \{0\}\). Затем эта функция создает соответствующий \(M \subseteq E\) с мощностью

\[\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),\]

который минимизирует сумму весов ребер, включенных в сопоставление, \(\sum_{e \in M} w(e)\), или вызывает ошибку, если такого соответствия не существует.

Когда \(\lvert U \rvert = \lvert V \rvert\), это обычно называется идеальным соответствием; здесь, поскольку мы разрешаем \(\lvert U \rvert\) и \(\lvert V \rvert\) чтобы различаться, мы следуем Карпу [1] и ссылаться на сопоставление как полный.

Эта функция реализует алгоритм LAPJVsp [2], сокращение от "Linear assignment problem, Jonker–Volgenant, sparse".

Решаемая задача эквивалентна задаче прямоугольного линейного назначения. [3] Таким образом, эту функцию можно использовать для решения тех же задач, что и scipy.optimize.linear_sum_assignment. Эта функция может работать лучше, когда входные данные плотные, или для определенных типов входных данных, таких как те, для которых \((i, j)\)i-я запись — это расстояние между двумя точками в евклидовом пространстве.

Если полного соответствия не существует, эта функция вызывает исключение ValueError. Для определения размера наибольшего соответствия в графе, см. maximum_bipartite_matching.

Мы требуем, чтобы веса были ненулевыми только для избежания проблем с обработкой явных нулей при преобразовании между различными разреженными представлениями. Нулевые веса можно обработать, добавив константу ко всем весам, чтобы результирующая матрица не содержала нулей.

Если возможны несколько допустимых решений, вывод может варьироваться в зависимости от версии SciPy и Python.

Ссылки

[1]

Ричард Мэннинг Карп: Алгоритм решения задачи назначения m x n за ожидаемое время O(mn log n). Networks, 10(2):143-152, 1980.

[2]

Рой Йонкер и Антон Волгенаант: Алгоритм кратчайшего увеличивающего пути для плотных и разреженных задач линейного назначения. Computing 38:325-340, 1987.

[3]

https://en.wikipedia.org/wiki/Assignment_problem

Примеры

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import min_weight_full_bipartite_matching

Рассмотрим сначала пример, в котором все веса равны:

>>> biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])

Здесь мы получаем идеальное соответствие графа:

>>> print(min_weight_full_bipartite_matching(biadjacency)[1])
[2 0 1]

То есть первая, вторая и третья строки соответствуют третьему, первому и второму столбцам соответственно. Обратите внимание, что в этом примере 0 во входной матрице не соответствуют ребру с весом 0, а скорее паре вершин, не соединённых ребром.

Также обратите внимание, что в этом случае выходные данные соответствуют результату применения maximum_bipartite_matching:

>>> from scipy.sparse.csgraph import maximum_bipartite_matching
>>> biadjacency = csr_array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])
>>> print(maximum_bipartite_matching(biadjacency, perm_type='column'))
[2 0 1]

Когда доступны несколько ребер, предпочтение отдается тем с наименьшими весами:

>>> biadjacency = csr_array([[3, 3, 6], [4, 3, 5], [10, 1, 8]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(col_ind)
[0 2 1]

Общий вес в этом случае составляет \(3 + 5 + 1 = 9\):

>>> print(biadjacency[row_ind, col_ind].sum())
9

Когда матрица не квадратная, т.е. когда два раздела имеют разную мощность, соответствие имеет размер меньшего из двух разделов:

>>> biadjacency = csr_array([[0, 1, 1], [0, 2, 3]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[0 1] [2 1]
>>> biadjacency = csr_array([[0, 1], [3, 1], [1, 4]])
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[0 2] [1 0]

Когда одна или обе разделы пусты, сопоставление также пусто:

>>> biadjacency = csr_array((2, 0))
>>> row_ind, col_ind = min_weight_full_bipartite_matching(biadjacency)
>>> print(row_ind, col_ind)
[] []

В общем случае мы всегда достигнем той же суммы весов, как если бы использовали scipy.optimize.linear_sum_assignment но обратите внимание, что для него отсутствующие ребра представлены элементом массива float('inf'). Давайте сгенерируем случайный разреженный массив с целочисленными элементами от 1 до 10:

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from scipy.optimize import linear_sum_assignment
>>> sparse = random_array((10, 10), rng=42, density=.5, format='coo') * 10
>>> sparse.data = np.ceil(sparse.data)
>>> dense = sparse.toarray()
>>> dense = np.full(sparse.shape, np.inf)
>>> dense[sparse.row, sparse.col] = sparse.data
>>> sparse = sparse.tocsr()
>>> row_ind, col_ind = linear_sum_assignment(dense)
>>> print(dense[row_ind, col_ind].sum())
25.0
>>> row_ind, col_ind = min_weight_full_bipartite_matching(sparse)
>>> print(sparse[row_ind, col_ind].sum())
25.0