Traveling Salesman
Trouvez la boucle la plus courte qui visite chaque ville une fois · le classique problème du voyageur de commerce
À propos du Voyageur de commerce
Le Voyageur de commerce est un petit puzzle d'optimisation d'itinéraire basé sur l'un des problèmes les plus célèbres de l'informatique · le Problème du Voyageur de Commerce (PVC). Quelques villes sont dispersées sur une carte, et vous commencez chez vous. Votre tâche est de planifier un circuit qui visite chaque ville exactement une fois et revient chez vous, en utilisant la distance totale la plus courte possible. Touchez les villes dans l'ordre où vous les parcourriez et l'itinéraire se dessine; le compteur de distance en direct vous indique la longueur de votre boucle.
Pourquoi cela entraîne votre cerveau. Trouver le circuit le plus court est un pur raisonnement spatial et une planification · vous devez comparer des ordres entiers les uns aux autres, remarquer quand un itinéraire se croise et gaspille de la distance, et rechercher l'arrangement imbattable. Il n'y a pas de formule à appliquer; vous raisonnez directement sur la géométrie, ce qui est exactement le type de pensée d'optimisation que le PVC a rendu célèbre.
Atteignez l'optimum pour gagner. Chaque carte est résolue exactement en coulisses, donc une manche ne compte comme une victoire que lorsque votre boucle correspond au véritable itinéraire le plus court · les circuits de longueur égale comptent tous. Si vous faites plus long, le jeu révèle l'itinéraire optimal par-dessus le vôtre afin que vous puissiez voir le croisement que vous auriez dû démêler.
La carte s'agrandit à mesure que vous progressez. Les premières manches sont de quatre ou cinq villes · assez courtes pour être évaluées à l'œil. Tous les quelques niveaux, la carte gagne une ville supplémentaire, et chaque arrêt supplémentaire multiplie le nombre d'itinéraires possibles, il devient donc plus difficile de repérer la boucle la plus courte à mesure que votre série s'allonge.
Fait partie de la famille de jeux d'entraînement cérébral PlayMemorize. Fonctionne entièrement dans votre navigateur, fonctionne hors ligne en tant qu'application web progressive.
FAQ
-
Comment jouer au Voyageur de commerce?
Vous commencez au marqueur de départ. Touchez les autres villes une par une dans l'ordre où vous les visiteriez · l'itinéraire se dessine au fur et à mesure et le compteur de distance se met à jour. Une fois que toutes les villes sont sur l'itinéraire, appuyez sur Vérifier. Si votre boucle correspond à l'itinéraire le plus court possible, vous gagnez la manche. -
Qu'est-ce que le Problème du Voyageur de Commerce?
C'est un problème d'optimisation classique: étant donné un ensemble de villes, trouver l'itinéraire le plus court possible qui visite chacune d'elles exactement une fois et revient au point de départ. Il est notoirement difficile car le nombre d'itinéraires possibles explose à mesure que vous ajoutez des villes · ce jeu vous permet de résoudre de petites instances à la main. -
Comment le jeu sait-il que l'itinéraire est optimal?
Chaque carte est suffisamment petite pour que le jeu calcule le circuit le plus court exact en vérifiant chaque ordre possible. Votre boucle gagne lorsque sa longueur correspond à cet optimum. Si deux itinéraires différents sont à égalité pour le plus court, l'un ou l'autre compte comme une victoire. -
Que se passe-t-il si mon itinéraire n'est pas le plus court?
La manche compte comme une défaite et le jeu dessine le véritable itinéraire optimal par-dessus le vôtre afin que vous puissiez comparer. Cherchez les endroits où votre boucle se croise · un non-croisement raccourcit presque toujours le circuit. Utilisez Annuler pour retirer la dernière ville ou Effacer pour recommencer l'itinéraire. -
Est-ce que ça devient plus difficile au fur et à mesure?
Oui. Chaque manche réussie augmente votre niveau, et tous les quelques niveaux, la carte gagne une ville supplémentaire. Étant donné que chaque arrêt supplémentaire augmente fortement le nombre d'itinéraires possibles, la boucle la plus courte devient de plus en plus difficile à repérer à mesure que votre série s'allonge. -
Fonctionne-t-il hors ligne?
Oui. PlayMemorize est une application web progressive. Installez-la une fois et le Voyageur de commerce fonctionne n'importe où sans connexion internet.