Graphen und NetzwerkeAnts

Das Problem des Handlungsreisenden ist NP-hard, was bedeutet, dass es sehr schwer von Computern zu lösen ist (zumindest für eine große Anzahl von Städten).

Die Entwicklung eines schnellen und genauen Algorithmus hätte schwerwiegende Auswirkungen auf den Bereich der Informatik: es würde bedeuten, dass es schnelle Algorithmen für alle NP-hard-Probleme gibt. Es würde auch den größten Teil der Sicherheitsmaßnahmen im Internet aushebeln, die sich darauf verlassen, dass bestimmte Probleme sehr schwer für Computer zu lösen sind.

Einen schnellen Algorithmus zu finden, um das Problem des Handlungsreisenden zu lösen, würde auch eines der berühmtesten offenen Probleme in Mathematik und Informatik lösen, das P versus NP Problem. Es ist eines der sieben Millenniumprobleme, die jeweils mit einem Preis von $1 Mio. dotiert sind.