WikiDer > Ungarischer Algorithmus
Es Ungarischer Algorithmus ist ein kombinatorischOptimierungsalgorithmus das ein Zuordnungsproblem in einer Reihenfolge löst . Die erste Version, bekannt als die Ungarische Methode, wurde konzipiert und herausgegeben von Harold Kuhn im 1955. Diese Version wurde bearbeitet von James Munkres im 1957 und ist seitdem Ungarischer Algorithmus, es Munkres-Zuordnungsalgorithmus wenn es Kuhn-Munkres-Algorithmus erwähnt.
Der von Kuhn entwickelte Algorithmus basierte weitgehend auf der Arbeit von zwei anderen ungarisch Mathematiker: Denes König und Jenő Egervary.
Beispiel: ein Minimierungsproblem
Sie hat gegeben Arbeitskräfte, Aufgaben und a Matrix, die die Kosten jeder möglichen Zuweisung einer Aufgabe an eine Arbeitskraft enthält. Nun soll eine Zuteilung mit minimalen Kosten gefunden werden.
Zunächst wird das Problem in ein Array geschrieben:
1 2 3 4 ein a1 a2 a3 a4 b b1 b2 b3 b4 c c1 c2 c3 c4 d d1 d2 d3 d4
Dabei sind a, b, c und d die Arbeiter, die die Aufgaben 1, 2, 3 und 4 ausführen müssen. a1, a2, a3 und a4 stellen die Kosten dar, wenn Person a Aufgabe 1, 2, 3 bzw. 4 ausführt. Analog für die anderen Elemente. Die Matrix ist quadratisch, was bedeutet, dass jeder Arbeiter nur eine Aufgabe ausführen kann und jede Aufgabe ausgeführt wird.
Als nächstes wenden wir Zeilenoperationen auf diese Matrix an. Das niedrigste aller ai mit i = 1, 2, 3 oder 4 wird gewählt. Dieser Wert wird von den anderen Elementen in dieser Zeile abgezogen. Dadurch wird sichergestellt, dass sich in dieser Zeile mindestens eine Null befindet. Mehrere Nullen werden erhalten, wenn in dieser Zeile gleiche Elemente mit dem niedrigsten Wert vorhanden sind. Dieser Vorgang wird für jede Reihe wiederholt. Jetzt haben wir also eine Matrix mit mindestens einer Null in jeder Zeile. Jetzt versuchen wir, die Arbeiter so zuzuteilen, dass jeder Arbeiter nur eine Aufgabe erledigt und die Kosten für jede Aufgabe null sind. Dies ist unten dargestellt.
1 2 3 4 ein 0 a2' 0' a4' b b1' b2' b'3 0' c 0' c2' c3' c4' d d1' 0' d3' d4'
Die mit 0' bezeichneten Nullen sind die zugewiesenen Aufgaben.
In manchen Fällen ist eine Zuordnung nicht möglich:
1 2 3 4 ein 0 a2' a3' a4' b b1' b2' b'3 0' c 0' c2' c3' c4' d d1' 0' d3' d4'
Beachten Sie, dass Aufgabe 1 sowohl von Arbeiter a als auch von Arbeiter c effizient erledigt werden kann. Beide können jedoch nicht derselben Aufgabe zugeordnet werden. Beachten Sie auch, dass niemand Aufgabe 3 effizient erledigt. Um dies zu vermeiden, wiederholen wir das obige Vorgehen für alle Spalten und prüfen dann, ob eine Zuordnung möglich ist. In den meisten Fällen führt dies zum Ergebnis, es kann jedoch trotzdem vorkommen, dass keine Zuordnung vorgenommen werden kann. Dann muss wie folgt vorgegangen werden:
Versuchen Sie, so viele Aufgaben wie möglich zuzuweisen und gehen Sie dann wie folgt vor (vergeben Sie Aufgaben in den Zeilen 2, 3 und 4)
1 2 3 4 ein 0 a2' a3' a4' b b1' b2' b'3 0' c 0' c2' c3' c4' d d1' 0' d3' d4'
Markieren Sie alle Zeilen, die keine Zuweisungen haben (Zeile 1). Markieren Sie dann alle Spalten mit einer Null in dieser Zeile (Spalte 1). Markieren Sie dann alle Zeilen, die Zuweisungen in der angegebenen Spalte haben (Zeile 3). Markieren Sie dann alle Spalten, die in den angegebenen Zeilen Zuweisungen haben. Wiederholen, bis sich eine geschlossene Schleife gebildet hat.
× 1 2 3 4 ein 0 a2' a3' a4' × b b1' b2' b'3 0' c 0' c2' c3' c4' × d d1' 0' d3' d4'
Ziehen Sie nun Linien durch alle markierten Spalten und unmarkierten Zeilen. (Anstatt Linien zu zeichnen, werden die Elemente rot markiert.)
× 1 2 3 4 ein 0 a2' a3' a4' × b b1' b2' b'3 0' c 0' c2' c3' c4' × d d1' 0' d3' d4'
Aus den verbleibenden Elementen wird der niedrigste Wert gesucht. Ziehen Sie diesen Wert von allen nicht gelöschten Elementen ab. Addieren Sie diesen Wert zu den Elementen, die sich am Schnittpunkt zweier Linien befinden. Lassen Sie die anderen Elemente unverändert. Ordnen Sie nun die Aufgaben gemäß den obigen Regeln zu. Wiederholen Sie diesen Vorgang, bis eine Zuordnung möglich ist.