Der ungarische Algorithmus ist ein kombinatorischer Optimierungsalgorithmus, der das Problem der bipartiten Anpassung mit maximalem Gewicht in der Polynomzeit löst und die spätere Entwicklung der wichtigen Primal-Dual-Methode vorwegnimmt . Der Algorithmus wurde 1955 von Harold Kuhn entwickelt und veröffentlicht, der den Namen "Ungarischer Algorithmus" erhielt, da der Algorithmus auf den früheren Arbeiten zweier ungarischer Mathematiker basierte: Dénes Kőnig und Jenő Egerváry. Munkres überprüfte den Algorithmus 1957 und stellte fest, dass es tatsächlich Polyzeit ist. Seitdem ist der Algorithmus auch als Kuhn-Munkres-Algorithmus bekannt.
Obwohl der Ungar die Grundidee der Primal-Dual-Methode enthält, löst er das Problem der bipartiten Anpassung mit maximalem Gewicht direkt, ohne einen linearen Programmierapparat (LP) zu verwenden. Auf die folgende Frage antwortete Jukka Suomela
Natürlich können Sie jede LP mit einem Allzweck-LP-Löser lösen, aber spezialisierte Algorithmen weisen in der Regel eine viel bessere Leistung auf. [...] Sie können auch häufig Probleme vermeiden, z. B. die Verwendung genauer rationaler Zahlen im Vergleich zu Gleitkommazahlen. alles kann leicht mit ganzen Zahlen gemacht werden.
Mit anderen Worten, Sie müssen sich keine Gedanken darüber machen, wie Sie eine Rational / Floating-Point-Lösung aus dem LP-Solver runden können, um eine perfekte Übereinstimmung der maximalen Gewichtung eines gegebenen zweigeteilten Graphen zu erhalten.
Meine Frage ist folgende:
Gibt es eine Verallgemeinerung des ungarischen Algorithmus, die für allgemeine ungerichtete Graphen ohne die Verwendung von LP-Maschinen ähnlich dem Geist des ursprünglichen ungarischen Algorithmus funktioniert ?
Ich würde lieber eine moderne und leicht lesbare Darstellung als ein kompliziertes Originalpapier vorziehen. Aber jeder Zeiger wird sehr geschätzt!
Vielen Dank im Voraus und Frohe Weihnachten !!!
Update: Die Frage wird von Arman unten schön beantwortet. Ich möchte nur darauf hinweisen, dass eine weitere gute Quelle zum Studium des Edmonds-Blossom-Algorithmus (für den gewichteten Fall) Kapitel 11 der kombinatorischen Optimierung von Korte und Vygen ist . Google Buch zeigt eigentlich fast alle Teile, die ich brauche, um den Algorithmus zu verstehen.
Antworten:
Der Matching-Algorithmus von Edmonds (auch als Blossom-Algorithmus bezeichnet) löst die maximale Übereinstimmung in allgemeinen Diagrammen. Tatsächlich handelt es sich um eine Verallgemeinerung der Wechselpfadmethode. (Ich bin mir nicht sicher, wie die Methode heißt, aber es sollte sich um die König-Hall-Methode handeln.) Es werden im Wesentlichen Erweiterungspfade gefunden (siehe Wikipedia-Seite: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm ), um den Algorithmus zu erweitern Der aktuelle Abgleich wird beendet, wenn keine zusätzlichen Pfade mehr vorhanden sind. In allgemeinen Grafiken tritt das einzige Problem in ungeraden Zyklen auf. Im Matching-Algorithmus der Edmonds werden ungerade Zyklen kontrahiert (Blüten) und aufgewendet, um eine Lösung zu erhalten.
Es gibt auch eine Entsprechung zwischen dem Blossom-Algorithmus und der Primal Dual-Methode. Ungerade Zyklen verursachen gebrochene Extrempunkte. Deshalb addieren wir für jeden ungeraden Zyklus sogenannte Blütenungleichungen.
Mit diesem Ansatz könnten auch minimale gewichtete perfekte Anpassungs- und maximale Gewichtsanpassungsprobleme behandelt werden.
Einzelheiten zum Algorithmus finden Sie unter http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
Die mathematische Formulierung und die entsprechende Primal-Dual-Methode finden Sie unter http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf
quelle
Vor zwei Jahren, als ich den (ungewichteten) Blütenalgorithmus erforschte, fand ich zwei großartige Notensätze, einen von Tarjan und einen von Zwick. Sie ließen den ungewichteten Fall ziemlich einfach erscheinen, und ich konnte ihn in Mathematica mithilfe von Rekursion implementieren. Es funktioniert ganz gut
Die Notizen, die ich nützlich fand, sind
http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf und http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/ tarjan-blossom.pdf
Sie fassen alles auf sehr einfache Begriffe zusammen, die es einem erlauben, rekursiv zu denken und dann, wie erwähnt, rekursiv zu programmieren.
Ich denke, es sollte alles in dem gewichteten Fall funktionieren, den ich jetzt implementieren möchte.
quelle