vorige nächste

Suchverfahren geraten in eine Sackgasse


Die Versuche, das Problem des tsp mit vollständigen oder greedy Algorithmen zu lösen, führen in eine Sackgasse. Das Hauptproblem dabei ist, dass dieses Problem -genauso wie einige andere, die diesem im Aufwand vergleichbar sind- einen exponentiellen Anstieg der Komplexität aufweisen. Wie groß das Problem ist, so groß, dass man es sogar wiederum bei der Kryptologie als Sicherheitsfaktor nutzen kann, zeigt der Artikel von Rüdeger Baumann in LogIn 20 (2000) Heft 2. Rüdeger Baumann schreibt in der Einleitung:

Das Rucksackproblem

Informatische und kryptologische Aspekte

Das Rucksackproblem ist eines der Standardbeispiele zur Bewusstmachung der "Grenzen des Computers" im Sinne des praktisch Unmöglichen (gegenüber dem prinzipiell Unmöglichen). Das heißt: Es gibt Probleme, die zwar algorithmisch lösbar sind, bei denen der Aufwand an Zeit oder Speicherplatz mit dem Problemumfang aber so stark ansteigt, dass er jedes vernünftige Maß übersteigt. Was das Rucksackproblem gegenüber anderen praktisch unlösbaren Problemen - für den Informatikunterricht aber besonders reizvoll macht, ist seine Anwendung in der Kryptologie: Auf ihm beruht das historisch erste Beispiel eines asymmetrischen Chiffrierverfahrens. Da das zugehörige Rucksack-Chiffrierverfahren - wegen geringer mathematischer Voraussetzungen - leicht zu verstehen ist, empfiehlt es sich zur Einführung in das Thema "Chiffriersysteme mit öffentlichem Schlüssel" - auch wenn es, drastisch formuliert, inzwischen "auf dem Müllhaufen der Kryptographie gelandet ist" (Schneier, 1997, S. 530). Das bekanntere (und in der Praxis überwiegend eingesetzte RSA-Verfahren) dagegen benötigt wesentlich mehr zahlentheoretische Kenntnisse (vgl. Sommer, 1998). Im Folgenden wird eine Unterrichtseinheit geschildert, die sich dem Problem von der Kryptologie her nähert, und sodann auf Fragen der Aufwandsanalyse von Algorithmen eingeht.

Schon einfache Abschätzungen über die Größe des Lösungsraumes bei beiden und anderen vergleichbaren Problemen zeigen, dass eine vollständige Suche am Laufzeitproblem scheitern muss: Seine Ordnung hängt von der Größenordnung VerbindungenOrte ab und damit exponentiell von der Zahl der Orte! Es gibt keinen Algorithmus, der diese exponentielle Abhängigkeit von der Zahl der Orte beim tsp und seinen Verwandten, den np-vollständigen Problemen, auf eine polynomiale Abhängigkeit drücken könnte!

Die Anwendung von greedy - Algorithmen (s.o.) führt zwar ganz schnell zu einem Endzustand, der sich aber beim genaueren Hinsehen im Gegensatz zur Situation beim minimal spanning tree nicht als die gesuchte Lösung der minimalen Gesamtlänge zeigt. Der wesentliche Unterschied zwischen dem Problem des minimal spanning tree und dem tsp ist eben, dass man für den Algorithmus von Prim (beispielsweise) zeigen kann, dass er wirklich zur optimalen Lösung führt, während schon einfache Beispiele zeigen, dass beim tsp in der Regel keine optimale Lösung erreicht wird.