The travelling salesman problem (TSP) asks the following question: If you have a list of cities and you absolutely have to visit every city on the list exactly once, what is the shortest possible route you can take? It’s a classical problem on combinatorial optimization and is widely studied in theoretical computer science (where, given a length L, the task is to decide whether the graph has any tour shorter than L). The TSP has many applications in planning, manufacture of microchips, astronomy and even in DNA sequencing (where cities are DNA fragments).
Simon and I have read about this problem in a Dutch children’s book (Telduivel) where it was stated that if a salesperson has to visit 25 cities and thus there are 25! possible routes to take, no modern computer can handle calculating the shortest one. Simon decided to check what the maximum number of characters was for a long in Java, and it turned out to be 19 (while 25! equals to 15.511.210.043.330.985.984.000.000 and exceeds that maximum). In his TSP example, Daniel Shiffman uses only 10 cities and 10! equals to merely 3.628.800, so that worked out fine.
Wikipedia says that even though the problem is computationally difficult, a large number of algorithms are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.
In the first two videos he starts and explains the project, in the later videos he applies additional algorithms to enhance accuracy.
Lexicographic Order Algorithm, one algorithm to iterate over all the permutations of an array:
In the following video, Simon explains what crossover is and how he plans to implement it within the Genetic Algorithm file in order to get even more exact results. (He later got stuck when introducing crossover into his Processing code).