Suchalgorithmen

Suchalgorithmen Informatik

Die wichtigste Frage zuerst: Was ist überhaupt ein Suchalgorithmus?

Suchalgorithmen gehören zu den grundlegenden Methoden in der Informatik – genau wie die Sortieralgorithmen. Bei beiden ist die Laufzeit – also die Schnelligkeit des Algorithmus – ein wichtiger Faktor. Neben der Effizienz unterscheiden sich Suchalgorithmen auch anhand ihres Aufbaus, also der Art und Weise, wie sie implementiert werden können.

Suchalgorithmen Anwendung

Doch wofür werden Suchalgorithmen genau angewendet? Wie es der Name bereits verrät, werden mithilfe von Suchalgorithmen Daten, Listen oder Baumstrukturen durchsucht. Wann welcher Algorithmus verwendet wird, kannst Du den folgenden Abschnitten entnehmen.

Suchalgorithmen Arten

Es existiert eine Reihe verschiedener Arten von Suchalgorithmen:

• Einfache Suchalgorithmen

• Heuristische Suchalgorithmen

• Weitere Suchverfahren

In den nachfolgenden Abschnitten werden die drei Kategorien genauer beschrieben.

Einfache Suchalgorithmen

Der Hintergrund von einfachen Suchalgorithmen ist, dass sie meist abstrakter implementiert werden können. Außerdem können sie für eine Vielzahl von Problemen eingesetzt werden. Ein Nachteil ist jedoch, dass diese Algorithmen bei der Suche kein gutes Kosten-Nutzen-Verhältnis haben und meistens eine relativ lange Laufzeit besitzen.

Heuristische Suchalgorithmen

Im Gegensatz zu den einfachen Suchalgorithmen besitzen heuristische Verfahren genauere Informationen über die zu durchsuchende Datenmenge wie z. B. über die Verteilung der Daten. Bei den heuristischen Suchalgorithmen kann zusätzlich zwischen informierten und uninformierten Suchalgorithmen unterschieden werden.

Informierte Suchalgorithmen

Die informierte Suche besucht zunächst "vielversprechende" Knoten in einem Baum. Dafür werden entsprechende Zusatzinformationen benötigt, damit der Algorithmus weiß, welche Knoten zuerst durchlaufen werden sollten.

Informierte Suchverfahren gehören zu den sogenannten "heuristischen Suchalgorithmen". Verwendet werden diese Algorithmen vor allem dann, wenn die Komplexität und die Rechenleistung eines Algorithmus verringert werden soll.

Uninformierte Suchalgorithmen

Bei der uniformierten Suche werden Knoten in einem Baum einfach der Reihe nach durchlaufen.

Weitere Suchverfahren

Neben den beiden bereits genannten Kategorien gibt es noch weitere Suchverfahren, dazu gehören z. B.:

• Optimierende Suche

• Suchverfahren für Zeichenketten

Optimierende Suche

Suchverfahren für Zeichenketten

Ein Suchverfahren für eine Zeichenkette sucht innerhalb einer solchen nach einem bestimmten Schlüssel. Diese Art von Verfahren zählen zu den sogenannten "String-Matching-Algorithmen", dazu zählen z. B.:

• Knuth-Morris-Pratt Algorithmus
• Boyer-Moore Algorithmus
• Karp-Rabin Algorithmus

Suchalgorithmen Beispiele

Weitere Beispiele für Suchalgorithmen findest Du in den nachfolgenden Abschnitten.

Lineare Suche

Zu den einfachen Suchalgorithmen gehört die lineare oder auch sequentielle Suche. Sie wird in der Regel bei ungeordneten Arrays verwendet und eignet sich vor allem bei eher kleineren Datenmengen.

Binäre Suche

Eine effektivere Variante ist die binäre Suche. Die Voraussetzung bei einer binären Suche ist allerdings, dass die Datenmenge vorher sortiert wurde. Bei der binären Suche wird nach dem "Teile-und-Herrsche-Prinzip" vorgegangen.

Die Vorgehensweise bei der binären Suche ist folgende:

• Mittleres Element suchen und mit gesuchtem Element vergleichen

  • Ist es kleiner, suche in der rechten Hälfte weiter

  • Ist es größer, suche in der linken Hälfte

• "Neue" Datenmenge erneut halbieren und das gesuchte Element mit dem mittleren Element vergleichen

• Das ganze so lange weiter durchführen, bis das gesuchte Element gefunden wurde

Interpolationssuche

Die Interpolationssuche ist eine Modifizierung der binären Suche. Der Unterschied liegt darin, dass die Interpolationssuche Daten nicht in der Mitte unterteilt, sondern die Größe der Teilmengen dynamisch gewählt werden können.

Das hat den Vorteil, dass Du die Trennung anhand des gesuchten Wertes wählen kannst. Suchst Du z. B. einen niedrigen Wert, kannst Du die Datenmenge in einem entsprechend niedrigen Bereich trennen und musst im Zweifelsfalls weniger Daten nach Deinem gesuchten Wert durchsuchen.

Binäre (Such-)Bäume

Eine weitere Möglichkeit um zu Suchen sind binäre und nicht binäre Suchbäume. Dabei ist das Prinzip ein ähnliches: Bei Suchen in Bäumen werden die einzelnen Knoten nacheinander durchgegangen. Die Vorgehensweise ist folgende:

• Entnehme einen Knoten aus einem Suchbaum
• Untersuche seine Kindknoten

In welcher Reihenfolge Du einen Baum durchsuchst, hängt vor verwendeten Verfahren ab. Dabei kannst Du z. B. die Breitensuche und die Tiefensuche unterscheiden. Auch Suchbäume enthalten bereits sortierte Datensätze, die je nach Art des Baumes aufsteigend oder absteigend sortiert sein können.

Suche in Graphen

Auch Suchen in Graphen können durch verschiedene Suchalgorithmen gelöst werden. Algorithmen, die Du dafür verwenden kannst, sind:

• Dijkstra Algorithmus

• Kruskal Algorithmus

• Prim Algorithmus

Hash-Suche/Hash-basierte Suche

Außerdem gibt es noch die Möglichkeit, mittels Hashverfahren zu suchen. Die Idee dahinter ist mithilfe eines Schlüssels, einer Hashfunktion und einer dazugehörigen Hashadresse eine sogenannte Hashtabelle zu erzeugen. Die Hashadresse gibt dabei genau an, an welcher Stelle, bzw. in welchem Feld sich der Datensatz befindet. In einer solchen Hashtabelle ist es nun möglich, Datensätze zu suchen.

Suchalgorithmen Übersicht

Nachfolgend findest Du eine Übersicht verschiedener Suchverfahren und ihrer wichtigsten Vor- und Nachteile:

Suchalgorithmen Vergleich

Die Kriterien zum Vergleich von Suchalgorithmen sind vergleichbar mit denen für Sortieralgorithmen. Dazu gehören z. B.:

• Laufzeit / Komplexität

• Zusätzlicher Speicherbedarf / Platzkomplexität

• Stabilität

• Intern vs. extern / in-place vs. out-of-place

• Rekursiv vs. iterativ

Suchalgorithmen Laufzeit

Die Laufzeit von Suchalgorithmen wird in den Best-Case, Average-Case und den Worst-Case unterschieden. Angegeben wird die Laufzeit mithilfe der sogenannten O-Notation.

In der folgenden Übersicht sind die Laufzeiten von verschiedenen Suchalgorithmen auf einem Blick zusammengefasst. Steht nichts explizit dabei, ist der Average-Case angegeben.