Randomisierte Traversierung
Um in einem Graphen von einem gegebenen Startknoten einen weiteren Zielknoten zu finden, werden unterschiedliche Suchstrategien angewendet. Die randomisierte Traversierung ist eine davon. Es können verschiedene Algorithmen genutzt werden, um eine möglichst effiziente Suche durchzuführen. Bei den meisten Suchstrategien wird der Graph beginnend ab dem Startknoten durchlaufen. Im schlechtesten Fall muss hier der komplette Graph durchlaufen werden.
Bei großen Graphen kann es sehr ineffizient sein, für eine Suche jedes Mal den kompletten Graphen zu durchlaufen. Hier helfen randomisierte Traversierungen. Der Graph wird nicht nach einem bestimmten Schema durchlaufen, sondern der nächste Knoten wird randomisiert ausgewählt. Dadurch kann so eine Suche wesentlich schneller ein Ergebnis finden, allerdings nicht immer das beste.
Ein Beispiel für eine randomisierte Traversierung in einem Graphen ist die Suche nach einem "Independent Set". Ein sogenanntes Independent Set ist ein Teilgraph, der unabhängig vom Rest des Graphen ist, es somit also keine Verbindung zu weiteren Knoten im Graphen gibt. Der Algorithmus wählt hier randomisiert anhand einer Wahrscheinlichkeit Knoten aus und sortiert diese in die Menge der unabhängigen Knoten. Im Anschluss werden alle Knoten entfernt, die noch Verbindungen zu weiteren Knoten im Graphen besitzen. Übrig bleiben genau die unabhängigen Knoten, die zu Anfang gesucht wurden.
Quellen:
- Edlich, Friedland, Hampe, Brauer: "NoSQL – Einstieg in die Welt der nichtrelationalen Web2.0- Anwendungen", Hanser-Verlag, 2010, ISBN 978-3-446-42355-8
- Prof. Dr. Peter Sanders, Dipl.-Inform. Johannes Singler: "Berechnung kürzester Wege", http://algo2.iti.kit.edu/singler/algorithmus-der-woche/Kuerzeste%20Wege.pdf, Stand Mai 2011
- Prof. Dr. Bernhard Schiefer: "Algorithmische Graphentheorie", http://www.informatik.fh-kl.de/~schiefer/lectures/download/GT_7.pdf, Stand Mai 2011
- Thomas Hofmeister: "Randomisierte Algorithmen", http://www14.informatik.tu-muenchen.de/lehre/2006WS/ra/Hofmeister.pdf, 2006, Stand Mai 2011
- Alexander Esser: "Der Dijkstra-Algorithmus zur Berechnung kürzester Wege in Graphen",1. Auflage, GRIN Verlag, 2009, ISBN 978-3-640-39550-7
Weiterführende Literatur:
- Prof. Dr. rer. nat. Peter Tittman: "Graphentheorie", Fachbuchverlag Leipzig im Carl Hanser Verlag, 2003, ISBN 3-446-22343-6
- Prof. Dr. Volker Turas: "Algorithmische Graphentheorie", 3. Auflage, Oldenburg Wissenschaftsverlag, 2009, ISBN 978-3-486-59057-9
- Bucher Gruppe: "Graphentheorie: Wege, Pfade, Zyklen und Kreise in Graphen, Durchlaufbarkeit Von Graphen, Vier-Farben-Satz, Zusammenhang Von Graphen", General Books LLC, 2010, ISBN 978-1-159-11215-8
- Steffi Meier: "Graphentheoretische Modelle zur Optimierung und Simulation", 1. Auflage, GRIN Verlag, 2006, ISBN 978-3-640-32530-6
Kategorie: Neue DB-Entwicklungen,NoSQL, Graphen-DB, R, T