In the virus investigation, a group of scientists must be able to understand how stop a hazard prehistoric virus. The only way they have to prevent it from spreading wherever it is to destroy one by one all rooms of your laboratory filling them with a toxic liquid Both for the virus and humans. How will they save the world and survive?
This riddle, apparently very simple, refers to problem of the travelera famous problem of optimization paths and algorithms. Studying this type of situations is not only used to stimulate logic: it is useful in areas such as the logisticstheinformatics and the organization of networks And transportwhere planning efficient paths is fundamental.
Let’s see how to solve it and what is the problem of the traveler.
What the riddle of the virus consists
We are in this situation: our research team has discovered a prehistoric virus Store in the Permafrost and brought him to the laboratory to study it. After a long day of work, we are about to close everything when a sudden earthquake He sautéed the current, sealing the security tailgakes, both internal and external. As soon as we can reactivate it, the alarm starts: all vial containing the virus they are route And the pathogen has spread in almost all rooms.
In less than half an hour, i ventilation ducts will openspreading the virus in the world. To avoid it, we must enter each contaminated room and Activate the switch which starts the protocol of decontamination. Once activated, we have 10 seconds To escape in the next room, before the one in which we find ourselves is filled with a toxic liquid for the virus and for humans. After flooding, going back will no longer be possible.
The laboratory consists of 16 rooms arranged File from 4all connected to each other by hatches Of safety. There is a lonely room Of entrance and one of exitas shown in the drawing.
At this point, we take our notebooks, draw the laboratory plant and mark the contaminated rooms. We begin to trace possible routes on the map, but nobody seems to take us to the exit without jumping at least one room. It seems impossible to destroy the virus everywhere and be able to save yourself.
Fortunately, in the research team there is also a brilliant mathematics that looks at the map and says:
Luckily the virus did not contaminate the first room, otherwise we would have no escape.
What did you understand? And how will we save the world?
The solution of the virus survey: the first room is not contaminated
Let’s start from the key point: How will we save the world? Our colleague had the right intuition: we must take advantage of the fact that the first room it is not yet contaminated. This allows us to move once towards one of the adjacent rooms and then go back.
We then choose to enter the room in front of us, the number 2activate the switch e return immediately in the room 1. Now room 2 is destroyed, and when we opened the tailgate between room 2 and 1, the 1 has also contaminated. So, let’s crush the switch also in room 1 and move around 5, the only one close to us remained intact.
From there, we can continue around 6 or 9. In both cases there are several paths that allow us to reach the exit through All rooms contaminate, such as, for example, those we see in the image.
Thus we manage to save the world from this very dangerous virus and to get out of healthy and safe.
Pass only once for each point: the problem of the traveler salesman
Find strategies for pass only once from All points On a map it is not just an exercise of logic, it is also very important in areas such as the logistics, computer science and the organization of the public transport. We think, for example, we have to find the best path so that a bus Passo in all the nerve points of the city without redoing the same road several times. The reasoning we will do will be very similar to that of the IndoVinello! This type of problems are all variants of the “problem of the traveler”, The simplest and most studied among the problems of Path planning and of management processes. The name comes from the 1930 formulation, in which it was asked:
Given a list of cities and the distances between each city couple, what is the shortest possible path that can travel a traveler to visit them all exactly once and return to the starting one?
Optimization problems, however much they seem simple When you have Few points (or a few cities) from which to pass, they become incredibly complex to be resolved when the number Of points increasesso much so that in the 1960s a Californian research institute offered cash prizes to anyone who managed to solve at least some particular cases.
These problems are not only more difficult to solve when we increase the number of points, but they can even become impossible If we change some conditions. For example, if in our riddle also the first room had been contaminatedwe would have been passed off. In fact, on a 4 -lines and 4 columns grid There is no path that you start at the top left and end up on the bottom right passing through All rooms only once … Try to believe.
