Dans l’enquête sur le virus, un groupe de scientifiques doit être capable de comprendre comment arrêter un virus préhistorique de danger. La seule façon dont ils doivent l’empêcher de se propager partout où il est de détruire un par un salles de votre laboratoire les remplissant d’un liquide toxique À la fois pour le virus et les humains. Comment sauvent-ils le monde et survivront-ils?
Cette énigme, apparemment très simple, fait référence à Problème du voyageurun célèbre problème de optimisation Chemins et algorithmes. L’étude de ce type de situations n’est pas seulement utilisée pour stimuler la logique: elle est utile dans des domaines tels que les logistiqueleinformatique et l’organisation de réseaux Et transportoù la planification des chemins efficaces est fondamentale.
Voyons comment le résoudre et quel est le problème du voyageur.
Ce que consiste à l’énigme du virus
Nous sommes dans cette situation: notre équipe de recherche a découvert un virus préhistorique Stocker dans le pergélisol et l’a amené au laboratoire pour l’étudier. Après une longue journée de travail, nous sommes sur le point de fermer tout quand un tremblement de terre soudain Il a sauté le courant, scellant les tailgakes de sécurité, à la fois internes et externes. Dès que nous pouvons le réactiver, l’alarme commence: tout ampoule contenant le virus qu’ils sont itinéraire Et l’agent pathogène s’est propagé dans presque toutes les pièces.
En moins d’une demi-heure, je Les conduits de ventilation s’ouvrirontdiffusant le virus dans le monde. Pour l’éviter, nous devons entrer dans chaque pièce contaminée et Activer l’interrupteur qui commence le protocole de décontamination. Une fois activé, nous avons 10 secondes S’échapper dans la pièce voisine, avant celui dans lequel nous nous retrouvons est rempli d’un liquide toxique pour le virus et pour les humains. Après les inondations, revenir en arrière ne sera plus possible.
Le laboratoire est composé de 16 chambres organisé Fichier de 4tous connectés les uns aux autres par trappe De sécurité. Il y a un solitaire chambre De entrée et l’un des sortiecomme indiqué dans le dessin.
À ce stade, nous prenons nos cahiers, dessinons l’usine de laboratoire et marquons les pièces contaminées. Nous commençons à retracer les itinéraires possibles sur la carte, mais personne ne semble nous emmener à la sortie sans sauter au moins une pièce. Il semble impossible de détruire le virus partout et de pouvoir vous sauver.
Heureusement, dans l’équipe de recherche, il y a aussi une brillante mathématiques qui examine la carte et dit:
Heureusement, le virus n’a pas contaminé la première pièce, sinon nous n’aurions pas d’évasion.
Qu’as-tu compris? Et comment allons-nous sauver le monde?
La solution de l’enquête sur le virus: la première salle n’est pas contaminée
Commençons par le point clé: Comment allons-nous sauver le monde? Notre collègue avait la bonne intuition: nous devons profiter du fait que la première salle ce n’est pas encore contaminé. Cela nous permet de nous déplacer une fois vers l’une des pièces adjacentes et ensuite remonter.
Nous choisissons ensuite d’entrer dans la pièce devant nous, le numéro 2Activez le commutateur E retour immédiatement dans le chambre 1. Maintenant, la salle 2 est détruite et lorsque nous avons ouvert le hayon entre la pièce 2 et 1, le 1 a également contaminé. Alors, écrasons l’interrupteur également dans la salle 1 et déplaçons autour de 5, le seul proche de nous est resté intact.
De là, nous pouvons continuer vers 6 ou 9 ans. Dans les deux cas, plusieurs chemins nous permettent d’atteindre la sortie à travers Toutes les chambres Contaminer, comme, par exemple, ceux que nous voyons dans l’image.
Ainsi, nous parvenons à sauver le monde de ce virus très dangereux et à sortir de sain et de sécurité.
Passer une seule fois pour chaque point: le problème du vendeur des voyageurs
Trouver des stratégies pour passer une seule fois depuis Tous points Sur une carte, ce n’est pas seulement un exercice de logique, il est également très important dans des domaines tels que le logistique, l’informatique et l’organisation du transports en commun. Nous pensons, par exemple, nous devons trouver le meilleur chemin afin qu’un bus Passo dans tous les points nerveux de la ville sans refaire la même route plusieurs fois. Le raisonnement que nous ferons sera très similaire à celui de l’Indovinello! Ce type de problèmes est tous des variantes du « Problème du voyageur», Le plus simple et le plus étudié parmi les problèmes de Planification des chemins et de gestion processus. Le nom vient de la formulation de 1930, dans laquelle il a été demandé:
Compte tenu d’une liste des villes et des distances entre chaque couple de ville, quel est le chemin le plus court possible qui peut parcourir un voyageur pour les visiter une fois exactement et revenir au premier?
Problèmes d’optimisation, même si ils semblent simple Quand tu as Peu de points (ou quelques villes) à partir de laquelle passer, ils deviennent incroyablement complexe à résoudre lorsque le nombre De Les points augmententà tel point que dans les années 1960, un institut de recherche californien a offert des prix en espèces à tous ceux qui ont réussi à résoudre au moins certains cas particuliers.
Ces problèmes sont non seulement plus difficiles à résoudre lorsque nous augmentons le nombre de points, mais ils peuvent même devenir impossible Si nous changeons un peu conditions. Par exemple, si dans notre énigme aussi première pièce avait été contaminénous aurions été s’évanouir. En fait, sur une grille de 4 lignes et 4 colonnes Il n’y a pas de chemin que vous commencez en haut à gauche et que vous vous retrouvez en bas à droite en passant Toutes les chambres une seule fois … Essayez de croire.