Suchverfahren

In der Informatik bezeichnet man als Suchverfahren bzw. Suchalgorithmus - in weitem Sinne - einen Algorithmus, dem ein Problem als Eingabe übergeben wird und der die Lösung des Problems zurückgibt.

Die meisten von Informatikern untersuchten Algorithmen sind somit in gewisser Hinsicht Suchalgorithmen. Die Menge aller möglichen Lösungen zu einem bestimmten Problem wird als Suchraum (eng. Search Space) bezeichnet. Man unterscheidet einfache und heuristische Suchalgorithmen. Einfache Suchalgorithmen benutzen die einfachsten, intuitivsten Methoden für das Durchsuchen des Suchraumes, während heuristische Suchalgorithmen Wissen über den Suchraum(beispielsweise die Datenverteilung) mit einbeziehen um die benötigte Suchzeit zu reduzieren.

Einfache Suchalgorithmen

Einfache Suchalgorithmen vernachlässigen die spezielle Natur des jeweiligen Problems. Deshalb können sie allgemeiner und abstrakter implementiert werden, wodurch dieselbe Implementation für eine große Auswahl von Problemen verwendet werden kann. Der Nachteil einfacher Suchalgorithmen sind die entstehenden Kosten: Der Suchraum von Suchproblemen ist im Allgemeinen sehr groß, einfaches Suchen läuft jedoch nur in kleinen Suchräumen in annehmbarer Zeit ab.

Suche in Listen

Algorithmen zur Suche in Listen sind die einfachsten Suchalgorithmen überhaupt. Das Ziel der Suche in Listen ist es, ein bestimmtes Element einer Liste zu finden, von dem der zugehörige Schlüssel bekannt ist. Da dieses Problem in der Informatik oft anzutreffen ist, sind die verwendeten Algorithmen - sowie deren Komplexität - sehr gut untersucht.

Der einfachste Suchalgorithmus für Listen ist die lineare Suche. Bei ihr wird solange ein Element nach dem anderen durchlaufen, bis ein Element mit dem gesuchten Schlüssel angetroffen wird. Die lineare Suche hat eine Laufzeit von O(n) (n ist die Anzahl der Elemente der Liste) und kann sowohl auf sortierte als auch unsortierte Listen angewendet werden. Ein fortgeschrittenes Verfahren ist die binäre Suche mit einer Laufzeit von O(log n). Für große Listen ist sie viel effektiver als die lineare Suche, setzt jedoch voraus, dass die Liste vorher sortiert wurde und ein wahlfreier Zugriff auf die Elemente möglich ist. Die Interpolationssuche ist eine Verbesserung der binären Suche, die eine Gleichverteilung der Daten voraussetzt. Die Laufzeit O(log(log n)) ist nur für sehr große Datenmengen besser als die der binären Suche. Ein weiterer Suchalgorithmus für Listen ist Groovers Algorithmus, der auf Quantencomputern zum Einsatz kommt und quadratisch schneller als die klassische lineare Suche für unsortierte Listen abläuft. Für die Suche in Listen kann auch Hashing verwendet werden, das im Durchschnitt eine konstante Zeit O(1) benötigt, im schlechtesten Fall jedoch linear ist.

Suche in Bäumen

Die Suche in Bäumen ist die Königsdisziplin unter den Suchalgorithmen. Sie durchsucht Knoten von Bäumen, unabhängig davon ob der Baum explizit oder implizit(während der Suche generiert) ist. Dabei wird folgendes Prinzip angewendet: Ein Knoten wird aus einer Datenstruktur entnommen. Seine Kindknoten werden untersucht und gegebenenfalls der Datenstruktur hinzugefügt. Je nach Auswahl der Datenstruktur kann der Baum in verschiedenen Reihenfolgen durchsucht werden. Die Verwendung einer Queue führt so zu einer Breitensuche, bei der der Baum Ebene für Ebene durchlaufen wird. Bei Verwendung eines Stacks hingegen, wird jeweils bis zu einem Blatt gesucht und erst anschließend mit dem nächsten Kindknoten fortgefahren. Dies wird als Tiefensuche bezeichnet.

Suche in Graphen

Viele Probleme der Graphentheorie können mit Hilfe von Suchalgorithmen gelöst werden. Beispiele für diese Algorithmen sind Dijkstras Algorithmus, Kruskals Algorithmus, Problem des kürzesten Weges oder Prims Algorithmus, die als Erweiterungen der Algorithmen für die Suche in Bäumen gesehen werden können.

Heuristische Suche

Es gibt nur wenige weithin bekannte heuristische Suchalgorithmen, da sie problemspezifisch sind und somit nicht gut übertragen werden können. Ein Beispiel für ein heuristisches Verfahren ist eine Hashtabelle mit einer Hashfunktion, die auf ein konkretes Problem optimiert wurde. Für gewöhnlich basieren heuristische Suchalgorithmen jedoch auf der Durchsuchung von Bäumen. Zu diesen zählen die Best-first search und A*. Ähnlich den einfachen Suchverfahren können auch die heuristischen Suchverfahren für Bäume an Graphen angepasst werden.

Optimierende Suche(?)

Diese Art der Suche löst Optimierungsaufgaben, bei der eine Reihe von Variablen mit Werten belegt werden muss. Da es sich dabei um sehr viele Variablen mit sehr großem Wertebereich handeln kann, ist der Suchbereich sehr groß und herkömmliche Suchverfahren versagen. Kombinatorische Suche und Backtracking sind Verfahren die bei der optimierenden Suche zum Einsatz kommen.

Andere Suchverfahren

Suchverfahren für Zeichenketten suchen, wie der Name schon sagt, in Zeichenketten nach einem Schlüssel. Bekannte Vertreter sind der Algorithmus von Knuth-Morris-Pratt, der Algorithmus von Boyer sowie der Algorithmus von Rabin-Karp.

Genetische Algorithmen benutzen Ideen aus der Evolutionslehre als Heuristiken, um den Suchraum zu verkleinern.

Simulated Annealing ist ein auf Wahrscheinlichkeit beruhender Suchalgorithmus.

Adversarial Search wird im Bereich der künstlichen Intelligenz eingesetzt.

Siehe auch: Liste von Algorithmen, Sortierverfahren