Robert Sedgewick: Algorithmen

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


44. Erschöpfendes Durchsuchen



Bei manchen Problemen ist es erforderlich, eine große Anzahl potentieller Lösungen zu durchsuchen, um die Antwort zu finden, und es scheint einfach nicht möglich zu sein, sie mit Hilfe effizienter Algorithmen zu lösen. Im vorliegenden Kapitel betrachten wir einige Merkmale von Problemen dieser Art sowie einige Methoden, die sich für ihre Lösung als nützlich erwiesen haben.

Zunächst müssen wir hinsichtlich der Frage, was eigentlich ein »effizienter« Algorithmus ist, etwas umdenken. Aufgrund der meisten Anwendungen, die wir untersucht haben, haben wir uns daran gewöhnt zu glauben, daß ein Algorithmus linear sein oder in einer zu N log N oder N3/2 oder ähnlichen Funktion proportionalen Zeit ablaufen muß, um als effizient angesehen zu werden. Im allgemeinen haben wir quadratische Algorithmen als schlecht und kubische Algorithmen als entsetzlich betrachtet. Doch jeder Informatiker wäre absolut begeistert, wenn er einen kubischen Algorithmus für die Probleme kennenlernen würde, die wir in diesem und im folgenden Kapitel betrachten werden. Tatsächlich wäre sogar ein zu N50 proportionaler Algorithmus (vom theoretischen Standpunkt aus) erfreulich, da von diesen Problemen angenommen wird, daß sie eine exponentielle Zeit benötigen.

Nehmen wir an, daß uns ein Algorithmus vorliegt, der eine zu 2N proportionale Zeit erfordert. Wenn wir einen Computer hätten, der 1000 mal schneller ist als der schnellste gegenwärtig zur Verfügung stehende Supercomputer, so könnten wir vielleicht ein Problem für N = 50 im Verlaufe einer Stunde lösen (unter den günstigsten Voraussetzungen hinsichtlich der Einfachheit des Algorithmus). Doch in zwei Stunden könnten wir es nur für N = 51 lösen, und selbst in einem Jahr würden wir nur bis N = 59 gelangen. Und selbst dann, wenn ein neuer Computer entwickelt würde, der eine Million mal schneller wäre, und wenn uns eine Million solcher Computer zur Verfügung stünden, könnten wir in einem Jahr nicht N = 100 erreichen. Realistisch ist, N in der Größenordnung von 25 oder 30 anzusetzen. In dieser Situation kann ein »effizienterer« Algorithmus ein Algorithmus sein, der ein Problem für N = 100 mit einem realistischen Aufwand an Zeit und Geld lösen könnte.

Das berühmteste Problem dieser Art ist das Problem des Handelsreisenden (traveling salesman problem): Zu einer gegebenen Menge von N Städten ist die kürzeste Route zu finden, die sie alle verbindet, ohne daß eine Stadt zweimal besucht wird. Dieses Problem entsteht bei einer Reihe wichtiger Anwendungen auf natürliche Weise und ist daher sehr gründlich untersucht worden. In diesem Kapitel verwenden wir es als Beispiel, um einige grundlegende Methoden zu untersuchen. Für dieses Problem wurden viele fortgeschrittene Verfahren ausgearbeitet, doch noch immer ist es undenkbar, eine beliebige Instanz dieses Problems für N = 1000 zu lösen.

Das Problem des Handelsreisenden ist deshalb schwierig, weil es scheinbar nicht zu vermeiden ist, daß die Länge einer sehr großen Anzahl möglicher Touren geprüft werden muß. Das Prüfen aller Touren ist erschöpfendes Durchsuchen; wir betrachten zunächst, wie dies erfolgt. Danach untersuchen wir, wie diese Prozedur modifiziert werden kann, um die Anzahl der zu prüfenden Möglichkeiten beträchtlich zu verringern, indem versucht wird, während der Entscheidungsfindung falsche Entscheidungen so früh wie möglich zu entdecken.

Wie oben erwähnt wurde, ist das Lösen eines umfangreichen Problems dieser Art selbst mit den besten bekannten Verfahren praktisch unmöglich. Wie wir im folgenden Kapitel sehen werden, gilt das gleiche für viele andere wichtige praktische Probleme. Doch was ist zu tun, wenn solche Probleme in der Praxis auftreten? Irgendeine Antwort muß gefunden werden (der Handelsreisende muß etwas tun); wir können die Existenz des Problems nicht einfach ignorieren oder nur feststellen, daß es zu schwer ist. Am Ende dieses Kapitels geben wir einige Methoden an, die <%-3>entwickelt wurden, um praktische Probleme zu bewältigen, die erschöpfendes Durchsuchen zu erfordern scheinen. Im folgenden Kapitel gehen wir ausführlicher auf die Gründe ein, weshalb für viele derartige Probleme sicherlich kein effizienter Algorithmus gefunden wird.


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