Algorithmes & émergenceOptimisation

Le voyageur de commerce

Visiter chaque ville une seule fois par le plus court trajet devient d'une difficulté folle

Une camionnette à 20 arrêts a plus de tournées possibles que de secondes écoulées depuis la mort des dinosaures. Comment en choisir une ?

Tu vas découvrir

  • Pourquoi les tournées explosent à chaque arrêt
  • Pourquoi l'arrêt le plus proche peut piéger
  • Son lien avec un prix de 1 million de dollars

Pourquoi c'est important

Camionnettes de livraison, usines de puces et labos d'ADN s'y heurtent tous : le meilleur ordre est facile à demander, difficile à trouver.

Environ 4 min7 diapositives interactives · 5 questionsLeçon 509 · Zone 57

Jouer cette leçon

Gratuit dans ton navigateur ou sur iPhone

Plus dans cette zone

  1. 505Théorie de l'informationLa fausse pièceDouze pièces, une fausse, trois pesées et beaucoup d'information
  2. 506Bugs matérielsLa puce qui ne savait pas diviserLe Pentium d'Intel de 1994 ratait certaines divisions et a coûté 475 millions de dollars
  3. 507Apprentissage non superviséTrouver des groupes que personne n'a nommésL'IA peut découvrir des groupes dans des données sans étiquettes
  4. 508Psychologie cognitiveCécité au choixOn défend des choix qu'on n'a jamais faits
  5. 510GéodésieLe point le plus haut n'est pas l'EverestLa Terre est renflée, si bien qu'un volcan en Équateur est le plus éloigné de son centre
  6. 511GéométrieEmpiler des orangesLes épiciers connaissaient depuis des siècles le meilleur empilement ; le prouver a exigé un ordinateur
  7. 512Communautés en ligneComment Wikipédia combat les vandalesTout le monde peut modifier, et les mauvaises modifications disparaissent souvent en quelques secondes
  8. 513Communication anonymeLa route de l'oignonDes couches de relais cachent qui parle à qui