Algorithmen für Dummies,

Algorithmus

Beschreibung

A*-Suche

Der Algorithmus berechnet während der Untersuchung der Knoten fortlaufend die damit verbundenen Kosten. Dies geschieht anhand der Gleichung f(n) = g(n) + h(n), wobei:

n für den Knoten steht,

g(n) die entstandenen Kosten bis zum Erreichen des Knotens sind,

h(n) die geschätzten Kosten vom Knoten bis zum Ziel sind und

f(n) die geschätzten Kosten des Wegs von n bis zum Ziel sind.

Die Idee hierbei ist, zuerst die aussichtsreichsten Wege zu durchsuchen und kostenintensive Wege zu vermeiden.

Balancierter Baum

Eine besondere Art von Baum, der durch Umordnen eine balancierte Struktur bewahrt. Hierdurch lassen sich Aufrufzeiten reduzieren. Die Anzahl der Elemente auf der linken Seite unterscheidet sich von der Anzahl der Elemente auf der rechten Seite höchstens um 1.

Bidirektionale Suche

Bei dieser Technik wird gleichzeitig vom Wurzelknoten und vom Zielknoten aus gesucht, bis sich die Wege beider Suchen in der Mitte treffen. Ein Vorteil dieses Ansatzes ist, dass er nicht sehr zeitaufwändig ist, weil er die Lösung schneller als viele andere Brute-Force-Ansätze findet. Zudem ist er im Vergleich zu anderen Ansätzen sparsamer hinsichtlich des Speicherplatzverbrauchs und findet garantiert eine Lösung. Der größte Nachteil ist die Kom­­plexität der Implementierung.

Binärer Baum

Bei dieser Art von Baum ist ein Knoten jeweils mit keinen (im Fall eines Blattknotens), einem oder zwei (bei inneren Knoten) anderen Knoten verbunden. Durch jeden Knoten werden drei wichtige Aspekte definiert: Datenspeicher, linke und rechte Verbindung.

Breitensuche

Diese Technik setzt am Wurzelknoten an und untersucht zunächst jeden der Kinderknoten. Anschließend geht sie zur nächsten Ebene über. So durchläuft sie Ebene für Ebene, bis eine Lösung gefunden wurde. Der Nachteil dieses Algorithmus ist, dass jeder Knoten abgespeichert werden muss, was bei großen Knotenmengen entsprechend viel Speicherplatz beansprucht. Die Breitensuche kann doppelt vorkommende Knoten finden, was Zeit spart. Eine Lösung ist immer garantiert.

Brute-Force-Methode

Bei diesem Ansatz wird jede mögliche Lösung ausprobiert, um darunter die beste Lösung zu finden. Brute-Force-Techniken finden immer die beste Lösung, sind jedoch dermaßen zeitaufwändig in der Implementierung, dass sie meistens nicht verwendet werden.

Dijkstra

Dieser Algorithmus findet den kürzesten Weg in einem gerichteten, positiv gewichteten Graphen.

Gierige Bestensuche

Dieser Algorithmus wählt stets diejenige Strecke aus, die sich am nächsten zum Zielpunkt befindet. Dies geschieht anhand der Gleichung f(n) = h(n). Der Algorithmus findet in der Regel sehr schnell eine Lösung, kann jedoch auch in Schleifen hängen bleiben. Aus diesem Grund stellt er oftmals keinen optimalen Lösungsansatz dar.

Gieriger Algorithmus

Bei dieser Technik wird für die Gesamtlösung das beste Ergebnis aus jedem einzelnen Schritt des Lösungsprozesses genommen. Gierige Algorithmen gehen von zwei Annahmen aus:

Es ist möglich, in jedem Schritt die eine optimale Wahl zu treffen.

Trifft man in jedem Schritt die optimale Wahl, lässt sich hierdurch eine optimale Lösung des Gesamtproblems finden.

Graph

Ein Graph ist eine Art Erweiterung eines Baums. Wie auch bei Bäumen können zwischen den Knoten eines Graphen Verbindungen bestehen. Anders als bei binären Bäumen können bei Graphen jedoch mehr als eine oder zwei Verbindungen von einem Knoten ausgehen. Graphknoten haben oftmals sogar sehr viele Verbindungen. Sie werden beispielsweise in GPS-Karten und in vielen anderen Anwendungen eingesetzt, wo der Top-Down-Ansatz für Bäume nicht funktioniert.

Hashing

Bei dieser Methode wird vorhergesagt, wo sich ein bestimmtes Datenobjekt in einer beliebigen Datenstruktur befindet, bevor man mit der eigentlichen Suche beginnt. Hierzu werden Schlüssel eingesetzt, die in einem Index abgelegt sind: Der Schlüssel wird zunächst durch eine Hashfunktion in einen numerischen Wert umgewandelt, den der Algorithmus in einer Hashtabelle ablegt. Anhand der Hashtabelle lässt sich ein Index erstellen, der auf die Elemente in der Datenstruktur verweist, sodass der Algorithmus die Position der Daten leicht vorhersagen kann.

Heap

Hierbei handelt es sich um eine raffinierte Baumstruktur, in die sich Daten einfügen lassen. Durch dieses Einfügen lässt sich der Sortiervorgang beschleunigen. Die Bäume können weiter in sogenannte Max-Heaps und Min-Heaps unterteilt werden, je nachdem, ob der Heap sofort den maximalen oder den minimalen Wert im Baum ausgibt.

Heuristik

Diese Problemlösetechnik beruht auf Erfahrungen und gibt Ergebnisse aus, die zwar nicht optimal, jedoch gut genug sind, sodass eine bessere Lösung nicht mehr nötig ist. Hierbei lässt man sich durch den Algorithmus potentiell nützliche Lösungswege aufzeigen. Anschließend ist man jedoch trotzdem auf menschliche Intuition und Vernunft angewiesen, um zu wissen, ob es sich bei dem Ergebnis tatsächlich um die richtige Lösung handelt.

MapReduce

Mithilfe dieser Grundstruktur können Algorithmen auf mehreren vernetzten Computern parallele Berechnungen ausführen, wodurch Ergebnisse schneller erzielt werden.

Mergesort

Mergesort ist eine universelle, vergleichsbasierte Methode des Datensortierens. Zur Ausführung macht man von einem Teile-und-herrsche-Ansatz Gebrauch.

Nash-Gleich­gewicht

Dies ist ein Begriff aus der Spieltheorie. Er beschreibt eine Situation, in der jedem Spieler die Strategie der anderen Spieler bekannt ist, sodass kein Spieler durch die Änderung seiner Strategie einen Vorteil hat. Diese Theorie wird auf Konfliktsituationen angewandt, bei denen ein Spieler die Entscheidungen aller beteiligten Spieler berücksichtigen muss, wenn er das Spiel gewinnen will.

PageRank

Der PageRank-Algorithmus misst die Wichtigkeit eines Knotens in einem Graphen. Dieser Algorithmus bildet die wesentliche Grundlage für die Kernalgorithmen von Google, die die relevantesten Ergebnisse einer Suchanfrage ausgeben.

Quicksort

Dies ist ein allgemeines Sortierverfahren, bei dem ein Datenarray durch einen Teile-und-herrsche-Ansatz in kleinere Datenarrays zerlegt wird.

Rein heuristische Suche

Dieser Algorithmus durchläuft die Knoten in der Reihenfolge ihrer Kosten und legt dabei zwei Listen an. Eine geschlossene Liste enthält bereits besuchte Knoten, während eine offene Liste diejenigen Knoten enthält, die noch besucht werden müssen. Bei jeder Iteration wählt der Algorithmus den Knoten mit den niedrigsten Kosten aus. Alle Kinderknoten dieses Knotens werden in der geschlossenen Liste abgelegt und die jeweiligen Kosten berechnet. Der Algorithmus legt sodann alle Kinderknoten mit niedrigen Kosten wieder in der offenen Liste ab und löscht die Kinderknoten mit hohen Kosten. So führt er eine intelligente, kostenbasierte Suche nach der Lösung aus.

Teile und herrsche

Bei diesem Lösungsansatz wird die Aufgabe in kleinstmögliche Teile zerlegt und mithilfe des einfachsten Ansatzes gelöst. Dies spart im Vergleich zu anderen Ansätzen wie etwa dem Brute-Force-Ansatz viel Zeit und Ressourcen. Jedoch ist eine optimale Lösung nicht immer garantiert.

Tiefensuche

Diese Technik setzt am Wurzelknoten an und untersucht dann eine Menge von verbundenen Kinderknoten, bis sie einen Blattknoten erreicht. Sie durchläuft Zweig um Zweig, bis sie eine Lösung findet. Der Nachteil dieses Algorithmus ist, dass er nicht nach doppelt vorkommenden Knoten suchen kann; das bedeutet, dass er die gleichen Knotenwege mehr als einmal durchlaufen könnte. Es kann sogar sein, dass dieser Algorithmus gar keine Lösung findet, sodass Sie eine obere Grenze definieren müssen, damit der Algorithmus nicht ewig weitersucht. Ein Vorteil dieses Ansatzes ist, dass er speicherplatzfreundlich ist.

Unbalancierter Baum

Bei diesem Baum werden je nach Bedarf neue Datenelemente eingefügt, ohne dass dabei die Balance des Baums berücksichtigt wird. Durch diese Methode des Hinzufügens wird der Baum schneller aufgebaut, bei Such- oder Sortiervorgängen jedoch langsamer abrufbar.