Ungarische Methode

Hilfsverfahren für komplexe Aufgabenstellungen

Beispiel 2 ist bequem in wenigen Sekunden zu lösen. Der Komplexitätsgrad des Auffindens der n unabhängigen Nullen (Rechenschritte Punkt 6) wächst mit der Dimension der n×n-Matrix allerdings rasch an. Ohne die entsprechende Software findet man mit einem händischen Verfahren bisweilen relativ lange keine Lösung. Zu einer Lösung, die in vielen Fällen bereits die Optimallösung darstellt, kommt man mit der Methode von Habr, die sich in einer Tabellenkalkulation einfacher programmieren lässt als die Ungarische Methode ab Rechenschritt 8. Die optimale Lösung andererseits durch zufällige Suche von Sets zulässiger Kombinationen zu finden, ist bei größeren Matrizen höchst unwahrscheinlich; für eine n×n-Matrix gibt es genau n! zulässiger Sets. Bereits bei einer 15×15-Matrix beträgt die Anzahl zulässiger Sets 1,3 Billionen. In der Regel sind höchstens einige, mindestens aber eine davon optimal.Je komplexer die Aufgabenstellungen sind, umso mehr muss auch der Aufwand zur Auffindung der optimalen Lösung in das Kalkül einbezogen werden. In der Praxis gibt man sich daher häufig mit suboptimalen Lösungen nahe dem vermuteten Optimum zufrieden, weil man die Gewähr hat, dass man diese viel rascher findet, was die Einbußen, die durch die Auswahl einer nicht ganz optimalen Lösung entstehen, oft mehr als wettmacht.

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