SUMit Roster Software > Nut's Weekly > December 2002 > Travelling Salesman  Nederlands · Search... 
Travelling Salesman 
Monday, 2 December 2002  October 2002 November 2002 Bounce Spin View Change January 2003 February 2003  
There is no perfect solution for the problem of the travelling salesman (TSP).
What is the shortest route


The problem of the travelling salesman is
NPcomplete.
There is one known algorithm that finds the optimal solution: using brute force to scan all possibilities. For larger problems this is undoable, as the number of possibilities grows exponentially. Yet you see a Java applet above that finds an excellent solution extremely quickly, even along hundreds or even a thousand points. How is this possible? The applet above does not always show the optimal solution, but it does find a solution that is at least excellent. It scores sometimes 10 out of 10, mostly 9.9!The underlying advanced algorithm is quite complex. It has taken me several sessions with the frog to invent it. The algorithm requires quite a few calculations, but still finds an excellent solution quickly, one with low or even minimal costs. Applications
