Routing : Lee - optimal?

Auf den Vorlesungsfolien steht ( Kap5, Folie 36 ) :

"- garantier kürzeste Verdrahtungslänge."

Somit wäre Routing nach Lee optimal.

In den Übungsaufgaben hatten wir jedoch beweisen müssen ( ÜB4, Aufgabe 4), dass es Fälle gibt, bei denen das Verfahren nicht optimal arbeitet.

Was ist nun richtig?

Danke

Lee garantiert fuer ein Netz die kuerzeste Verdrahtungslaenge, aber nicht fuer die Menge alle Netze.
Man stelle sich eine gewisse Menge von Netzen vor. Wenn Lee das erste Netz verbinden soll, so ist diese Verbindung garantiert die kuerzeste. Verbindet Lee dann das zweite Netz, so ist diese Verbindung unter der Einschraenkung, dass das die Draehte vom ersten Netz nun Hindernisse sind, wieder optimal fuer das zweite Netz. Usw. Usf.
D.h. fuer jedes Netz garantiert Lee die kuerzeste Verbindung. Fuer die Menge aller Netze gilt dies dann nicht mehr, da bereits verdrahtete Netze nun Hindernisse darstellen. Da es haeufig mehrere kuerzeste Verbindungen gibt, fueren unterschiedliche Lee-Loesungen zu unterschiedlichen Kosten fuer die Verdrahtung aller Netze.
Ebenso ist es abhaengig von der Reihenfolge, wie die Netze verdrahtet werden.

Hoffe, dass das helfen konnte.
Gruesse,
Sven