Alter Code: Ameisen lösen Problem des Handlungsreisenden (TSP)

…puh, nochmal alter Code. Das bekannte Traveling Salesman Problem (TSP) gehört zu der Komplexitätsklasse NP, da die Laufzeit auf einem klassischen Computer mit Anzahl der Wegpunkte exponentiel ansteigt. Eigentlich theoretisch nur lösbar in polynomialzeit von  einem Quantencomputer. Allerdings gibt es interessante Ansätze die auf klassischen Computern zu lösen, wenn man keine optimale Lösung braucht, sondern auch eine suboptimale Lösung taugt.

Ein Ansatz kommt aus der Biologie und zwar im speziellen von den Ameisen. Man hat festgestellt, dass Ameisen mit der Zeit einen kürzesten Weg zwischen ihrem Bau und einer Futterstelle finden. Wie machen sie das? Sie versprühen eine Duftmarke am Boden und je stärker diese ist, desto mehr Ameisen benutzen diesen Weg. Klar ist, dass auf einem kurzen Weg auch mehr Duftstoff ausgebracht werden kann, da ihn mehr Ameisen pro Zeit verwenden.

Dafür hab ich einen Simulator geschrieben, der dieses Phänomen verdeutlichen soll.

Link:
https://github.com/sky4walk/AntTSP

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

Verbinde mit %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.