quadratic_assignment(method=’2opt’)#
- scipy.optimize.quadratic_assignment(A, B, method='faq', options=None)
Löst das quadratische Zuordnungsproblem (ungefähr).
Diese Funktion löst das quadratische Zuordnungsproblem (QAP) und das Graph Matching Problem (GMP) mithilfe des 2-opt-Algorithmus [1].
Das quadratische Zuordnungsproblem löst Probleme der folgenden Form
\[\begin{split}\min_P & \ {\ \text{trace}(A^T P B P^T)}\\ \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\\end{split}\]wobei \(\mathcal{P}\) die Menge aller Permutationsmatrizen ist und \(A\) und \(B\) quadratische Matrizen sind.
Graph-Matching versucht, die gleiche Zielfunktion zu *maximieren*. Dieser Algorithmus kann als das Finden der Ausrichtung der Knoten zweier Graphen betrachtet werden, die die Anzahl der induzierten Kanten-Diskrepanzen minimiert, oder im Fall von gewichteten Graphen die Summe der quadrierten Kanten-Gewichts-Differenzen.
Beachten Sie, dass das quadratische Zuordnungsproblem NP-schwer ist. Die hier angegebenen Ergebnisse sind Annäherungen und keine Garantie für Optimalität.
- Parameter:
- A2-D-Array, quadratisch
Die quadratische Matrix \(A\) in der obigen Zielfunktion.
- B2-D-Array, quadratisch
Die quadratische Matrix \(B\) in der obigen Zielfunktion.
- methodstr in {‘faq’, ‘2opt’} (Standard: ‘faq’)
Der Algorithmus, der zum Lösen des Problems verwendet wird. Dies ist die metodienspezifische Dokumentation für „2opt“. „faq“ ist ebenfalls verfügbar.
- Rückgabe:
- resOptimizeResult
OptimizeResult, das die folgenden Felder enthält.- col_ind1-D-Array
Spaltenindizes, die der besten gefundenen Permutation der Knoten von B entsprechen.
- funfloat
Der Zielfunktionswert der Lösung.
- nitint
Die Anzahl der während der Optimierung durchgeführten Iterationen.
Siehe auch
Für die Dokumentation der restlichen Parameter siehe
scipy.optimize.quadratic_assignment- Optionen:
- ——-
- maximizebool (Standard: False)
Maximiert die Zielfunktion, wenn
True.- rng{None, int,
numpy.random.Generator}, optional Zustand des pseudozufälligen Zahlen-Generators. Siehe
quadratic_assignmentfür Details.- partial_match2-D-Array von ganzen Zahlen, optional (Standard: None)
Fixiert einen Teil der Zuordnung. Auch bekannt als „Seed“ [2].
Jede Zeile von partial_match gibt ein Paar zugeordneter Knoten an: Knoten
partial_match[i, 0]von A wird dem Knotenpartial_match[i, 1]von B zugeordnet. Das Array hat die Form(m, 2), wobeimnicht größer ist als die Anzahl der Knoten, \(n\).Hinweis
partial_match muss nach der ersten Spalte sortiert sein.
- partial_guess2-D-Array von ganzen Zahlen, optional (Standard: None)
Eine Vermutung für die Zuordnung zwischen den beiden Matrizen. Im Gegensatz zu partial_match fixiert partial_guess die Indizes nicht; diese können immer noch optimiert werden.
Jede Zeile von partial_guess gibt ein Paar von zugeordneten Knoten an: Knoten
partial_guess[i, 0]von A wird dem Knotenpartial_guess[i, 1]von B zugeordnet. Das Array hat die Form(m, 2), wobeimnicht größer als die Anzahl der Knoten, \(n\), ist.Hinweis
partial_guess muss nach der ersten Spalte sortiert sein.
Hinweise
Dies ist ein gieriger Algorithmus, der ähnlich wie Bubble Sort funktioniert: Beginnend mit einer Anfangspermutation tauscht er iterativ Paare von Indizes aus, um die Zielfunktion zu verbessern, bis keine solchen Verbesserungen mehr möglich sind.
Referenzen
[1]„2-opt,“ Wikipedia. https://en.wikipedia.org/wiki/2-opt
[2]D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, „Seeded graph matching“, Pattern Recognit. 87 (2019): 203-215, https://doi.org/10.1016/j.patcog.2018.09.014