Robert Sedgewick: Algorithmen

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


45. NP-vollständige Probleme



Die in diesem Buch untersuchten Algorithmen werden im allgemeinen zur Lösung praktischer Probleme benutzt und erfordern daher keine übermäßig großen Ressourcen. Der praktische Nutzen der meisten Algorithmen ist offensichtlich; bei vielen Problemen haben wir sogar das Glück, unter mehreren effizienten Algorithmen auswählen zu können. Wie im vorangegangenen Kapitel dargelegt wurde, treten in der Praxis aber leider auch viele Probleme auf, die solche effizienten Lösungen nicht ermöglichen. Und was noch schlechter ist, wir können für eine große Klasse derartiger Probleme nicht einmal sagen, ob eine effiziente Lösung existieren könnte oder nicht.

Diese Situation war schon immer äußerst unbefriedigend für Programmierer und Algorithmenentwickler, die für ein breites Spektrum praktischer Probleme keinen einzigen effizienten Algorithmus finden können, sowie für Theoretiker, die keinerlei Begründung dafür finden konnten, warum diese Probleme kompliziert sein sollten. Auf diesem Gebiet sind umfangreiche Forschungsarbeiten durchgeführt worden, die zur Entwicklung von Mechanismen führten, mit deren Hilfe neue Probleme als »so schwierig wie« alte Probleme in einem speziellen technischen Sinn klassifiziert werden können. Obwohl ein großer Teil dieser Ergebnisse über den Rahmen dieses Buches hinausgeht, sind die zentralen Ideen nicht schwer zu verstehen. Wenn man mit einem neuen Problem konfrontiert wird, ist es sicher von Nutzen, eine gewisse Vorstellung von den Problemtypen zu haben, für die kein effizienter Algorithmus bekannt ist.

Manchmal ist die Grenze zwischen »leichten« und »schweren« Problemen nur durch einen feinen Unterschied gegeben. Zum Beispiel betrachteten wir in Kapitel 31 einen effizienten Algorithmus für das folgende Problem: »Finde den kürzesten Pfad vom Knoten x zum Knoten y in einem gegebenen gewichteten Graph.« Doch wenn wir nach dem längsten Pfad (ohne Zyklen) von x nach y fragen, haben wir es mit einem Problem zu tun, für das keine Lösung bekannt ist, die wesentlich besser ist als das Prüfen aller möglichen Pfade. Die feine Grenze ist sogar noch verblüffender, wenn wir ähnliche Probleme betrachten, in denen nur nach »ja-nein« Antworten gefragt wird:

Leicht: Existiert ein Pfad von x nach y mit einem Gewicht <= M?
Schwer(?):     Existiert ein Pfad von x nach y mit einem Gewicht >= M?

Breitensuche liefert für das erste Problem eine Lösung in linearer Zeit, doch alle bekannten Algorithmen für das zweite Problem könnten eine exponentielle Zeit benötigen.

Wir können eine weit genauere Aussage machen als »könnten eine exponentielle Zeit benötigen«, doch das ist für die gegenwärtigen Betrachtungen nicht erforderlich. Im allgemeinen ist es zweckmäßig, sich einen Algorithmus mit exponentieller Zeit als einen Algorithmus vorzustellen, der für bestimmte Eingabedaten vom Umfang N eine Zeit benötigt, die (wenigstens) zu 2N proportional ist. (Die Grundaussage der Ergebnisse, die wir hier betrachten wollen, ändert sich nicht, wenn 2 durch irgendeine Zahl Alpha > 1 ersetzt wird.) Das bedeutet zum Beispiel, daß für einen Algorithmus, der exponentielle Zeit benötigt, nicht garantiert werden kann, daß er für Probleme mit einem Umfang von (beispielsweise) 100 zum Ziel führt, da niemand warten kann, bis 2100 Schritte eines Algorithmus ausgeführt worden sind, unabhängig von der Geschwindigkeit des Computers. Angesichts exponentiellen Wachstums werden technologische Veränderungen unbedeutend: Ein Supercomputer mag eine Billion mal so schnell sein wie ein Rechenbrett, doch auch er ist nicht annähernd in der Lage, ein Problem zu lösen, das 2100 Schritte erfordert.


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