Robert Sedgewick: Algorithmen

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


44. Erschöpfendes Durchsuchen



Approximationsalgorithmen

Da die Ermittlung der kürzesten Tour eine so umfangreiche Berechnung zu erfordern scheint, ist es sinnvoll zu überlegen, ob es einfacher sein könnte, eine Tour zu finden, die beinahe die kürzeste ist. Wenn wir bereit sind, die Forderung abzuschwächen, daß wir unbedingt den kürzesten möglichen Pfad erhalten müssen, erweist es sich, daß wir weit umfangreichere Probleme bewältigen können, als es mit den obigen Verfahren möglich ist.

Beispielsweise ist es relativ leicht, eine Tour zu finden, die höchstens um den Faktor zwei länger ist als die optimale Tour. Die Methode beruht darauf, daß einfach der minimale Spannbaum ermittelt wird. Dies liefert nicht nur eine untere Schranke für die Länge der Tour, wie bereits erwähnt, sondern es zeigt sich, daß man auch eine obere Schranke für die Länge der Tour enthält: Zu einem gegebenen minimalen Spannbaum erzeuge man eine Tour, indem man die Knoten des minimalen Spannbaums unter Benutzung der folgenden Prozedur besucht: Um den Knoten x zu verarbeiten, besuche man x, besuche dann jeden Nachfolger von x, wobei man diese Prozedur des Besuchens rekursiv anwendet und nach dem Besuchen jedes Nachfolgers zum Knoten x zurückkehrt, und beende die Prozedur im Knoten x. Bei dieser Tour wird jede Kante im Spannbaum zweimal durchlaufen, so daß ihre Kosten doppelt so groß sind wie die Kosten des Baumes. Es ist keine einfache Tour, da ein Knoten viele Male besucht werden kann, doch sie kann in eine einfache Tour umgewandelt werden, indem einfach jeder Knoten immer dann, wenn er nicht zum erstenmal erscheint, gelöscht wird. Das Löschen des Auftretens eines Knotens entspricht der Benutzung einer Abkürzung, die an diesem Knoten vorbeiführt; natürlich können sich die Kosten der Tour dadurch nicht erhöhen. Folglich liegt eine einfache Tour vor, deren Kosten weniger als doppelt so groß sind wie die des minimalen Spannbaumes.

Die Skizze im linken Teil von Abbildung 44.5 zeigt einen minimalen Spannbaum für unsere Punktmenge (deren Berechnung gemäß der Beschreibung in Kapitel 31 erfolgte), zusammen mit einer entsprechenden einfachen Tour. Diese Tour ist offensichtlich nicht optimal, da sie sich selbst kreuzt. Für eine große zufällige Punktmenge hat es den Anschein, daß die auf diese Weise erzeugte Tour der optimalen Tour nahekommt, obwohl diese Annahme noch durch keine Analyse unterstützt werden konnte.

Abbildung 44.5
Abbildung 44.5 Einfache Tour beim Euklidischen Problem des Handlungsreisenden.

Ein anderer ausprobierter Ansatz ist die Entwicklung von Methoden zur Verbesserung einer vorhandenen Tour in der Hoffnung, daß eine kurze Tour gefunden werden kann, wenn solche Verbesserungen wiederholt vorgenommen werden. Zum Beispiel kann beim Euklidischen Problem des Handlungsreisenden, wo Abstände im Graph Abständen zwischen Punkten in der Ebene entsprechen, eine sich selbst überschneidende Tour verbessert werden, indem jeder Schnitt wie folgt beseitigt wird: Falls die Strecke AB die Strecke CD schneidet, ergibt sich eine kürzere Tour, wenn man AB und CD löscht und AD und CB hinzufügt. Die sukzessive Anwendung dieses Verfahrens führt für eine beliebige gegebene Tour zur Erzeugung einer Tour, die nicht länger ist und sich nicht selbst überschneidet. Zum Beispiel erhält man durch Anwendung dieser Prozedur auf die aus dem minimalen Spannbaum erzeugte Tour (im linken Teil von Abbildung 44.5) die im rechten Teil von Abbildung 44.5 dargestellte kürzere Tour.

Tatsächlich besteht eines der effizientesten Verfahren zur Gewinnung von Näherungslösungen für das Euklidische Rundreiseproblem, das von S. Lin entwickelt wurde, in der Verallgemeinerung des obigen Verfahrens der Verbesserung von Touren durch Umlegen von drei oder mehr Kanten in einer gegebenen Tour. Sehr gute Ergebnisse wurden durch so lange sukzessive Anwendung einer solchen Methode auf eine ursprünglich zufällige Tour, bis sie zu keiner Verbesserung mehr führt, erzielt. Man könnte vermuten, daß es besser ist, mit einer Tour zu beginnen, die der optimalen bereits nahekommt, doch die Untersuchungen von Lin zeigen, daß das nicht der Fall sein muß.

Die oben beschriebenen verschiedenen Ansätze für die Gewinnung von Näherungslösungen für das Problem des Handlungsreisenden sollen nur einen Eindruck der Verfahrenstypen vermitteln, die angewandt werden können, um erschöpfendes Durchsuchen zu vermeiden. Die oben gegebenen kurzen Beschreibungen werden den vielen brillianten Ideen, die entwickelt worden sind, nicht gerecht; die Formulierung und Analyse von Algorithmen dieses Typs ist ein Forschungsgebiet der Informatik, auf dem noch aktiv gearbeitet wird.

Man könnte mit Recht fragen, warum das Problem des Handlungsreisenden und die anderen Probleme, die wir angedeutet haben, erschöpfendes Durchsuchen erfordern. Könnte es nicht möglich sein, daß ein eleganter Algorithmus die minimale Tour ebenso leicht und schnell findet, wie wir den minimalen Spannbaum finden können? Im folgenden Kapitel werden wir sehen, warum die meisten Informatiker der Ansicht sind, daß ein solcher Algorithmus nicht existiert, und warum stattdessen Approximationsalgorithmen von der in diesem Abschnitt betrachteten Art untersucht werden müssen.


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