Graphes et réseauxSalesman

Jusqu'ici, nous avons ignoré le fait que certaines villes pourraient être plus éloignées que d'autres. Cependant, dans la vie réelle, il s'agit d'une considération très importante: nous ne voulons pas simplement trouver un chemin mais nous voulons aussi trouver le chemin le plus court. Ce problème s'appelle le voyageur itinérant. Ce problème doit être résolu non seulement dans les domaines du transport et de la logistique, mais également lors du positionnement des transistors sur des puces, afin de rendre les ordinateurs plus rapides, ou lors de l'analyse de la structure de DNA.

Une méthode simple serait d'essayer tous les chemins possibles, en trouvant la longueur de chacun, puis en choisissant le plus court. Cependant, nous venons de montrer que, même avec seulement ${tsn2} villes, il existe ${tsn2}! = ${factorial(tsn2)} chemins possibles. Une fois que vous avez des centaines ou des milliers de sommets, il est impossible d'essayer tous les chemins possibles, même avec des ordinateurs puissants.