Wie ein Weighted-Random-Walk-Algorithmus funktioniert
Sich vom Zufall leiten zu lassen kann zu überraschenden Ergebnissen führen und auch nützlich sein. Eine Einführung in gewichtet zufällige Spaziergänge.
- Oliver Lau
Stoffhersteller und Hobbybatiker aufgepasst: Hier gibt es Inspiration für neue Designs. Auch Programmierer vernachlässigen wir in diesem Artikel nicht. Wir haben nämlich eine Demoanwendung für sogenannte Weighted Random Walks programmiert, die verblüffende Grafiken aus dem Zufall erzeugt – und wir erklären, wie sie funktioniert. Lässt man die Farblinien kurz auf der weißen Leinwand tänzeln, kommen Stoff-, Tapeten- oder Teppichmuster heraus, laufen sie länger, erinnern die Bilder an Batik oder Rorschach-Tests. Die Anwendung funktioniert in allen aktuellen Browsern. Im GitHub-Repository zu diesem Artikel finden Sie den Code und einen Link zur Live-Demo. Wenn Sie zu keiner der eben genannten Zielgruppen gehören, finden Sie vielleicht Gefallen daran, die damit erzeugten Bilder als Desktophintergründe zu verwenden.
- Random Walks simulieren ökonomische, biologische, physikalische Prozesse und vieles mehr.
- Wir haben sie genutzt, um damit Bilder aus dem Zufall zu erstellen.
- Anhand der dafür programmierten Beispielanwendung erklären wir, wie das funktioniert.
Wankend zum Ziel
Ein Random Walk (Zufallsspaziergang) bezeichnet das mathematische Modell eines Pfades, der aus zufälligen Schritten besteht: Es lässt sich nicht vorhersagen, in welche Richtung der nächste Schritt geht. Deshalb wird ein Random Walk scherzhaft auch als Trunkenbold-Spaziergang (engl. drunkard walk) bezeichnet.
Ein Random Walk muss nicht zwangsläufig eine zweidimensionale Bewegung sein, wie das Wort "Spaziergang" suggeriert. Auch eindimensionale Vorgänge wie das Auf und Ab eines Kryptowährungskurses kann man damit simulieren oder dreidimensionale Bewegungen wie die von Partikeln in einem Gas oder in einer Flüssigkeit (Stichwort: Brownsche Bewegung). Den originalen PageRank-Algorithmus zum Bewerten von Ergebnissen einer Google-Suche könnte man gar als einen multidimensionalen Random Walk bezeichnen: Er simuliert das Verhalten eines "Random Surfers", dem eine Webseite vorgesetzt wird, auf der er blind Links anklickt. Dabei wird ihm irgendwann langweilig und er macht mit einer anderen zufälligen Seite weiter. Die Wahrscheinlichkeit, dass der Surfer auf eine Seite trifft, ist ihr PageRank.
Das war die Leseprobe unseres heise-Plus-Artikels "Wie ein Weighted-Random-Walk-Algorithmus funktioniert". Mit einem heise-Plus-Abo können Sie den ganzen Artikel lesen.
