![]() | SUMit Roster Software > Nut's Weekly > December 2002 > Travelling Salesman | Nederlands · Search... |
Travelling Salesman |
Monday, 2 December 2002 |
![]() | |
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
NP-complete.
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
|