Problème du voyageur de commerce
Plus de soixante millions de milliards. Chaque ville ajoutée multiplie le nombre de tournées possibles, au lieu de simplement l'augmenter. Un ordinateur qui en testerait un million par seconde y passerait près de deux mille ans.
Plus de soixante millions de milliards. Chaque ville ajoutée multiplie le nombre de tournées possibles, au lieu de simplement l'augmenter. Un ordinateur qui en testerait un million par seconde y passerait près de deux mille ans.
On se contente d'une tournée presque parfaite, trouvée par des heuristiques. La plus simple file toujours vers la ville la plus proche pas encore visitée ; sur des villes placées au hasard, elle donne un trajet environ 25 % plus long que le meilleur. Les méthodes modernes descendent à 2 ou 3 % de l'optimum, même avec des millions de points.
Parce que la question « existe-t-il une tournée plus courte que tant de kilomètres ? » est NP-complète. Un algorithme exact et rapide pour elle en donnerait un pour tout problème de la classe NP, et trancherait la question P = NP, l'un des sept problèmes du millénaire mis à prix par l'institut Clay.