Suche (Informatik)

Ein binärer Suchbaum der Größe neun und der Tiefe drei

In der Informatik bedeutet das Suchen den Vorgang, einen oder mehrere Datensätze aus einer Menge von Datensätzen zu identifizieren. Dabei wird ein Suchschlüssel vorgegeben, der die Kriterien für die zu findenden Datenobjekte vorgibt.

Zum systematischen Suchen in Datenmengen gibt es in der Informatik verschiedene Suchverfahren. Suchprobleme sind hier (in der Status-basierten Suche) durch einen Startzustand, einen Endzustand (beide meistens in einer symbolischen Repräsentation) definiert, zusätzlich eine Menge von Operatoren, welche durch Anwendung auf den Startzustand den Suchraum aufspannen und letztlich noch eine Funktion, welche einem sagt, ob der aktuelle Zustand mit der Zielzustandsbeschreibung übereinstimmt.

Es ist zu beachten, dass die Lösung eines Problems ganz allgemein immer als Suche nach der Lösung in einer Menge von möglichen Lösungen (dem Lösungsraum) verstanden werden kann. Eine Lösung kann nur der Zielzustand sein, aber auch der Pfad zum Ziel oder die Operatorenreihenfolge. Ist der Suchraum endlich, so führt die Suche (eine geeignete Suchstrategie vorausgesetzt) immer zu einem Ergebnis - bei unendlichen (Lösungs-)Mengen muss die Suche nach gewissen Kriterien (z. B. nach einer bestimmten Zeit) abgebrochen werden.

Die Suche in einer endlichen Menge kann dadurch effizient gestaltet werden, dass über den Daten ein Suchindex (z. B. in Form eines B-Baums) erstellt wird, der nach einem bestimmten Kriterium sortiert ist – so müssen nicht mehr alle Einträge betrachtet werden, um einen bestimmten zu finden (z. B. in einem Telefonbuch). Dieses Vorgehen ist sehr wichtig für die Funktionsfähigkeit von Datenbanken und Suchmaschinen.

Unterschieden wird in der Informatik zwischen Brute-Force-Suche (durch uninformierte Suche den kompletten Suchraum durchsuchen, oft ein intraktables Problem bei NP-schweren Problemen) und heuristischer Suche (geschicktes Raten der Operatoren, die Effizienz wird oft stark verbessert, aber es gibt keine Garantie, dass diese Heuristiken immer ein Ergebnis liefern); Erwähnenswert ist hier der oft benutzte A* Algorithmus.

Siehe auch

• Suchmaschine – ein Programm zur Recherche von Dokumenten in einem Computer oder einem Computernetzwerk.
• Suchfunktion – die Funktion eines Produkts (oft Software), die einen Datensatz in einer Datenmenge findet
• String Matching – eine gegebene Zeichenkette innerhalb einer anderen finden.
• Pattern Matching – ein gegebenes Muster in einem Suchbereich wiederfinden.
• Suchproblem – zu einer gegebenen Suche eine bestmögliche Lösung suchen (Suchoptimierung).
• Desktopsuche – Applikation zum Durchsuchen des Datenbestandes eines Computers