Ungarische Methode

Methode mit Formeln

Maschinelle Lösung

Für die Zuordnung der Sterne und das Speichern der Strich-Markierungen werden zwei Vektoren benötigt. Dabei bedeutet s_j = 0, dass in Spalte j noch kein Stern steht, während z_i = 0 heißt, dass in der i-ten Zeile keine Null mit Strich steht. Andernfalls geben s_j und z_i die Position des Sterns oder Strichs in Spalte j bzw. Zeile i an. Zeile i ist genau dann randmarkiert, wenn z_i > 0 ist. Spalte j ist genau dann randmarkiert, wenn gilt.

Um die Komplexität gering zu halten und auf zu senken, werden für die maschinelle Rechnung zusätzliche Vektoren für die Knotenpotentiale benutzt. Schritt 1 wird wie folgt ersetzt:

Für j = 1, ..., n setze .

Für i = 1, ..., n setze .

In den Schritten 2–10 wird jeweils mit den reduzierten Gewichten gerechnet. Insbesondere reduziert sich Schritt 6 zu

Für j = 1, ..., n:

a) Falls Spalte j nicht randmarkiert ist, addiere h zu v_j .

b) Falls Zeile j randmarkiert ist, subtrahiere h von u_j .

Außerdem kann die Minimumsuche in Schritt 5 mittels eines zusätzlichen Vektors vereinfacht werden. Dieser enthalte für jede Zeile das Minimum der nicht randmarkierten Elemente. Somit wird , wobei randmarkierte Zeilen auszuschließen sind. Die Initialisierung dieses Vektors m kann in Schritt 3 oder 4 erfolgen. Falls in Schritt 8 eine Spaltenmarkierung aufzuheben ist, so erfordert die Anpassung von m nur linearen Aufwand, nämlich Vergleich mit den Einträgen der betreffenden Spalte und ggf. deren Übernahme nach m.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Ungarische Methode aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung