Jeder kennt sicher das kleine Gedankenbeispiel: jemand, eine einfache Person wie Du und ich, schreibt einen Brief und schickt diesen an alle Freunde und Bekannte mit der Bitte es ihm gleich zu tun. Diese schicken den Brief ebenfalls weiter und die Freunde der Freunde schicken den Brief ebenfalls weiter. Dann dauert es nur ca. 5-6 Abschnitte, bis der Brief den U.S. Präsidenten erreichen könnte.
Hinter diesem Phänomen liegt das so genannte “small-world-paradigm” (Kleine-Welt-Paradigma). Dieses Paradigma sagt aus, dass jeder auf der Welt über einen besonders kurzen Abschnitt von Bekanntschaften zu jedem anderen Menschen verbunden ist.
Im Eureka!-Artikel ‘Six Degrees of Kevin Bacon’ game provides clue to efficiency of complex networks auf http://esciencenews.com/ wird erklärt, wie dieses Phänomen mit der Effizienz von komplexen Netzen zusammenhängt.
Kürzeste Wege mit Dijkstra
Jeder der sich mit Informatik auskennt, hat schon einmal vom Kürzeste-Wege-Algorithmus Dijkstra gehört, benannt nach seinem niederländischen Erfinder Edsger W. Dijkstra. Der Algorithmus berechnet in einem Graphen (auch Netzwerk genannt, in der Informatik bestehend aus Knoten und den Verbindungen zwischen ihnen, genannt Kanten) den kürzesten Weg von einem Punkt A nach einem Punkt B.
Wie in dem Bild vom Eureka!-Artikel zu sehen, kann es nicht nur einen Weg von A nach B geben. Nun gibt es eine Erweiterung des Dijkstra-Algorithmus, die mit geometrischen Informationen arbeitet, um schneller ans Ziel zu kommen. In dem zugrunde liegenden Artikel ist die Problemstellung in komplexen Netzen (z. Bsp. Peer-to-Peer-Netze), dass eine Information zu einem bestimmten Empfänger muss. Stell dir also vor, dass Du einen Brief an den U.S.-Präsidenten schreibst und dieser soll so schnell wie möglich ankommen. Nun gibst Du den Brief einem Freund, von dem Du weißt, dass er Beziehungen in die USA hat mit der Information, ihn an jeden Freund weiter zu reichen, der Beziehungen zu Washingtion, zum Weißen Haus bzw. zum U.S.-Präsidenten hat. Unter dieser Prämisse wird der Brief nun weiter gereicht und landet nach der Theorie in nur ca. 5-6 Abschnitten beim Präsidenten.
Diese Vorgehensweise unterscheidet sich insofern vom Dijkstra-Algorithmus, da Dijkstra sich eher wellenartig (in konzentrischen Kreisen), wie wenn man einen Stein ins Wasser wirft, in alle Richtungen ausbreitet, bis er den Zielpunkt erreicht hat. In unserem Beispiel würde das bedeuten, dass alle Freunde (nicht nur einer) in meinem Umfeld einen Brief bekommen, diesen kopieren und an all ihre Freunde weiterreichen würden. Das würde einen enormen Aufwand bedeuten. Stellt man sich das nun bei komplexen Netzen vor wie sie im Internet zugrunde liegen, könnte das schnell zu Überlastung führen. Die Information soll so schnell wie möglich ans Ziel. Hier greift der A*-Algorithmus (A-Stern) ein.
Der A*-Algorithmus
Der A*-Algorithmus arbeitet im Prinzip wie der Dijkstra-Algorithmus, nur mit dem Unterschied, dass er sich einer wesentlichen und zielführenden Information bedient. Dieses bedeutet zwar auch mehr Speicherverbrauch für die Bereitstellung der Daten und der Algorithmus weist eine teilweise erhöhte Komplexität auf, jedoch hat sich in der Praxis gezeigt, dass er durch das zielgerichtet Vorgehen schneller ans Ziel kommt und damit effizienter arbeitet.
Der A*-Algorithmus bedient sich geometrischer Informationen. Um genau zu sein Abstandsinformationen zwischen Start- und Zielpunkt. Das kann in Form geomtrischer Koordinaten wie Längen- und Breitengrad sein, jedoch auch in jeder anderen mathematisch vergleichbaren Form (Kennzahlen wie unsere Postleitzahl oder ähnliches).
Wo der Dijkstra-Algorithmus sich wellenartig ausbreitet, bildet der A*-Algorithmus eine art Ellipse Richtung Ziel aus. Es wird nicht jeder mögliche Weg gegangen, sondern es wird zur Berechnung des möglichen kürzesten Abstands die geometrische Information herangezogen (bspw. Abstand beider geomtrischer Koordinaten muss klein sein, dann ist auch die Luftlinie besonders klein). Damit nimmt der Algorithmus als nächsten Punkt auf dem Weg von A nach B immer den, welcher ihn den geometrischen Daten nach immer näher an B bringt und somit breitet er sich kaum in die Richtung aus, die ihn von B weg führt (beim Dijkstra wäre das hingegen die genannte konzentrische Ausbreitung in alle Richtungen).
Genau diese Idee wird auch in dem Eureka!-Artikel erläutert, um auf kürzestem Wege von A nach B zu gelangen. Der A-Stern- bzw Dijkstra-Algorithmus findet bereits großen Einsatz. Ersterer wird zum Beispiel in Spielen (wie Civilization oder Age Of Empires) benutzt, um eine Person (auf kürzestem Weg) von A nach B zu schicken (Go-To-Funktion). Letzterer wird eher in Navigationsgeräten benutzt, um uns im Auto die schnellstmögliche Route von A nach B zu berechnen (natürlich unter Berücksichtigung von etlichen Daten wie Höchstgeschwindigkeit, Ausbaustufe der Straße, Stau, Baustellen, usw.).
Diese Algorithmen haben also einen sehr praktischen Nutzen und Einsatz, nicht nur am bzw. mit dem Rechner, sondern auch im täglichen Leben. Auch wir benutzen indirekt (und weniger genau) einen A-Stern-Algorithmus, wenn wir von einem Punkt zum anderen gehen. In der Stadt überlegen wir oft unbewusst und in nur wenigen Sekunden welcher Weg nun der kürzere ist und gehen dann den für uns subjektiv kürzeren. Unser Eindruck täuscht uns zwar manchmal, da wir einen Weg mit vielen verschiedenen Eindrücken (bspw. in der Innenstadt mit Geschäften) als kürzer empfinden, als einen eher langweiligen/eintönigen geraden Weg ohne vermehrte Eindrücke.
Verwandte Beiträge:
0 Responses to “Was der A-Stern-Algorithmus mit komplexen sozialen Netzen gemeinsam hat”