Wikipedia · einfach zusammengefasst · Stand
Suchverfahren
Dieser Artikel beschreibt die Suche nach Daten im Kontext der Informatik. Für die Suche nach vermissten Personen und Schiffen siehe Suchmuster. Dieser …
Inhalt5 Abschnitte
Grundidee und Einteilung
Suchverfahren oder Suchalgorithmen sind Algorithmen, die in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften suchen. Ein algorithmisches Problem lässt sich allgemein als Suche nach einer Lösung in einer Menge möglicher Lösungen, dem Lösungsraum, verstehen. Als Lösung kann der Zielzustand selbst gelten, aber auch der Weg zum Ziel oder die Reihenfolge bestimmter Aktionen.
Man unterscheidet einfache beziehungsweise uninformierte Suchalgorithmen und heuristische beziehungsweise informierte Suchalgorithmen. Einfache Verfahren verwenden allgemeine, intuitive Methoden und berücksichtigen die besondere Struktur des Problems nicht. Dadurch sind sie vielseitig einsetzbar, verursachen aber bei großen Suchräumen oft hohe Suchkosten. Heuristische Verfahren nutzen zusätzlich Wissen über den Suchraum, zum Beispiel über die Datenverteilung, um die benötigte Suchzeit zu verringern.
Ist der Suchraum endlich, kann eine geeignete Suchstrategie immer zu einem Ergebnis führen. Bei unendlichen Lösungsräumen muss die Suche nach bestimmten Kriterien abgebrochen werden, beispielsweise nach einer festgelegten Zeit. Bei wiederholten Suchen in einer endlichen Datenmenge kann eine Indexstruktur, etwa ein nach einem Kriterium sortierter Suchbaum, die Suche beschleunigen. Dann müssen nicht mehr alle Einträge geprüft werden; in einem Telefonbuch beginnt man beispielsweise beim Buchstaben, mit dem der gesuchte Name anfängt.
Einfache Suche in Listen, Bäumen und Graphen
Bei der Suche in Listen soll ein Element gefunden werden, dessen Suchschlüssel bekannt ist. Die lineare Suche prüft die Elemente nacheinander, bis ein Element mit dem gesuchten Schlüssel gefunden wird. Ihre Laufzeit beträgt O(n), wobei n die Anzahl der Listenelemente ist. Sie funktioniert mit sortierten und unsortierten Listen.
Die binäre Suche hat eine Laufzeit von O(log n) und ist bei großen Listen deutlich effizienter als die lineare Suche. Sie setzt jedoch voraus, dass die Liste vorher sortiert wurde und ein wahlfreier Zugriff auf ihre Elemente möglich ist. Die Interpolationssuche, auch Intervallsuche genannt, verbessert die binäre Suche unter der Voraussetzung einer Gleichverteilung der Daten. Ihre Laufzeit O(log(log n)) ist erst bei sehr großen Datenmengen besser als die der binären Suche. Hashing ermöglicht im Durchschnitt eine konstante Laufzeit O(1), benötigt im schlechtesten Fall aber lineare Zeit. Der Grover-Algorithmus wird auf Quantencomputern verwendet und ist bei unsortierten Listen quadratisch schneller als die klassische lineare Suche.
Bei der Suche in Bäumen werden Knoten untersucht. Ein Knoten wird aus einer Datenstruktur entnommen; seine Kindknoten werden geprüft und gegebenenfalls ebenfalls in diese Datenstruktur aufgenommen. Die Wahl der Datenstruktur bestimmt die Reihenfolge der Suche. Eine Warteschlange führt zur Breitensuche: Der Baum wird Ebene für Ebene durchsucht. Bei einem Stack, also einem Stapel, wird zunächst möglichst weit bis zu einem Blatt gesucht, bevor der nächste Kindknoten bearbeitet wird. Dieses Verfahren heißt Tiefensuche. Der Baum kann ausdrücklich vorhanden sein oder während der Suche erst erzeugt werden.
Suchalgorithmen spielen auch bei Problemen der Graphentheorie eine wichtige Rolle. Beispiele sind das Problem des Handlungsreisenden, die Berechnung kürzester Pfade und die Konstruktion eines minimalen Spannbaums. Kruskals, Dijkstras und Prims Algorithmus können als Erweiterungen von Verfahren zur Suche in Bäumen betrachtet werden.
Heuristische Suchalgorithmen
Heuristiken sind Strategien, die das Auffinden von Lösungen beschleunigen können. Dazu gehören Faustregeln, die Orientierung an Beispielen und die Nachbildung menschlicher Problemlöseprozesse. Deshalb wird zwischen uninformierter Suche, auch blinder Suche genannt, und informierter Suche unterschieden. Die informierte Suche nutzt Heuristiken, also zusätzliches Wissen zur Orientierung im Suchraum.
Die Entwicklung und Anwendung heuristischer Suchverfahren gehört üblicherweise zum algorithmischen Kern der Künstlichen Intelligenz. Anwendungsbereiche sind unter anderem das automatische Beweisen, die Steuerung von Robotern und Spiele. Dazu zählen Zwei-Personen-Spiele, also Nullsummenspiele mit vollständiger Information, beispielsweise Schach, Dame und Mühle, sowie Ein-Personen-Spiele wie Schiebepuzzles und Solitaire.
Zu den klassischen Verfahren der heuristischen Suche gehören A*, IDA*, bidirektionale Suchschemata, das Minimax-Verfahren und die Alpha-Beta-Suche. Heuristische Verfahren werden außerdem eingesetzt, wenn eine exakte Problemlösung zu rechenintensiv wäre. Dann kann ein gewisser Fehler in Kauf genommen werden: Auch eine nicht optimale Lösung wird akzeptiert, wenn sich dadurch die Rechenzeit deutlich verringert.
Optimierende und weitere Verfahren
Die optimierende Suche bearbeitet Optimierungsaufgaben, bei denen eine Reihe von Variablen mit Werten belegt werden muss. Weil sehr viele Variablen mit jeweils großen Wertebereichen vorkommen können, entsteht ein sehr großer Suchbereich, in dem herkömmliche Suchverfahren versagen können.
Bei diskreten Variablen werden insbesondere kombinatorische Suche und Backtracking eingesetzt. Für die analoge Suche nach Minima oder Maxima mehrdimensionaler Funktionen gibt es zahlreiche numerische Optimierungsverfahren. Welches Verfahren geeignet ist, hängt von den jeweiligen Ausgangsbedingungen ab. Ein weiteres Vorgehen nutzt das Feedback des Nutzers: Dieser bewertet die Relevanz der gefundenen Ergebnisse.
Suchverfahren für Zeichenketten suchen in einer Zeichenkette nach dem Auftreten eines Schlüssels. Bekannte Vertreter sind der Algorithmus von Knuth-Morris-Pratt, der Algorithmus von Boyer-Moore und der Karp-Rabin-Algorithmus. Evolutionäre Algorithmen verwenden Ideen aus der Evolutionstheorie als Heuristiken, um schneller gute Ergebnisse zu erhalten. Simulierte Abkühlung, englisch simulated annealing, ist ein auf Wahrscheinlichkeit beruhender Suchalgorithmus. Adversarial Search wird im Bereich der Künstlichen Intelligenz eingesetzt.
Leistungsvergleich
Die No-Free-Lunch-Theoreme zeigen, dass – gemittelt über alle mathematisch formulierbaren Probleme – alle Suchverfahren gleich gut sind. Ein Leistungsvorsprung entsteht daher jeweils nur bei einer speziellen Klasse von Problemen. Die Wahl eines geeigneten Suchverfahrens hängt folglich von den Eigenschaften des jeweiligen Suchraums und der konkreten Aufgabe ab.
