Hase-Igel-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Hase-Igel-Algorithmus ist ein Verfahren, mit dem in einer einfach verketteten Liste Schleifen mit der Zeitkomplexität O(n) und einer Platzkomplexität von O(1) gefunden werden können. Mathematisch betrachtet dient der Algorithmus zum Auffinden von Zyklen in Folgen. Er ist auch unter dem Namen Floyds Algorithmus zum Auffinden von Schleifen (englisch Floyd's cycle-finding algorithm) bekannt und darf nicht mit Floyds Algorithmus aus der Graphentheorie verwechselt werden.
Inhaltsverzeichnis |
[Bearbeiten] Bedeutung in der Mathematik
Neben der trivial ersichtlichen Verwendung zum Auffinden von Schleifen in zur Ablage von Daten genutzten Listen ist der Hase-Igel-Algorithmus die Grundlage der Pollard-Rho-Methode zur Bestimmung der Periodenlänge einer Zahlenfolge einschließlich der darauf zurückführbaren Primfaktorzerlegung.
Der Algorithmus wird auch im Themenfeld der pseudozufälligen Folgen eingesetzt.
[Bearbeiten] Prinzip
Der Algorithmus besteht aus dem gleichzeitigen Durchlauf der Liste mit unterschiedlichen Schrittweiten. Dabei werden zwei Zeiger auf Listenelemente benutzt, von denen der eine (Igel) bei jeder Iteration auf das nächste Element verschoben wird, während der andere (Hase) bei derselben Iteration auf das übernächste Element verschoben wird. Wenn die beiden Zeiger sich begegnen, also dasselbe Element referenzieren, hat die Liste eine Schleife. Wenn einer der beiden Zeiger das Ende der Liste erreicht, hat sie keine Schleife.
[Bearbeiten] Begründung
Am besten kann die Vorgehensweise visualisiert werden, indem in einem gezeichneten Diagramm der Weg der beiden Zeiger verfolgt wird. Es ist leicht ersichtlich, dass sowohl bei einer Schleife mit ungerader Anzahl von Elementen als auch bei einer Schleife mit gerader Anzahl der Hase in höchstens einem Durchlauf des Igels auf diesen trifft.
Weil mit jedem Schritt des Igels der Hase einen Schritt näher an den Igel heran kommt, terminiert der Algorithmus in endlicher Zeit.
[Bearbeiten] Performance-Betrachtung
Im besten Fall (best case performance) sind bei einer zyklischen Liste mit m + n Elementen mit n als Länge des Zyklus und m als Anzahl der Elemente vor dem Beginn des Zyklus m Schritte notwendig, da der Igel mindestens den Anfang des Zyklus erreichen muss, bevor der Hase ihn auf einer zweiten Runde einholen kann.
Im schlechtesten Fall (worst case performance) sind m + n / 2 Schritte notwendig, weil der Igel nicht weiter als bis zur Mitte des Zyklus gelangen kann bevor der Hase diese zum zweiten Mal passiert.
[Bearbeiten] Implementierungen
[Bearbeiten] C
#include <stdio.h>
#include <stdlib.h>
int main() {
struct liste { struct liste *next; } *root, *el, *hase, *igel;
int i;
// Liste erzeugen.
root = el = malloc(sizeof(struct liste));
for(i=0; i<5; ++i) {
struct liste *eneu = malloc(sizeof(struct liste));
el->next = eneu;
el = eneu;
}
// Zyklischen Verweis vom letzten auf das zweite Element anlegen.
el->next = root->next;
// Hase-Igel-Algorithmus.
igel = root;
hase = root->next;
while(hase && hase != igel) {
printf("%p %p\n", hase, igel);
igel = igel->next;
hase = hase->next;
if(hase) hase = hase->next;
}
if(hase) puts("Zyklus gefunden!");
else puts("Liste ist nicht zyklisch!");
return 0;
}
[Bearbeiten] Vergleich mit anderen Ansätzen zur Schleifenerkennung
[Bearbeiten] Jeden Knoten merken
[Bearbeiten] Ansatz
Jeder durchlaufene Knoten wird in einer geeigneten Struktur gespeichert.
[Bearbeiten] Probleme
- Das Verfahren benötigt sehr viel Speicherplatz und Rechenleistung und ist daher ungeeignet für große Listen.
[Bearbeiten] Doppelte Verkettung nutzen
[Bearbeiten] Ansatz
In einer doppelt verketteten Liste hat jedes Element sowohl einen Zeiger auf das folgende als auch auf das vorhergehende Element. Beim Durchlauf einer solchen Liste muss also jedes Element das vorher besuchte als vorhergehendes Element referenzieren. Wenn das nicht so ist, muss die Liste eine Schleife haben, da - Korrektheit der Verkettung vorausgesetzt - zu diesem besuchten Element zwei Zeiger existieren.
[Bearbeiten] Probleme
- Das Verfahren funktioniert nur, wenn die doppelte Verkettung nicht fehlerhaft ist.
- Eine Schleife über die ganze Liste muss gesondert am Zeiger auf das vorhergehende Element des Startelements geprüft werden.
[Bearbeiten] Jeden Knoten markieren
[Bearbeiten] Ansatz
Die Liste wird durchlaufen; dabei wird jeder Knoten markiert. Wenn ein markierter Knoten getroffen wird, hat die Liste eine Schleife.
[Bearbeiten] Probleme
- Das Verfahren funktioniert nicht, da die Liste im Fall einer Schleife nicht durchlaufen werden kann, um alle Markierungen zu löschen.
- Die Markierung benötigt zusätzlichen Speicherbedarf.
[Bearbeiten] Vergleich mit Startelement
[Bearbeiten] Ansatz
Der Zeiger auf das nächste Element jedes Listenelements wird mit dem Startelement verglichen. Wenn ein Element auf das Startelement zeigt, hat die Liste eine Schleife.
[Bearbeiten] Probleme
- Das Verfahren funktioniert nur bei Listen, die eine einzige Schleife sind. Listen, die an irgendeiner Position nach dem Startelement eine Schleife haben, werden nicht erkannt.
