Die wichtigsten Infos rund um Suchalgorithmen, 2. Teil
Zusammen mit Datenstrukturen sind Algorithmen zentrale Konzepte in der Informatik. Sie haben großen Einfluss auf die Qualität und die Effizienz von Softwarelösungen. Während die Datenstrukturen definieren, in welcher Form Daten organisiert und gespeichert werden, liefern Algorithmen bestimmte Methoden, um ein Problem zu lösen. Bei einem Algorithmus ist wichtig, dass er genau und effizient ist.
Außerdem muss er für viele Daten funktionieren und die jeweilige Aufgabe in einer vorhersehbaren Zeit abschließen können. Suchalgorithmen sind Algorithmen, die eingesetzt werden, um bestimmte Daten oder Datenelemente innerhalb einer Datenstruktur zu finden.
In einem zweiteiligen Beitrag haben wir die wichtigsten Infos rund um Suchalgorithmen zusammengestellt. Dabei haben wir im 1. Teil beantwortet, was genau Suchalgorithmen sind, in welchen Arten es sie gibt und wie sie funktionieren.
Hier ist der 2. Teil!:
Inhalt
Welche weiteren Verfahren können Suchalgorithmen noch nutzen?
Neben der linearen und der binären Suche können Suchalgorithmen noch auf andere Verfahren zurückgreifen. Dazu gehören Suchbäume, die Suche in Graphen und die hash-basierte Suche.
Suche in Bäumen
Binäre und nicht binäre Suchbäume bieten eine weitere Möglichkeit, um Datenstrukturen zu durchzusuchen. Dabei werden die einzelnen Knoten nacheinander durchlaufen. Dazu wird zunächst ein Knoten aus dem Suchbaum entnommen und anschließend seine Kindknoten untersucht.
Die Reihenfolge, in der der Baum durchsucht wird, richtet sich nach dem verwendeten Verfahren.
Suchbäume enthalten bereits geordnete Datensätze, die je nach Art des Baumes aufsteigend oder absteigend sortiert sein können. Um nun Knoten in einem Graphen zu finden, kann entweder die Breitensuche oder die Tiefensuche zum Einsatz kommen.
-
Die Breitensuche wird auch als breadth-first-search bezeichnet. Hier werden zunächst alle die Nachbarn überprüft, die sich in nächster Nähe zum aktuellen Knoten befinden.
-
Im Unterschied dazu bearbeitet die Tiefensuche, auch depth-first-search genannt, zuerst alle Kindknoten eines Knotens.
Beide Verfahren gehören in die Gruppe der uniformierten Suchalgorithmen.
Suche in Graphen
Für die Suche in Graphen bieten Suchalgorithmen ebenfalls verschiedene Lösungen. Zu den gängigsten gehören der Dijkstra, der Kurskal und der Prim Algorithmus.
Dijkstra Algorithmus
Der niederländische Mathematiker E. W. Dijkstra entwickelte 1959 einen Algorithmus, um die kürzesten Wege in gewichteten Graphen zu finden. Heute nutzen die meisten Routenplaner und Navigationsgeräte diesen Algorithmus.
Bei dem Verfahren werden zuerst die kürzesten Wege in einem Teil des Gesamtgraphen bestimmt. Anschließend wird dieser Teil schrittweise vergrößert und gleichzeitig überprüft, wie sich die Vergrößerung auf den kürzesten Weg auswirkt.
Die Idee dahinter ist, dass wenn der kürzeste Weg von A nach C durch B verläuft, das Pfadsegment zwischen A und B die kürzeste Verbindung zwischen diesen beiden Punkten ist.
Der Dijkstra Algorithmus setzt aber voraus, dass alle Werte positiv sind. Sobald negative Zahlen auftreten, funktioniert der Algorithmus nicht mehr.
Kruskal Algorithmus
1956 veröffentliche Joseph B. Kruskal einen Algorithmus, der die kürzeste Verbindung zwischen einem Knoten zu allen Knoten eines Graphen findet.
Als sogenannter Greedy Algorithmus berechnet das Verfahren effizient den Spannbaum eines verbundenen, gewichteten, ungerichteten Graphen und wählt bei jedem Schritt die lokal beste Variante aus, um auf dieser Basis auch die global optimale Lösung zu finden.
Die Grundidee dabei ist simpel:
-
Eine Verbindung wird in der Reihenfolge der Länge betrachtet, beginnend mit der kürzesten.
-
Verbindet eine Kante zwei Knoten, die noch nicht verbunden sind, ist sie Teil der Lösung. Andernfalls wird sie verworfen.
-
Dies wird so lange wiederholt, bis n-1 Verbindungen für die Lösung gefunden sind.
Der Kruskal Algorithmus arbeitet mit einer Liste, die alle Kanten des ursprünglichen Graphen in sortierter Form enthält. Jede dieser Kanten wird verworfen oder in die Konstruktion des jeweiligen minimalen Spannbaums integriert. Anschließend wird aus den Teilbäumen nach und nach ein minimaler Spannbaum aufgebaut.
Prim Algorithmus
Der nach Robert C. Prim benannte und 1957 veröffentlichte Prim Algorithmus gehört zu den einfachsten Algorithmen, um das Problem mit dem minimalen Spannbaum zu lösen.
Die Schritte des Verfahrens gestalten sich wie folgt:
-
Der Ausgangspunkt ist ein beliebiger Startknoten.
-
Alle Kanten der benachbarten Knoten werden in die Nachbarliste eingefügt. Aus der Nachbarliste wird eine Kante mit minimaler Länge ausgewählt und in den initialisierten Spannbaum eingefügt.
-
Von diesem Punkt aus wird auf Basis der ausgewählten Kante erneut der kürzeste Pfad zum nächsten Knoten ausgewählt. Wurde dieser Knoten schon besucht, wird er ignoriert.
-
Dieser Ablauf wird so lange wiederholt, bis alle Knoten besucht wurden.
Der Algorithmus führt n-1 Wiederholungen durch, wobei n die Anzahl der Knoten im Graphen entspricht. Wie der Kruskal Algorithmus liefert damit auch der Prim Algorithmus einen minimalen Spannbaum von einem verbundenen, gewichteten, ungerichteten Graphen nach dem Greedy Prinzip.
Hash-basierte Suche
Eine weitere Möglichkeit ist, ein Hashverfahren für die Suche einzusetzen. Dafür wird mit einem Schlüssel, einer Hashfunktion und einer Hashadresse eine sogenannte Hashtabelle erzeugt.
Die Hashadresse gibt präzise an, in welchem Feld sich der Datensatz befindet. Die Datensätze können dann in so einer Hashtabelle gesucht werden.
Anhand welcher Kriterien lassen sich Algorithmen miteinander vergleichen?
Die unterschiedlichen Algorithmen helfen dabei, viele verschiedene Probleme zu lösen. Um den Suchalgorithmus auszuwählen, der für die jeweilige Aufgabe am besten geeignet ist, müssen aber mehrere Kriterien berücksichtigt werden.
Zu diesen Kriterien gehören:
-
Laufzeit
-
benötigter Speicherplatz
-
Stabilität
-
Fehleranfälligkeit
-
Reaktion auf Datenänderungen
Es kann sinnvoll sein, einen Algorithmus an den Kontext anzupassen. Denn ein Algorithmus, der zum Beispiel für große Datensätze optimiert ist, kann bei kleinen Datensätzen zu langsam werden.
Genauso ist möglich, dass ein Suchalgorithmus nur sortierte Datenmengen verarbeiten kann und deshalb die Datensätze jedes Mal erst neu sortiert werden müssen, wenn frische Daten dazukommen.
Und generell eignet sich nicht jeder Algorithmus gleich gut für jede Aufgabe. Mitunter ist ein Suchalgorithmus für bestimmte Funktionen sogar komplett ungeeignet.
Die Laufzeit bei Suchalgorithmen
Zu den wichtigsten Kriterien bei Suchalgorithmen gehört die Laufzeit, bei der zwischen dem Best Case, dem Average Case und dem Worst Case unterschieden wird. Die Angabe der Laufzeit erfolgt mithilfe der sogenannten O-Notation.
In der Informatik ist die O-Notation eine Methode, die den Aufwand von Algorithmen bzw. die Komplexität von Funktionen in Abhängigkeit zu ihrer Eingabegröße einordnet. Dadurch kann verglichen werden, wie effizient Algorithmen sind.
Angegeben wird die Komplexität durch O(n), wobei n die Größe eines Datensatzes ist. O(n) bezeichnet ein lineares Wachstum der Rechenzeit. Verdoppelt sich n, verdoppelt sich also auch die Rechenzeit. O(1) hingegen bedeutet, dass die Rechenzeit von n unabhängig ist.
Mehr Ratgeber, Tipps und Anleitungen:
- Die wichtigsten Infos rund um Suchalgorithmen, 1. Teil
- KI-basierte Code-Sicherheit: Wie KI-Systeme unser digitales Leben sicherer machen
- 3 wichtige Aufgaben von KI-Systemen im Recruiting
- Starlink als Mittel zur Förderung von Bildung und Wissenschaft
- 7 Tipps für einen DSGVO-gerechten Umgang mit Daten im Homeoffice
- Leitfaden: SEO und Social-Media – Wirtschaftliche und geschäftliche Leistungsvorteile
- Lehrplan für das Schulfach Informatik
- Tabelle CMS-Systeme und Homepagebaukästen für Webseiten und Webdesign
Thema: Die wichtigsten Infos rund um Suchalgorithmen, 2. Teil
Übersicht:
Fachartikel
Verzeichnis
Über uns
- Die 5 größten Gefahren für externe Festplatten - 6. April 2024
- Eine E-Mail an mehrere Empfänger verschicken – so geht’s richtig - 15. März 2024
- Grundlegendes Wissen zu verteilten Datenstrukturen, 2. Teil - 7. März 2024