Intelligente Suchverfahren

Viele Suchprobleme sind "alte Bekannte" der Informatik. Dennoch gibt es eine Fülle hoch aktueller Probleme, zu denen es keine direkten Lösungsverfahren gibt. Gerade die interessanteren Probleme verdeutlichen in besonderem Maße die Grenzen des Einsatzes von Informatiksystemen, aber auch die Möglichkeiten, wie man mit ihnen dennoch zu akzeptablen Lösungen kommen kann.

Die Schülerinnen und Schüler müssen am Ende des Kurses nicht nur verstanden haben, sondern auch ein Gefühl dafür bekommen haben, welche Auswirkung das exponentielle Ansteigen der Größe eines Suchraumes für die Frage der Lösbarkeit hat.

Kontext

Es gilt also für den Kurs einen Kontext zu wählen, der eines der besonders schweren (np-vollständig) Probleme beinhaltet. In Hamburg ist dafür das Thema Logistik geeignet, da es mehrere wichtige Suchprobleme beinhaltet.

  • Das sind einmal Wegeprobleme, z.B. das Problem des kürzesten Weges, das mit seiner Anwendung bei Navigationssystemen sehr aktuell ist. Als Erweiterung, bei den man eines der ganz schwierigen Probleme untersuchen kann, gibt es hier das Problem des travelling salesmen. Allgemein geht es (auch anschaulich) um die Suche in Graphen.
  • Sehr passend sind auch Packprobleme. Das verallgemeinderte Container-Lade-Problem stellt auch eines der sehr schwierigen Probleme dar.

Wahl der Programmiersprache

Für dieses Thema ist wie bei der Sprachverarbeitung eine Funktionale Sprache angemessen. Da oft sehr leicht eine rekursive Beschreibung des Lösungsverfahrens möglich ist, ist Scheme eine gute Wahl. Alle Beispiellösungen lassen sich interaktiv bearbeiten. Zwei ganz einfache Beispielprogramme mit Benutzeroberfläche einfache-Programme-mit-gui.zip zeigen, dass man natürlich auch mit Scheme eine solche erstellen kann.

Kursmaterial

Die Dateien zu diesem Abschnitt sind so geordnet und durchnummeriert, dass ein möglicher Unterrichtsgang deutlich wird. Die Materialien basieren z.T. auf einem älteren html-Skrip von mir, das hier zunächst abgelegt ist.

Allgemeines zu Scheme

Einige meiner Programme verwenden eine unit mit dem Namen breakpoint.ss (oder breakpoint.rkt), die einmal eine etwas komfortablere Ausgabe mit (writeln <0..beliebigeAnzahlParameter>) ermöglicht und außerdem verschiedene Funktionen zum Debugging bereitstellt (bkpt <0..beliebigeAnzahlParameter>) . Sie kann auch im selben Ordner wie die verwendeten Programmdateien liegen und mit (load breakpoint.scm) geladen werden. Verwenden Sie eines der Programme:

Die ersten hier abgelegten Materialien dienen zur Ergänzung.

Wegen der häufig - nicht nur bei Schülerinnen und Schülern - auftretenden Probleme beim Verständnis der rekursiven Lösung von Problemen, habe ich ein Konzept entwickelt, das ausgehend vom Konzept des test-driven-development eine schrittweise Entwicklung der Funktion ermöglicht.

Abgrenzung der Suchverfahren zu direkten Verfahren

Es kann sinnvoll sein, zur Einführung in Scheme und der Abgrenzung zwischen Suchproblemen und Problemen, die sich durch direkte Verfahren lösen lassen, ein Sortierverfahren anzusehen.

Einstieg über das Füllen eines Containers

Macht man das Problem nicht zu groß (ein Container, nur eine zu optimierende Größe, wenige Alternativen), dann ist der Mensch sehr schnell in der Lage, geschickt eine Lösung zu finden. Dabei verwendet er in der Regel ein greedy Verfahren (gierige Strategie). Wählt man die Daten zunächst so, dass diese Strategie erfolgreich ist, kann man mit den Schülerinnen und Schülern sehr schnell eine bei diesen Daten funktionierende Programmlösung entwickeln.

Sollten die Schülerinnen und Schüler nicht schon vorher bemerkt haben, dass man mit dieser Methode nicht immer eine Lösung finden kann, obwohl eine existiert, gibt man Daten vor, an denen klar wird, dass man eine Möglichkeit finden muss, Entscheidungen rückgängig zu machen. Dies führt mit geringfügigen Änderungen auf ein vollständiges Suchverfahren, die Tiefensuche.

Die folgenden Beispiele behandeln die Tiefensuche im Gaphen. Damit sollte man sich beschäftigen, wenn man vorrangig Wegeprobleme betrachten will.

Braucht man die Breitensuche? Interessant ist die Breitensuche vor allem dann, wenn man sich mit den Datenstrukturen beschäftigt, die bei den verschiedenen Suchverfahren zur Speicherung der Alternativen verwendet werden. Es treten stack (Stapel; bei der Tiefensuche), queue (Warteschlange; bei der Breitensuche) und priority queue (Prioritätswarteschlange; z.B. bei A*) auf. Der folgende Text behandelt beide blinden und vollständigen (damit brute force) Suchverfahren.

Vollständige Suchverfahren stoßen bei zu großen Suchräumen an die Grenzen der Berechenbarkeit. Dies kann man gut mit dem (verallgemeinerten) Problem der Acht Damen erfahrbar machen.

Das Problem des minimalen Versorgungsnetzes (minimal spanning tree) lässt sich mit greedy Algorithmen ("führe jeweils den Schritt mit dem größten Zuwachs, Gewinn o.ä. aus") lösen und man kann auf einfache Art nachweisen, dass die Lösung wirklich minimal ist. Bei diesen Verfahren erfolgt die Auswahl der Nachfolger eines Zustandes nicht mehr blind, sondern auf Grund von Informationen.

Die Schülerinnen und Schüler müssen für ein gegebenes Problem beurteilen können, ob es mit einem der einfachen Verfahren gelöst werden kann, sollten größere Probleme erkennen können und eines der dafür anwendbaren Verfahren kennen gelernt haben. A-Stern bezeichnet eines der intelligenten Verfahren, mit dem auch sehr große Probleme dadurch gelöst werden können, dass man bei der Auswahl der Nachfolger eines Zustandes gezielt günstige wählt. Es unterscheidet sich von den vorher betrachteten dadurch, dass es dabei nicht nur lokale Informationen über den Suchraum, sondern auch globale verwendet.

Bei den Programmen ist auch ein Programm zur Behandlung eines Packproblems, das schon im zweidimensionalen Fall, noch mehr im dreidimesionalen Fall schnell sehr aufwändig wird und in dieser Form mit zu den np-vollständigen Problemen gehört. Es ist gut für eine Projektarbeit der Schülerinnen und Schülern geeignet.

Eines der weiteren wichtigen großen Probleme ist das travelling-salesmen-problem. Es tritt nicht nur in dieser sehr speziellen Form der Rundreise einer Person auf, sondern auch z.B. bei den Arbeitsschritten eines Lötkopfes beim Verlöten einer Platine. Die Größe des Suchraums steigt exponentiell mit der der Zahl der anzusteuernden Orte an und wie für alle np-vollständigen Probleme gibt es (bisher??) kein Verfahren, das bei einer großen Zahl von Orten eine Lösung erzeugen kann. Allerdings gibt es Verfahren, die gute Lösungen generieren, wenn auch nicht die beste.

Eines dieser Verfahren sind die Genetischen Algorithmen, zu denen hier Lösungen mehrerer Probleme abgelegt sind.

Das Bemerkenswerte an den GA ist, dass sie die Möglichkeit nutzen, mit dem Computer zufällige Prozesse zu simulieren und daher eben nicht durch systematisches Suchen, sondern durch Optimierung eines Pools von unterschiedlich guten Zwischenschritten zu einer in der Regel suboptimalen Lösung kommen.

Alternativer Einstieg

Gallenbacher hat sich in seinem Buch Abenteuer Informatik mit dem Problem des kürzesten Weges beschäftigt, das er mit dem Algorithmus von Dijkstraa löst. Sein Vorschlag bietet die Möglichkeit eines alternativen Einstiegs, der auch ganz ohne Programmierung arbeiten könnte. Dazu finden Sie hier einen Kurztext für den Unterrichtsgang und Programme.

Literatur

Die Literatur zu diesem Themenbereich ist sehr umfangreich, da viele der Algorithmen in Büchern über Algorithmen auftauchen. Speziell möchte ich auf folgende Bücher hinweisen [ISBN usw. lasse ich weg, da man die Bücher in der Regel -so es sie noch gibt- über Suchmaschinen findet.]

  • Volker Turau: Algorithmische Graphentheorie
  • Gritzmann/Brandenburg: Das Geheimnis des kürzesten Weges
  • Andreas Bortfeldt: Informierte Graphensuchverfahren und Genetische Algorithmen (lässt sich zwar nicht mehr kaufen, von Bortfeldt gibt es aber Skripte zum download)
  • Jens Gallenbacher: Abenteuer Informatik
  • Jochen Ziegenbalk: Algorithmen

Sekundarstufe I

Sekundarstufe II

CommSy-Räume