Schwarmverhalten in der Informatik

Nutzen von Schwarmverhalten in Alogrithmen zur Lösung von Problemen in der Informatik

Traveling Salesman Problem

Der kürzeste Weg

 

Das Traveling Salesman Problem (dt:  Problem des Handlungsreisenden) ist eines der am häufigsten diskutierten Probleme in der theoretischen Informatik. Es handelt sich dabei um folgendes:
Ein Geschäftsmann ist auf Geschäftsreise. Er muss verschiedene Städte in Europa jeweils einmal  besuchen. Es gilt herauszufinden, welches der schnellste Weg ist.
Dies klingt zunächst nicht sehr kompliziert, aber tatsächlich ist dieses Problem extrem schwierig zu lösen, denn die einzige Möglichkeit, die wirklich exakte Lösung zu finden, besteht darin, alle möglichen Wege auszuprobieren und ihre Längen zu vergleichen. Dies würde jedoch unglaublich lange dauern, denn die Menge aller Wege in Abhängigkeit zur Anzahl der zu besuchenden Städte ist:

 

(M = Menge aller Wege; A = Anzahl der zu besuchenden Städte)

Das heißt, dass es bei nur 25 Städten circa:1,5511*10^25 mögliche Wege gibt . Der schnellste Computer der Welt -Cray XT5(1.759.000 GigaFLOPS) - bräuchte somit über acht Millionen Jahre:

Daher ist es nicht sinnvoll, dieses Problem exakt zu lösen. Es ist eine Heuristik notwendig, um dieses Problem mit realistischem Aufwand zu bewältigen. Heuristiken sind Lösungsverfahren, die ein sehr stark angenähertes Ergebnis liefern, mit geringem Aufwand. Der Ameisenalgorithmus ist eine solche Heuristik.

 

 

<<vorherige Seite || nächste Seite>>