Graphes et réseauxAnts

Le problème du voyageur de commerce est NP-hard, ce qui signifie qu’il est très difficile d’être résolu par un ordinateur (du moins pour un grand nombre de villes).

Trouver un algorithme rapide et exact aurait de sérieuses implications dans le domaine de l'informatique: cela signifierait qu'il existe des algorithmes rapides pour tous les problèmes difficiles. Cela rendrait également la majeure partie de la sécurité Internet inutile, ce qui repose sur le fait que certains problèmes sont jugés très difficiles pour les ordinateurs.

Trouver un algorithme rapide pour résoudre le problème du voyageur voyageur résoudrait également l'un des problèmes les plus connus en mathématiques et en informatique, le problème P vs NP. Il s’agit de l’un des sept prix du millénaire, chacun comportant un prix d’un million de dollars.