scipy.optimize.

linear_sum_assignment#

scipy.optimize.linear_sum_assignment()#

Löst das lineare Summenzuweisungsproblem.

Parameter:

cost_matrixarray: Die Kostenmatrix des bipartiten Graphen.
maximizebool (Standard: False): Berechnet eine maximale Gewichtsübereinstimmung, wenn True.

Rückgabe:

row_ind, col_indarray: Ein Array von Zeilenindizes und eines der entsprechenden Spaltenindizes, die die optimale Zuweisung ergeben. Die Kosten der Zuweisung können als cost_matrix[row_ind, col_ind].sum() berechnet werden. Die Zeilenindizes werden sortiert; im Falle einer quadratischen Kostenmatrix sind sie gleich numpy.arange(cost_matrix.shape[0]).

Siehe auch

scipy.sparse.csgraph.min_weight_full_bipartite_matching: für sparse Eingaben

Hinweise

Das lineare Summenzuweisungsproblem [1] ist auch bekannt als minimale Gewichtsübereinstimmung in bipartiten Graphen. Eine Probleminstanz wird durch eine Matrix C beschrieben, wobei jedes C[i,j] die Kosten für die Zuordnung des Knotens i der ersten Menge (ein „Arbeiter“) und des Knotens j der zweiten Menge (ein „Job“) ist. Das Ziel ist es, eine vollständige Zuordnung von Arbeitern zu Jobs mit minimalen Kosten zu finden.

Formal sei X eine boolesche Matrix, wobei \(X[i,j] = 1\) genau dann, wenn Zeile i Spalte j zugeordnet ist. Dann hat die optimale Zuweisung die Kosten

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

wobei im Fall einer quadratischen Matrix X jeder Zeile genau eine Spalte und jeder Spalte genau eine Zeile zugeordnet ist.

Diese Funktion kann auch eine Verallgemeinerung des klassischen Zuweisungsproblems lösen, bei dem die Kostenmatrix rechteckig ist. Wenn sie mehr Zeilen als Spalten hat, muss nicht jede Zeile einer Spalte zugeordnet werden und umgekehrt.

Diese Implementierung ist ein modifizierter Jonker-Volgenant-Algorithmus ohne Initialisierung, beschrieben in ref. [2].

Hinzugefügt in Version 0.17.0.

Referenzen

[1]

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

[2]

DF Crouse. On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 52(4):1679-1696, August 2016, DOI:10.1109/TAES.2016.140952

Beispiele

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