Breitensuche (2)


Bei der Planung der Leitungsführung auf einer Leiterplatte (Entflechtung) läßt sich das Verfahren der Breitensuche gut verwenden; wir betrachten ein etwas idealisiertes Modell:

Gegeben ist eine rechteckige Platine, die in ein festes Punktraster eingeteilt ist. Auf manchen Rasterpunkten liegen Anschlüsse für Bauteile; einige davon sollen paarweise verbunden werden. Manche Bereiche der Platte sind blockiert, einige Verbindungen bestehen bereits und müssen umgangen werden. Die Verbindungen dürfen nur parallel zu den Platinenseiten auf Rasterlinien geführt werden (evtl. mit Ecken), sollen aber möglichst kurz sein.

Wir fassen den freien Bereich der Platine als Graphen auf: Knoten sind alle freien Rasterpunkte, Kanten jeweils die Verbindungen zu den Nachbarn. Wir zeichnen einen Startpunkt und einen Zielpunkt aus und suchen dazwischen eine möglichst kurze Kantenfolge. Dazu starten wir eine Breitensuche vom Startpunkt aus und markieren jeden dabei gefundenen Knoten mit dem Abstand zum Startpunkt (die Markierung kann man als Höhe auffassen). Ist der Zielpunkt erreicht, so folgen wir einer möglichst steil nach unten folgenden Kantenfolge; sie ist eine  kürzeste Verbindung zum Startpunkt (es kann davon mehrere geben).

Lee
Im Beispiel haben wir in der Mitte eine bestehende vertikale Verbindung vorgegeben, die zu umgehen ist; der Startpunkt liegt links (das Raster selbst haben wir hier nicht dargestellt). Man sieht an den diagonal liegenden Höhenlinien, wie sich schichtenweise ein Gebirge aufbaut, bis es den rechts liegenden Zielpunkt erreicht, von dem aus man dann wieder absteigt.

Gibt es mehrere Verbindungen durchzuschalten, so kommt es auf eine geschickte Reihenfolge an: man kann sich leicht den weiteren Weg versperren! Unter Umständen muß man also zurücksetzen und eine andere Reihenfolge versuchen. Dennoch ist das Verfahren (das von Lee angegeben wurde) praktisch brauchbar auch bei Verwendung durch Laien, und führt manchmal zu überraschenden Lösungen.

Interessant ist, daß es bei der hier verwendeten Definition der Länge eines Kantenzugs, der Manhattan-Metrik, zu zwei Punkten mehrere  kürzeste Verbindungen geben kann, wie auch in einer Großstadt mit rechtwinkligem Straßennetz!

Manhattan

zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36