Viele der grundlegenden Suchverfahren sind schon im 19. Jahrhundert untersucht worden, speziell bei der Analyse von Labyrinthen. Sie gehören inzwischen zu den Standardalgorithmen, insbesondere die Tiefensuche mit backtracking ist in der Informatik häufig untersucht worden. Dafür gibt es gute Gründe, was allerdings nicht den Neuigkeitswert dieser Verfahren steigert. Über diese altbekannten elementaren Verfahren der uninformierten Suche -wenn sie denn anwendbar sein sollten- ist genug bekannt und sie sind standardisierbar genug, um sie an neue Probleme anzupassen. Wenn sie denn anwendbar sind!
Suchprobleme werden dennoch auch heute noch intensiv untersucht, ständig neue Probleme werden mit neuen oder veränderten Suchverfahren bearbeitet. Die Zahl der Probleme, die nicht mit einem direkten Lösungsverfahren gelöst werden können, sondern Suchprobleme darstellen, nimmt eigentlich ständig zu.
Hierin liegt ein besonderer Reiz des Themas für den Unterricht: Man findet überall in der Literatur Hinweise zu Problemen, an denen zur Zeit gearbeitet wird.
Ich fand die folgende Notiz zu Genetischen Algorithmen :
Das Erstaunliche an den Suchproblemen ist aber, dass es sogar ganz altbekannte Probleme gibt, die mit den o.a. einfachen Lösungsverfahren nicht lösbar sind. Es ist die Klasse der np-vollständigen Probleme, zu denen es keine allgemeinen Lösungsverfahren gibt, bei denen man zur Zeit davon ausgeht, dass sie auch weiterhin nicht allgemein lösbar sind. Das Hauptproblem ist, dass sie einen exponentiellen Anstieg der Komplexität aufweisen.
Ich will das an einem sehr häufig betrachteten Beispiel deutlich machen, dem travelling salesperson problem (tsp). Untersucht man das Problem einer optimalen Rundreise (Was das Optimierungskriterium dabei ist, ist belanglos. Es kann einfach die Länge sein.) eines Vertreters durch beispielsweise 6 Orte, dann kann man einen optimalen Weg in der Regel problemlos per Hand bestimmen. Das Problem verschärft sich natürlich bei 20 Orten, insbesondere dann, wenn von einer hohen Zahl möglicher Verbindungswege ausgegangen werden muss. Es zeigt sich, dass die Ordnung des Verfahrens von der Größenordnung Verbindungen Orte abhängt und damit exponentiell von der Zahl der Orte!
Wendet man auf das tsp eines der einfachen Suchverfahren an, dann kann man sehr einfach nicht nur nachrechnen, sondern auch am Programmablauf zeigen, dass ein solches exponentielles Anwachsen sehr bald zu völlig unrealistischen Laufzeiten führen kann. Das können bei durchaus realistischen Problemen Zeiten werden, die deutlich über die Lebensdauer des Weltalls hinaus gehen.
Es empfiehlt sich tatsächlich, sich die Mühe mit dieser "sinnlosen" Lösung zu machen. Nicht nur die Schülerinnen und Schüler, sondern auch wir selbst haben es sicher zwar "verstanden" aber oft durchaus Mühe zu "begreifen", was exponentieller Anstieg bedeutet. Es wird eben nicht einfach immer nur mehr!
Es gibt also (bisher?) 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 und das können und wollen auch wir mit den Genetischen Algorithmen nicht. Sie liefern uns in der Regel nicht "die" optimale Lösung, sondern nur eine suboptimale. Das ist aber auch schon viel, wenn man denn keine andere Methode hat, deren Lösungen die Qualität der so erreichten haben. Beachten Sie, dass die wirklich optimale Lösung zu finden, in vielen Anwendungen eine im strengen Sinne "akademische" Frage ist, die den Anwender herzlich wenig interessiert. Der will nur möglichst wenig Kosten haben, das soll aber jetzt erreicht werden und nicht in ferner Zukunft!
Ob für die Behandlung des tsp in realen Anwendungen die Genetischen Algorithmen der "richtige" Weg sind, mag durchaus zu hinterfragen sein. Sie haben aber den wesentlichen Vorteil, dass man auf dem Bildschirm sehen kann, was passiert. Zu anderen Problemen, z.B. dem Containerladeproblem, sei auf die Literatur verwiesen.
Vergessen Sie nicht bei der Behandlung des Themas, dass es nicht den "richtigen" Algorithmus gibt, sondern dass jedes neue Problem auch Anreiz bietet, neue Wege zu finden. Ich verweise dazu nur auf die Ideen zu Softwarebomben und Softwareameisen, die neueren Heften von Spektrum der Wissenschaft entstammen. Lassen Sie sich und ihre Schülerinnen und Schüler inspirieren und animieren Sie zum experimentieren. Es ist sehr sinnvoll, ihnen nur den Gedanken der Genetischen Algorithmen zu beschreiben. Die Schülerinnen und Schüler kennen genetische Prozesse aus dem Biologieunterricht und sie sollten diese Kenntnisse nutzen, um selbst die Teilprozesse in funktionierende Algorithmen umzuwandeln. Sie sollten im besten Sinne experimentieren, denn eigentlich geht es gerade darum!