Diskussion:Ungarische Methode

Matchings in bipartiten Graphen

Ich habe im Studium einen Algorithmus zur Ermittlung eines Maximum Matchings in einem bipartiten Graphen kennengelernt, der auch Ungarische Methode genannt wurde. Vermutlich besteht ein Zusammenhang mit dem hier Beschriebenen. Kennt jemand diesen Zusammenhang? --HeikoTheissen 08:36, 4. Sep 2006 (CEST)

Das Bild scheint einen Ungarischen Wald zu zeigen: Algorithmus_von_Hopcroft_und_Karp#Ungarische_W.C3.A4lder. Beides hat mit Paarungen im bipartiten Graphen zu tun, nur das die Ungarische Methode gewichtete Kanten nutzt und der Algorithmus von Hopcroft und Karp ungewichtete. (nicht signierter Beitrag von 212.202.224.148 (Diskussion) 09:59, 12. Aug. 2015 (CEST))

Soweit ich das ganze verstanden habe, wird bei dem Paarungsalgorithmus jede Kante mit 1 gewichtet. --Pythonpauker (Diskussion) 12:08, 17. Sep. 2024 (CEST)

Fehler in Matrix Y bei der Methode von Habr

Ich habe gerade mal die Matrix Y im Beispiel der Methode nach Habr nachgerechnet und komme zu folgendem Ergebnis:

-0.25    -0.25    -0.25    0.75
 0.5     -0.5      1.5    -1.5
 0.5      0.5     -1.5     0.5 
-0.75     0.25     0.25    0.25

Dann passen auch die Zeilen- und Spaltenmittelwerte. Die minimale Summe beträgt jetzt -4. Die optimalen Elemente bleiben aber die gleichen. Leider kann ich das Bild nicht direkt editieren, um den Fehler zu korrigieren.(nicht signierter Beitrag von 80.156.43.1 (Diskussion | Beiträge) 10:49, 23. Feb. 2007)

Korrekt! Der Fehler im Original liegt in der Ausgabefunktion. Die falschen Werte treten immer dort auf, wo mehr als 3 Zeichen ausgegeben werden müssten, beispielsweise steht "-0,3" statt "-0,25", was im printf aber 4 Zeichen wären. Ich weiß nicht, ob der Artikel nach dieser Seite beschrieben wurde, dort ist aber das gleiche falsche Bild: http://www.mathepedia.de/Ungarische_Methode.aspx (nicht signierter Beitrag von 62.159.185.194 (Diskussion | Beiträge) 18:09, 2. Feb. 2010 (CET))

Ich habe eine Tabelle erstellt und die Werte korrigiert. erledigtErledigt--Harald321 (Diskussion) 00:43, 24. Feb. 2015 (CET)

Falscher Fokus

Dieser Artikel fokussiert ausschließlich auf der Matrixinterpretation der ungarischen Methode. Sie wurde aber von Kuhn 1955 in seinem paper "The hungarian Method for the assignment problem" zuerst beschrieben und müsste daher zuerst graphentheoretisch beschrieben werden. Momentan ist der Artikel m.E. nur sehr bedingt zu gebrauchen, eine Überabreitung dringend nötig.(nicht signierter Beitrag von 92.76.124.77 (Diskussion | Beiträge) 09:12, 27. Jan. 2009)

Die Notwendigkeit einer Überarbeitung sehe ich unabhängig vom graphentheoretischen Gesichtspunkt ebenfalls, da das angegebene Verfahren („11 Schritte ...“) auch einiges Erraten zu erfordern scheint, zumindest in Punkt 8. Da ich derzeit nicht an Bücher wie „Mathematik für Ingenieure, Naturwissenschaftler, Ökonomen und Landwirte (MINÖL) Bd. 14“ und „Ergänzende Kapitel zu Bronstein/Semendjajew: Taschenbuch der Mathematik“ herankomme, muß ich die Überarbeitung auf mein Gedächtnis stützen. Im übrigen befürchte ich, daß der Aufwand des Verfahrens bei $n$ zuzuordnenden Dingen ${\mathcal {O}}(n^{4})$ wird, wenn die Matrix wie in Punkt 10 verändert wird. Für eine Handrechnung mag dieses Herangehen sinnvoll sein, da die Benutzung zusätzlicher Vektoren und die Verwendung von Differenzen statt der Matrixelemente fehlerträchtig wird. Beim maschinellen Rechnen zählt dieser Grund freilich nicht. Ich hoffe, meine Überarbeitung (angelehnt an „Bronstein“) wird akzeptiert.--Gandalf Mithrandir 14:01, 1. Feb. 2009 (CET)

Der in der englischen Seite großzügig zitierte Artikel von Andres Frank stellt den graphenbasierten Zugang knapp und übersichtlich dar und ordnet ihn historisch ein. U.A. stand die systematische Konstruktion des maximalen Matching per alternierenden Pfaden oder Bäumen ganz am Anfang der Entwicklung, jedoch taucht nichts davon im Artikel auf. Der Artikel demonstriert eher in einem langen Absatz die Unkenntnis dieses fundamentalen Bestandteils des Algorithmus. Ist die Frequenzmethode hier wirklich am richtigen Ort?--LutzL 16:28, 22. Feb. 2009 (CET)

Zuordnungsprobleme mit tausenden von Zeilen und Spalten lassen sich heute in Bruchteilen von Sekunden lösen, siehe die Monographie Assignment Problems von Burkard, Del Amico und Martello - die Frequenzmethode ist komplett outdated und sollte gestrichen werden. Programme zur Lösung von Zuordnungsproblemen findet man auf der Homepage zum oben zitierten Buch.--$Mathe94$ 19:44, 23. Feb. 2010 (CET)

Trägt der Artikel noch zurecht den Überarbeiten-Baustein oder wurde er nur vergessen? --Christian1985 (Diskussion) 17:44, 29. Feb. 2012 (CET)

Ja, der Zustand hat sich seither nicht verbessert. Nullgraph, Breitensuche, augmentierende Pfade sind Begriffe, die zentral für alle aktuellen Lösungsverfahren sind, fehlen aber noch vollständig.--LutzL (Diskussion) 12:56, 1. Mär. 2012 (CET)

Fehler in Maschinelle Lösung Schritt 6?

Zitat: "In den Schritten 2–10 wird jeweils mit $c_{ij}-u_{i}-v_{j}$ gerechnet. Insbesondere reduziert sich Schritt 6 zu

Für $j=1,\ldots ,n$:

a) Falls Spalte $j$ nicht randmarkiert ist, subtrahiere $h$ von $v_{j}$.

b) Falls Zeile $j$ randmarkiert ist, addiere $h$ zu $u_{j}$."

Sollte da nicht subtrahiere und addiere in a) und b) vertauscht werden, es wird ja $-u_{i}-v_{j}$ zur Matrix addiert? Die Elemente, die nicht randmarkiert werden sollen ja kleiner werden, also $v_{j}$ größer. -- Bernhard 12:36, 17. Feb. 2009 (CET)

Fehler in Methode mit Formeln?

Ich glaube in dem Abschnitte Methode mit Formeln ist ein kleiner Dreher drin:

Handrechnung

  1. Subtrahiere von C in jeder Zeile und Spalte das Minimum.
  2. Kennzeichne möglichst viele Nullen in der reduzierten Matrix mit einem Stern (\star), sofern weder in der Zeile noch in der Spalte bereits ein Stern steht.
  3. Konnten n Sterne gesetzt werden, dann kennzeichnen diese eine optimale Zuordnung, halt.
  4. Setze für jede Spalte, die einen Stern enthält, eine Randmarkierung (Pluszeichen).
  5. Ermittle das Minimum h der nicht randmarkierten Elemente.
  6. Bei h > 0 addiere h zu allen doppelt randmarkierten Elementen und subtrahiere h von allen nicht randmarkierten Elementen.
  7. Kennzeichne eine nicht randmarkierte Null mit einem Strich.
  8. Steht in der Zeile dieser Null bereits ein Stern, so lösche die Randmarkierung des Sterns, setze für diese Zeile eine Randmarkierung und gehe zum Schritt 5.
  9. Kennzeichne die Null mit einem Stern.
 10. Steht innerhalb dieser Spalte ein anderer Stern, etwa in einer Zeile i, so lösche diesen Stern, wähle in Zeile i die mit Strich versehene Null und gehe zu Schritt 9.
 11. Lösche sämtliche Striche und Zeilenmarkierungen und gehe zu Schritt 3.

Beim 10. Punkt müsste in der Zeile (statt in dieser Spalte) nach einem anderen Stern gesucht werden. Neben der Tatsache, dass das Beispiel darauf schließen lässt, lässt auch der Nebensatz darauf schließen.

Viele Grüße, V4mpire

-- V4mpire 16:19, 16. Sep. 2009 (CEST)

Übertragen von Hilfe_Diskussion:Einstellungen --Wiegels „…“ 16:38, 16. Sep. 2009 (CEST)

Skript von Triesch

Prof. E. Triesch: Zusammenfassung der Vorlesung Optimierung. RHTW Achen Sommersemester 2007. S. 37. (pdf)

Habe ich wieder rausgenommen. In dem Skript wird die Methode von Evergary zum bestimmen eines max. Matching als Ungarische Methode bezeichnet, was aber falsch ist, da die von Kuhn als ungarisch benannte Methode maximale gewichtete Matchings bestimmt. Die dualen Variablen und deren Berechnung ist im Skript nicht aufzufinden.--LutzL 10:04, 15. Apr. 2010 (CEST)

Ah ok, ist wohl ein gutes Beispiel warum Skripte nicht als Quellen nehmen sollte.--Schönen Gruß "Wohingenau" 17:46, 15. Apr. 2010 (CEST)

Dummy-Zeilen für n>k

Gibt es hierfür noch eine seriösere Quelle als Wikihow? Meines Erachtens ist dadurch nicht gewährleistet, dass die Zuordnung weiterhin optimal ist. Beispiel:

$\left({\begin{array}{ccc}1&2&3\\1&2&3\end{array}}\right)\Rightarrow \left({\begin{array}{ccc}1&2&3\\1&2&3\\3&3&3\end{array}}\right)\Rightarrow \left({\begin{array}{ccc}0&1&2\\0&1&2\\0&0&0\end{array}}\right)$

Hier kann man jetzt zum Beispiel der ersten Zeile die erste Spalte zuordnen und der letzten (Dummy-)Zeile die zweite Spalte. Übrig bleibt im nächsten Schritt $\left(2\right)$, also die (vormals) dritte Spalte für die zweite Zeile.

Entfernt man nun wieder den Dummy-Knoten hat man also ein Gewicht von $1+3=4>3=1+2$, also nicht die optimale Lösung. Ich sehe auch keinen Weg wie man sich beim raustreichen der Nullen für den "richtigen" Weg entscheiden soll.

--Cerotidinon (Diskussion) 15:03, 17. Apr. 2015 (CEST)

Woher kommt bei dir die zweite Umformung? Ist das die Reduktion der Spaltenelemente um das Spaltenminimum? Viele Grüße -- Phil1881 (Diskussion) 16:17, 17. Apr. 2015 (CEST)

Tatsächlich ist das die Reduktion der Zeilenelemente um das Zeilenminimum. In der englischen Wikipedia führt man das als ersten Schritt durch, da habe ich mich wohl verwirren lassen. Reduziert man zuerst die Spaltenelemente erhält man aber einen ähnlichen Widerspruch. Beispiel:

$\left({\begin{array}{ccc}1&2&3\end{array}}\right)\Rightarrow \left({\begin{array}{ccc}1&2&3\\3&3&3\\3&3&3\end{array}}\right)\Rightarrow \left({\begin{array}{ccc}0&0&0\\2&1&0\\2&1&0\end{array}}\right)$

Hier ordnet man z.B. der ersten Zeile die zweite Spalte zu und der zweiten Zeile die dritte Spalte. Übrig bleibt die erste Spalte für die dritte Zeile. Nach dem Entfernen der Dummy-Knoten hat man Gewicht $2>1$.

Danke für den Hinweis! --Cerotidinon (Diskussion) 14:33, 22. Apr. 2015 (CEST)

Hallo, ich glaube, du machst dir das Leben zu leicht ;-) Der Einfachheit halber beschränke ich mich auf die "11 Rechenschritte ohne Formeln": Nr. 6 funktioniert in deiner letzten Matrix nicht, also kommen die Schritte 8 bis 11 dran, wodurch (peu à peu) dafür gesorgt wird, dass eindeutige Nullen pro Zeile / Spalte erzeugt werden. Ich hoffe, das hilft :-) Viele Grüße -- Phil1881 (Diskussion) 15:59, 30. Apr. 2015 (CEST)

Ich habe es in der Uni so gelernt, dass man bei einem Minimierungsproblem in der Dummy Zeile Nullen schreibt, diese werden erst nach der Zeilen- und Spaltenreduktion hinzugefügt oder bei der Zeilen- und Spaltenreduktion nicht beachtet :

$\left({\begin{array}{ccc}1&2&3\\1&2&3\end{array}}\right)\Rightarrow \left({\begin{array}{ccc}1&2&3\\1&2&3\\0&0&0\end{array}}\right)\Rightarrow \left({\begin{array}{ccc}0&1&2\\0&1&2\\0&0&0\end{array}}\right)$

Jetzt streichen (rot makiert) wir alle Nullen möglichst clever, doppelt gestrichen (blau makiert).

$\left({\begin{array}{ccc}\color {red}0&\color {yellow}1&2\\\color {red}0&\color {yellow}1&2\\\color {blue}0&\color {red}0&\color {red}0\end{array}}\right)$

Jetzt Wählen wir die kleinste nicht gestrichene Zahl (Gelb makiert) und ziehe sie von den anderen nicht gestrichen Zahlen ab und addieren sie auf die doppelt gestrichene Zahl.

$\left({\begin{array}{ccc}\color {Orange}0&0&1\\0&\color {Orange}0&1\\1&0&\color {Orange}0\end{array}}\right)$ oder $\left({\begin{array}{ccc}0&\color {Orange}0&1\\\color {Orange}0&0&1\\1&0&\color {Orange}0\end{array}}\right)$

Das Ergebnis (orange makiert) ist 2+1+0 =3. --Harald321 (Diskussion) 21:30, 10. Aug. 2015 (CEST)

Online-Tool

Zur ungarischen Methode gibt es ein online Tool. [1] Man muss die Seite leider erst einmal zur Ausnahmeliste in Java hinzufügen.--Harald321 (Diskussion) 21:41, 24. Jun. 2015 (CEST)

Einleitung

In der Einleitung könnte man noch den Satz von König (Graphentheorie) einfügen.--Harald321 (Diskussion) 23:08, 24. Jun. 2015 (CEST)

Bereits von Jacobi entwickelt

Ich erinnere mich an einen Vortrag von Kuhn auf der EURO2010, bei der er zeigte, dass der von ihm entwickelte Algorithmus auch schon mal in einer Schrift von Jacobi zu finden war. Hier ist ein kleiner Teil des Vortrags: https://www.youtube.com/watch?v=iPNwfGwD6C8 Reicht das schon als Referenz hier, um die Info hinzuzufügen? --Sepp (Diskussion) 11:59, 10. Sep. 2015 (CEST)

Nachtrag: Hier schreibt auch noch jemand von diesem Vortrag. --Sepp (Diskussion) 12:04, 10. Sep. 2015 (CEST)

Die Englische Wikipedia schreibt dazu: "In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.[5]" mit Quelle http://www.lix.polytechnique.fr/~ollivier/JACOBI/jacobiEngl.htm die auch PDF-Scans der Arbeiten enthält. Die Schrift um die es geht ist dann vermutlich diese hier: "Jacobi, C. (1890). De aequationum differentialum systemate non normali ad formam normalem revocando, published by A. Clebsch, CGJ Jacobi’s gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. (nicht signierter Beitrag von 93.132.177.253 (Diskussion) 21:13, 16. Nov. 2019 (CET))

Fehler bei "11 Rechenschritte ohne Formeln"?

Bei Schritt 10 steht, dass man die Koeffizienten aus der Ursprungsmatrix übertragen muss. Aber man kann doch einfach die bisher ausgerechneten Koeffizienten verwenden, oder nicht? Auf jeden Fall kann man dann nicht von Schritt 11 direkt zu Schritt 6, sondern muss nochmal zu Schritt 1. Ich finde den Begriff "Ursprungsmatrix" äusserst irreführend. (nicht signierter Beitrag von 2A02:AA11:1200:1080:ED7C:AC16:B49D:5F64 (Diskussion | Beiträge) 20:10, 14. Sep. 2015 (CEST))