Travelling Salesmen VS Pigeons (Part 2)
So here we are in the second part of this journey. Let’s see the question that will certainly have made you lose sleep in the last nights.
In case you missed the first part, here it is below!
But how do we solve the problem?
In the first episode, we went to the discovery of graphs, useful structures to represent our dilemma. But now we would like to know how to find a solution.
When faced with such problems, we have 2 possibilities:
- to use a heuristic algorithm
- to use an optimal algorithm
Don’t be intimidated when you read the word algorithm. To simplify, we can say that an algorithm is a finite sequence of steps. For example, the recipe for a cake is an algorithm and you, while doing it, trying to prepare your favourite dessert, are just like a computer running an algorithm.
Sure, computer algorithms tend to be a bit more complicated, but let’s not worry about that for now.
Note (only for the pickiest). We say there would also be a third way, that of approximate algorithms, but now we don’t want to complicate things too much.
We also have enough problems and now it’s better to ask ourselves: how to choose when to use a heuristic algorithm or an optimal one? Mainly based on the time and money we have, as for everything in short, but let’s see a little more in detail these alternatives.
Heuristic algorithms
Suppose we are in the shoes of the Swiss merchant: what would you do? If you don’t feel like thinking, you will probably go to the nearest city. After visiting it and selling your goods, on your map you will mark this city with a beautiful red X (that is, you will not visit it until your next tour). And now? Move the cart to the city closest to where you are. And so on, until you have exhausted all the cities. Simple, isn’t it?
Yes, however, this approach, based on a rule that you have invented (a heuristic, in fact) does not guarantee you at all to make the shortest path. Let’s say that on average, this solution will make you do 25% more than the best solution you can find.
But let’s see a practical example. Suppose we have 5 cities called, very imaginatively, A, B, C, D, E. Not all of these cities are connected directly to each other. For example, we cannot go from A to E.
Regarding the cities that are connected, we can say:
- to go from A to B it takes 50 kilometres
- to go from A to D we take 75 kilometres
- to go from B to C we take 100 kilometres
- to go from B to E it takes 50 kilometres
- to go from C to D it takes 25 kilometres
- to go from C to E it takes 50 kilometres
- to go from D to E we take 75 kilometres
For each of the previous points, we can safely think that even to go from B to A it will take 50 kilometres. Hence, we can represent all this information with an undirected graph. Just like below (although the kilometres are not shown).
As you will notice, the representation we make here has nothing to do with geometry: the distance that separates cities C and D is different from the distance that separates B from C, but we can represent the connection with segments of the same length.
Now suppose you take on the role of the Travelling Salesman and find yourself in city A. What to do? You can choose between:
- go to city B and go 50 kilometres
- go to city D and go 75 kilometres
Applying your heuristics, you’ll go to B. Once you reach it, you can’t go back, so you can choose between going to C or E. In short, you should have understood by now how it works.
In the end, once you return to your city A, you will have covered a total of 250 kilometres. It must be said that for this example it is difficult to find a better solution, so it went well.
But what would you do if instead of 5 cities you had 100, or even 1000? Of course, this approach continues to work and takes you home, but it could make you go a long way in more than you would do with a better (or perhaps optimal) solution.
Optimal algorithms
Do I need to tell you more? It seems obvious to me that an optimal algorithm guarantees you to find the optimal solution! And what does optimal solution mean? Simple, that there are no solutions in which the total path is shorter than the one found. Yes, we can have more optimal solutions, but if we have no further criteria to distinguish them, one is exactly as good as the other.
Now the right question to ask would be: and how do we find the optimal solution? But even here the answer should immediately spring to mind:
WE TRY THEM ALL!
Simple, isn’t it? Well, more or less. Let’s go back to the example with our 5 cities A, B, C, D, E and now suppose that all cities are directly connected to each other (i.e. A is connected with B, C, D, E — B is connected with A, C, D, E — and so on …). Now let’s try to count the solutions.
Starting from A we now have 4 possible choices: B, C, D, E. We choose C (randomly). Now we can choose between B, D, E (3 choices). Let’s take D. Now we have B and E (2 choices). We take B and therefore our last stop will be E.
Our solution will, therefore, be path A, C, D, B, E. But this is only one.
If we now go back and try every possible choice we will see that the number of possible solutions will be:
4 * 3 * 2 * 1 = 24
Not bad! In an hour you can try them all and find the best one! However, 5 cities are not many and in reality, we may have to solve this problem with 1000 cities. This means that all the possible solutions are
999 * 998 * 997 * 996 * … * 3 * 2 * 1
We have a more convenient way to write this number, namely 999! (reads 999 factorial). Here this number is very large and that’s why I don’t feel like writing it here (but you can find it in the notes). For the moment, we can tell you that it has 2565 digits and is a number that far exceeds the number of atoms in the universe.
Yet there are programs that allow us to solve even such big problems. And the beauty is that you don’t need the most powerful computer in the world to do it, often even just your PC is enough.
Of course, these programs are very smart and don’t really have to try all the solutions. Furthermore, in real cases of the Traveling Salesman Problem, it does not often happen that all cities are connected to each other (therefore the possible solutions are a little less). But the previous reasoning should serve to give you an idea of the complexity of the problem.
Ah, but now you ask me what the price is. This is another matter. Here, it depends. Do you have a lot of money? Well, you can purchase a software license that allows you to find optimal solutions for the Traveling Salesman Problem (and for many other problems similar to this). Let’s talk about 4-zero digits. For a year and then expires. Let’s say it’s not really the license of WinRAR, it’s something a little more sophisticated.
What?! Don’t you even have a dime?! Ok, maybe some alternatives may be there. In fact, there is Concorde, a software that allows you to solve this problem and it is also open-source (yes, it means that it is free in practice).
But why isn’t a solution obtained with a heuristic algorithm good? It may actually be fine in some cases, but sometimes this can cost a lot of resources. And if these resources are limited (such as time) or cost a lot (think of the fuel that a truck needs to make 1000 kilometres) then we try to optimize them at best.
For this reason, there is a discipline that deals with studying and solving problems such as that of our travelling salesman. This discipline is Operations Research and you will probably still hear about it if you continue to follow us.
What about the animals?
The problem has always fascinated many scientists, and it has not been long before some biologist also worked to try to get other animals to solve it: someone has therefore spent precious energy (and public money) to make sure that primates, birds and even single-celled organisms proceeded through a series of points.
A particularly original study has tried to understand how an amoeba, devoid of nerve cells and therefore of any reasoning ability, could have solved the problem.
Scientists applied some chemotactic substances in about twenty points of a culture plate, that is, capable of attracting the single-celled organism as a sort of nourishment, to see how the organism would act to incorporate them all. The organism was therefore placed on the culture plate: our friends under the microscope were able to see it cover all the areas where the chemotactic substance was found and instead abandon those where it was not present, thus creating with its body a connection between the various points (as in the images below).
By comparing the arrangement with the best connection pattern between the points, the scientists found a difference of 6% more, among other things probably due to the accommodation of the surface tension.
Taking into account that the heuristic approach described previously allows to obtain results 25% longer than the optimal pattern, this is certainly an impressive result. Not bad for a brainless beast!
Another study focused on perhaps more intelligent animals but certainly not less repellent than amoebas: pigeons.
Scholars have placed some specimens of these cursed birds in a cage connected to a chamber containing 3 food dispensers (in particular, peas).
Released in a corner of the room, the pigeons moved in the room moving from one distributor to another following a pattern based on proximity, or moving from time to time to the nearest distributor. In a second experiment, moreover, the scholars placed the cage in the centre of the room, placing the distributors at equal distances around it so as not to incur bias related to the position of the start. In this second phase it was observed that the birds continued to prefer itineraries based on the distributors closest to each other, but still following patterns marked by the least energy consumption possible, which seems to suggest the presence in them of spatial awareness and a capacity forecasts regarding subsequent trips.
Obviously, all the sessions in which the pigeons did not visit all the distributors or those in which they returned to a previously visited distributor were discarded from the analyzes. Every time any of these situations occurred, the room lights were turned off and the experiment stopped.
Incredibly, the sessions excluded were only 25% of the total.
These results were also strengthened by another study which observed that pigeons if re-exposed to the same scenario, are able to choose even more effective paths compared to the first exposure. In short, they are capable of learning, perhaps better than you are able to do!
Obviously we joke, but we do not want to attract the ire of those who could be our future rulers (Douglas Adams was wrong about mice, he had not considered the supreme intelligence of the pigeons).
Useful Links
Notes
999! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
