Glossar · approach
Ungarische Methode
Kombinatorischer Algorithmus, der das Zuordnungsproblem (n×n-Kostenmatrix, Eins-zu-eins minimaler-Kosten-Matching) in polynomieller Zeit O(n³) löst; Kuhn (1955) und Munkres (1957).
Hungarian MethodHungarian AlgorithmKuhn-Munkres-Algorithmus
Die Ungarische Methode (auch Kuhn-Munkres-Algorithmus) ist der kombinatorische Optimierungsalgorithmus, der das Zuordnungsproblem — Eins-zu-eins-Zuordnung von n Arbeitern/Ressourcen zu n Aufgaben unter einer n×n-Kostenmatrix mit minimierter Gesamtkost — in polynomieller Zeit O(n³) löst. Harold Kuhn stellte den Algorithmus 1955 in *Naval Research Logistics Quarterly* vor; der Name wurde zu Ehren der bipartiten Matching-Sätze gegeben, die die ungarischen Mathematiker Dénes König und Jenő Egerváry zu Beginn des 20. Jahrhunderts entwickelten. James Munkres goss den Algorithmus 1957 in eine vollständig formale polynomielle O(n³)-Prozedur, daher die moderne alternative Bezeichnung Kuhn-Munkres-Algorithmus. Arbeitsweise: subtrahiere Zeilen-/Spaltenminima, finde mit dem König-Egerváry-Satz ein maximales Matching auf den Null-Kosten-Zellen, wenn nicht perfekt wende eine sequentielle Überdeckungsprozedur an, wiederhole bis perfekt. Garantiertes Optimum, polynomielle Zeit, kombinatorisch. Moderne schnellere Alternativen: LAP — shortest augmenting path (Jonker und Volgenant 1987, praktisch 5-20-mal schneller); Auction-Algorithmus (Bertsekas 1988, parallelisierungsfreundlich). Kuhn (1955), Munkres (1957).
Örnek
Bei einer 5×5-Kostenmatrix, in der jeder Techniker eine unterschiedliche Fahrzeit zu jedem Kunden hat, findet die Ungarische Methode in Sekunden die Eins-zu-eins-Zuordnung, die die Gesamtfahrzeit minimiert; 15-30% besser als die intuitive Zuordnung.