Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


31. Gewichtete Graphen



Geometrische Probleme

Gegeben seien N Punkte in der Ebene, und wir möchten die kürzeste Menge von Linien finden, die alle Punkte verbinden. Dies ist ein geometrisches Problem, welches Problem des Euklidischen minimalen Spannbaumes genannt wird. Es kann unter Benutzung des oben angegebenen Algorithmus für Graphen gelöst werden, doch es dürfte klar sein, daß die Geometrie genügend viele zusätzliche Strukturen bietet, um die Entwicklung wesentlich effizienterer Algorithmen zu ermöglichen.

Der Lösungsweg für das Euklidische Problem, bei dem der oben angegebene Algorithmus benutzt wird, besteht in der Erzeugung eines vollständigen Graphen mit N Knoten und N(N-1)/2 Kanten, wobei jedes Paar von Knoten durch eine Kante verbunden ist, mit dem Abstand zwischen den betreffenden Punkten als Gewicht. Der minimale Spannbaum kann dann mit matrixpfs für dichte Graphen in einer zu N2 proportionalen Zeit gefunden werden.

Es konnte bewiesen werden, daß es möglich ist, noch mehr zu erreichen. Die entscheidende Tatsache ist, daß die geometrische Struktur bewirkt, daß die meisten Kanten des vollständigen Graphen für das Problem irrelevant sind und wir die meisten von ihnen eliminieren können, noch bevor wir mit der Erzeugung des minimalen Spannbaumes beginnen. Tatsächlich ist bewiesen worden, daß der minimale Spannbaum eine Teilmenge des Graphen ist, den man erhält, indem man nur die Kanten aus der zum Voronoi-Diagramm dualen Struktur nimmt (siehe Kapitel 28). Wir wissen, daß die Anzahl der Kanten dieses Graphen proportional zu N ist, und sowohl der Algorithmus von Kruskal als auch die Prioritätssuche sind für solche lichte Graphen effizient. Im Prinzip könnten wir daher die zum Voronoi-Diagramm duale Struktur berechnen (wozu eine zu N log N proportionale Zeit erforderlich ist) und dann entweder den Algorithmus von Kruskal oder die Prioritätssuche anwenden, um einen Algorithmus für den Euklidischen minimalen Spannbaum zu erhalten, der in einer zu N log N proportionalen Zeit abläuft. Doch die Erstellung eines Programms zur Berechnung der zum Voronoi-Diagramm dualen Struktur ist selbst für einen erfahrenen Programmierer eine sehr schwierige Aufgabe, so daß sich diese Vorgehensweise wohl als nicht realisierbar erweisen dürfte.

Ein anderer Ansatz, der für zufällige Punktmengen verwendet werden kann, besteht darin, die Verteilung der Punkte auszunutzen, um die Anzahl der in den Graph aufgenommenen Kanten zu begrenzen, etwa wie in dem Gitterverfahren, das in Kapitel 26 für die Bereichssuche angewandt wurde. Wenn wir die Ebene so in Quadrate einteilen, daß jedes Quadrat wahrscheinlich ungefähr lg N/2 Punkte enthält, und dann für jeden Punkt nur die Kanten in den Graph aufnehmen, die ihn mit den Punkten in den benachbarten Quadraten verbinden, so ist es sehr wahrscheinlich (wenn auch nicht sicher), daß wir alle Kanten des minimalen Spannbaumes erhalten, was bedeuten würde, daß die Lösung der Aufgabe mit Hilfe des Algorithmus von Kruskal oder die Prioritätssuche effizient vollendet werden könnte.

Es ist interessant, über den Zusammenhang zwischen Algorithmen für Graphen und geometrischen Algorithmen nachzudenken, der in dem in den obigen Absätzen genannten Problem zum Ausdruck kommt. Sicher trifft es zu, daß viele Probleme entweder als geometrische Probleme oder als Probleme für Graphen formuliert werden können. Wenn die tatsächliche physikalische Anordnung von Objekten ein entscheidendes Merkmal ist, so können die geometrischen Algorithmen aus den Kapiteln 24-28 geeignet sein. Sind dagegen Verbindungen zwischen Objekten von grundlegender Bedeutung, so könnten die Algorithmen für Graphen aus dem vorliegenden Kapitel zweckmäßiger sein. Der Euklidische minimale Spannbaum scheint auf der Grenze zwischen diesen beiden Gebieten zu liegen (bei der Eingabe spielt Geometrie eine Rolle, bei der Ausgabe Verbindungen), und die Entwicklung einfacher, unmittelbar anwendbarer Verfahren für dieses und verwandte Probleme bleibt eine wichtige, jedoch schwierige Aufgabe.

Eine andere Situation, wo geometrische Algorithmen und Algorithmen für Graphen in Wechselwirkung treten, ist das Problem der Bestimmung des kürzesten Weges zwischen x und y in einem Graph, dessen Knoten Punkte in der Ebene sind und dessen Kanten Linien sind, die diese Punkte verbinden. Der von uns betrachtete Labyrinth-Graph kann als ein solcher Graph angesehen werden. Die Lösung dieses Problems ist einfach: Wir benutzen die Prioritätssuche, wobei wir die Priorität jedes vorgefundenen Randknotens gleich dem Abstand im Baum von x bis zu dem Randknoten (wie in dem angegebenen Algorithmus) plus dem Euklidischen Abstand von dem Randknoten bis y setzen. Dann brechen wir ab, wenn y zum Baum hinzugefügt wird. Mit Hilfe dieses Verfahrens wird sehr schnell der kürzeste Pfad von x nach y gefunden, indem stets in der Richtung von y vorgegangen wird, während bei dem Standardalgorithmus nach y »gesucht« werden muß. Die Bewegung von einer Ecke eines großen Labyrinth-Graphen zu einer anderen könnte die Untersuchung einer Anzahl von Knoten erfordern, die zu sqrtN proportional ist, während bei dem Standardalgorithmus praktisch alle Knoten betrachtet werden müssen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]