Global Wiring
Im Applet ist ein Verdrahtungsproblem zu sehen: Die angezeigten Knoten
gehören paarweise zusammen - was an der Farbe zu
erkennen ist - und zwei Knoten gleicher Farbe sollen durch
einen Draht verbunden werden. Der Draht soll nur horizontal und
vertikal verlaufen und maximal einen 90-Grad Knick habe - es gibt also
nur zwei Möglichkeiten: man kann sich mit der Taste
"zufällige Lösung berechnen" zufällig per
Münzwurf erzeugte Verdrahtungen anzeigen lassen.
Wenn eine Drahtverbindung
gezogen wird, läuft sie über die 6 vertikalen und 6
horizontalen dünnen schwarzen Kanten, die es zwischen den 9
Feldern gibt. Eine dieser
Kanten wird also von mehreren Drahtverbindungen
überkreuzt. Diese Überkreuzungs-Anzahl ist in technischen
Anwendungen (VLSI Design) ein Wert, den es klein zu halten
gilt. Das Ziel ist es also, alle Knotenpaare zu verbinden und dabei die
größte Überkreuzungs-Anzahl (von allen Kanten)
möglichst klein zu halten. Dieses MinMax Optimierungproblem ist
rechts
als Lineares Gleichungssystem
angegeben (die Ungleichungen sind in der Reihenfolge der schwarzen
Kanten in der Skizze geordnet, und zwar primär von oben nach unten
und sekundär von links nach rechts). Mit der Taste "relaxierte
Lösung berechnen" wird mit
Hilfe des Simplex Algorithmus eine optimale relaxierte Lösung
berechnet,
d.h. eine, die sich nicht notwendigerweise entscheidet, ob ein Draht
entweder über die eine oder die andere mögliche Stecke
verlegt wird,
sondern z.B. auch sagt: 40% der Verbindung geht über die eine
Strecke und 60% über die andere. In der Skizze ist diese
vorläufige Lösung durch die Dicke des
Verbindungsdrahts dargestellt. Für das vorgegebene
Verdrahtungsproblem
ist eine relaxierte Lösung natürlich nicht brauchbar. Deshalb
wird aus der relaxierten Lösung mit der Taste "randomisierte
Lösung berechnen" die folgende 0/1-Lösung gemacht: ein
relaxierter Wert x des Lösungsvektors, dessen Werte ja zwischen
jeweils
einschließlich 0
und 1 liegen, wird mit Wahrscheinlichkeit x zu 1 und mit
Wahrscheinlichkeit 1-x zu 0.
Dieser randomisierte Algorithmus und insbesondere das randomisierte
Runden wurde
1987 von P. Raghavan und C. D. Thompson vorgestellt.
Das Applet wurde von Jonas Behr geschrieben.
Datum: 6.2.2006.
Der Java-Quellcode
für das Applet.
Letzte Änderung: 6. Feb. ‘06 | Bei Fragen und Anregungen E-Mail an:
Bernd Borchert
