Ob materiell oder ideell, wir alle suchen. Der eine sucht sein Kleidungsstueck im Schrank, die andere ein geeignetes Fernsehprogramm. Vergessliche Menschen suchen noch ein wenig mehr. Ein Fussballspieler sucht den Weg in das Tor und viele Menschen suchen Geborgenheit und Ruhe. Forschung ist die Suche nach unbewaeltigten Problemenstellungen bzw. der Loesung selbiger, und die grosse Unrast menschlichen Seins ist die Suche nach dem Sinn des Lebens. Kurzum, dieses Grundverstaendnis des Wortes Suche laesst sich zur Begriffsbildung nutzen, denn so allgemein, wie der Begriff Suche im menschlichen Umgang erscheint, ist er auch in der Informatik: Jeder Handlungsablauf oder Algorithmus sucht nach Loesungen fuer ein gestelltes Problem. Suchprobleme sind eingebettet in einer Umgebung, in der die Suche stattfindet. Um diese Domaene fuer den Suchprozess greifbar zu gestalten, muss eine eindeutige Beschreibung aller legalen Problemzustaende erfolgen. Innerhalb dieser Menge werden ein Startzustand und mitunter mehrere Zielzustaende ausgezeichnet. Das Rendezvous Wir illustrieren die Begrifflichkeit der Zustandsraumsuche an einem Beispiel aus der Alltagswelt. Ein Mann sucht den Ausgang aus einem grossen Amtsgebaeude, sagen wir, um ein geplantes Essen mit seiner Geliebten nicht zu verpassen. Der Zustandsraum ist durch die Menge der Raeume und Flure, der Startzustand durch den gegenwaertigen Standort und der Zielzustand durch den Ausgang gegeben. Kann aus verschiedenen Ausgaengen alternativ gewaehlt werden, so gibt es gleich mehrere Zielzustaende. Ist die Position der Ausgaenge unbekannt, so liegen die Zielzustaende nicht explizit vor, sondern werden durch die Anwendung einer Regel (eines Praedikates) beschrieben. Desweiteren werden Uebergaenge spezifiziert, die es erlauben, einen Zustands bzw. Raumwechsel durchzufuehren, z.B. hoch, runter, vor, zurueck, rechts oder links. Je nach Anschauung und Umgebung wird ein Uebergang auch als Operator, als Transition oder einfach als Zug bezeichnet. Die einzelnen Zustandswechsel sind haeufig generisch, d.h. fuer mehrere Zustaende anwendbar. Mehr noch, man geht in der Zustandsraumsuche zumeist von einer endlichen Menge von Zustandsuebergaengen aus. Expansionen und Heuristiken Die Erzeugung aller Nachfolger zu einem gegebenen Zustand wird als Expansion bezeichnet. Dieses entspricht einer Neuorientierung ueber die zu Verfuegung stehenden Moeglichkeiten des ausweglosen Mannes im Beispiel. Die Menge der erreichten (generierten), aber noch nicht betretenen (expandierten) Zustaende in einem Problemloeseprozess heisst Horizont. Von dem Startzustand ausgehend wird durch wiederholte Expansion eines Zustandes am Horizont die Menge der tatsaechlich erreichbaren Zustaende beschrieben, die eine Teilmenge aller moeglichen Problemzustaende darstellt. In dem Beispiel koennten manche Tueren verschlossen sein und den Liebenden an den Rand der Verzweiflung bringen. Er mag sich wuenschen, den gesamten Horizont zu ueberblicken, ein Traum, der sich im Rechner durch die mengentheoretische Beschreibung des Horizonts tatsaechlich realisieren laesst (vergl. Kapitel~\ref{Obdds}). Der Mann hat dadurch, dass er in das Gebaeude hineingegangen ist, eine gewisse Schaetzung der Weglaenge und damit der einzukalkulierenden Zeit. Diese Einschaetzung wird als Heuristik bezeichnet. Fuer eine effiziente Problemloesung ist es guenstig, wenn die Heuristik die tatsaechliche minimale Weglaenge zum Ziel immer unterschaetzt. Demnach sprechen wir von einer unteren Schranke oder auch von einer optimistischen Heuristik. In einer graphischen Repraesentation der Suche nutzt man Knoten fuer die einzelnen Zustaende und Kanten fuer die jeweiligen Uebergaenge. Eine Knotenfolge innerhalb des sich aus diesen Elementen zusammensetzenden Problemgraphen bildet einen Pfad, waehrend die damit assoziierte Kantensequenz als Makrooperator oder kurz als Makro bezeichnet wird. Der Problemgraph entspricht in unserem Beispiel einer Uebersichtskarte des Gebaeudes. Die Uebergaenge koennen gewichtet sein, um die unterschiedlichen Schwierigkeiten verschiedener Operatoren zu betonen. So ist die Bewaeltigung einer Treppe fuer unseren Hauptdarsteller ungleich schwerer als der Gang ueber eine Tuerschwelle. Duplikate und Abkuerzungen Nun kann es sein, dass ein und derselbe Zustand ueber zwei (oder mehrere) unterschiedliche Wege erreicht werden kann. Der Mann ist in einen Zyklu} geraten. Er mag sich hilflos fragen: War ich hier schon mal oder nicht? Anders gesprochen, der Problemgraph kann so gross werden, dass sich gleiche Zustaende im Loeseprozess nicht immer aufspueren lassen. Die moeglichst speicherplatzsparende Aufdeckung dieser Duplikate ist somit zum Kernproblem der Zustandsraumsuche geworden. Die Dissertation setzt in den Kapiteln~\ref{MultiSuffixBaeume} und \ref{LernenVonAbkuerzungen} an diesem Punkt an und versucht, im Problemloeseprozess Regelmaessigkeiten innerhalb der entdeckten Zyklen aufzudecken und im weiteren Verlauf der Suche zu nutzen. Suchbaumgroesse Durch die wiederholte Expansion von Knoten wird eine Vorgaengerbeziehung der Zustaende untereinander beschrieben und ein Explorations bzw. Suchbaum aufgebaut, der die Menge aller Wege (Generierungspfade) beschreibt. Die Groesse des Suchbaumes haengt von der Suchtiefe und dem Verzweigungsgrad der einzelnen Knoten ab, wobei letzterer durch die Anzahl von Nachfolgern festgelegt ist. Die Berechnung des durchschnittlichen Verzweigungsgrads innerhalb des Suchbaumes von Problemraeumen, deren Zustaende eine unterschiedliche Anzahl von Nachfolgerpositionen (Kinder) besitzen, wird im Kapitel~\ref{BerechnungDesVerzweigungsgrads} aufgegriffen. Dabei werden wir insbesondere auf die Reduktion des Verzweigungsgrads durch die verschiedenen Abschneidestrategien eingehen. Lernverfahren Wie bei der Entdeckung von Zyklen soll unser Akteur weitere Information auffangen und zur Verbesserung seines Weges hinzuziehen. So bekommt der Suchende mehr und mehr einen Eindruck der ihn umgebenden Umwelt und entwickelt Strategien, damit er sich auf seinem Weg immer sicherer wird. Damit wird der umherirrende Mann nicht nur beim naechsten Mal den Ausgang schneller finden, sondern schon beim Erreichen der naechsten Etage die gewonnenen Erkenntnisse ueber die Gebaeudestruktur nutzen. Getragen von dieser Analogie sprechen wir in diesem Fall von einem Lernverfahren. Haeufig kann man einen Zustandsuebergang in die Gegenrichtung durchfuehren. Manche Zwischentueren schnappen jedoch nach dem Durchschreiten ins Schloss. Damit ergeben sich in gerichteten Graphen Sackgasse, also Positionen, in denen das Ziel unerreichbar geworden ist. Das Kapitel \ref{LernenVonSackgassen} widmet sich dem Aufspueren von Indikatoren fuer Sackgassen. Auch dieses Verfahren soll dem Mann wenigstens auf Dauer das Leben versuessen. Die Suchaufgabe in dem so erarbeiteten Formalismus besteht fuer den Liebenden nun darin, die kostenguenstigste "Ubergangsfolge zu finden, die den Startzustand in einen der Zielzustaende ueberf"uhrt. Gelingt dieses, so wird das Suchverfahren, nach dem der Mann handelt, zulaessig genannt. Realzeitanforderungen Eines kann der Mann jedoch nicht. Es ist ihm unmoeglich, innerhalb der Domaene in Nullzeit von einem Raum in einen anderen weit entfernten zu gelangen. Diese zusaetzliche sogenannte Realzeitanforderung im Problemloeseprozess wird in Kapitel \ref{LernenDerHeuristik} untersucht. Wir hoffen nicht, dass die sicherlich mi"smutig gelaunte Geliebte die Verabredung platzen laesst und weggeht. In diesem Fall bleibt dem Liebenden nur noch die Verfolgung eines sich somit bewegenden Zieles, ein Thema, das in Kapitel~\ref{BeweglicheZiele} behandelt wird. Wir gehen vielmehr davon aus, dass die beiden Liebenden einmuetig beieinander sitzen und sich tief in die Augen schauen. Ziehen wir uns deshalb dezent zurueck und widmen uns einer generellen Betrachtung der Suchaufgabe.