Hallo

In Kapitel 5 Folie 36 steht, dass der Lee Algorithmus garantiert die kürzeste Verdrahtung findet.
Auf Übungsblatt 4 Aufgabe 4b) soll man ein Netz erstellen in dem das nicht der Fall ist.

Bezieht sich Folie 36 nur auf ein Netz mit zwei Punkten? weil an sich widerlegen wir ja in der Übung den Satz auf der Folie.
oder erkenne ich was falsch?


mfG

W

Hallo,

der Lee-Algorithmus findet unter gegebener Situation die kürzeste Verbindung zwischen zwei Punkten. Was der Algorithmus aber nicht kann, ist das globale Minimum bei der Verdrahtung mehrerer Netze zu finden (siehe Übung). Die Aussage der Optimalität bezieht sich also nur auf die Situation der Verdrahtung zweier Punkte.

Oder anders: Eine Chipfläche, mehrere Netze. wird das erste Netz berechnet, findet Lee die optimale (kostengünstigste) Verbindung. Für das nächste Netz wird nun die erste Verdrahtung als Hindernis angesehen. Mit dieser zusätzlichen Bedingung findet Lee auch für das zweite Netz wieder die kürzeste Verbindung, usw. usf. Dass heißt aber nicht, dass die zweite (dritte, vierte) Verbindung auch dann die kürzeste gewesen wäre, wenn dieses zweite (dritte, vierte) Netz als erstes geroutet worden wäre.

Alles klar?

Grüße,
Martin

Jap, danke!