Jozef Kratica
Slobodan Radojeviæ
This paper describes one improvement to "nearest neighbor" method for solving "traveling salesman" problem. This improvement finds sub optimal solutions (heuristic), so as original method.
The only algorithms that are known are of exponential execution time, because "traveling salesman" problem is NP complete ([4]). These algorithms are correct theoretically, and they easily find solution for small number of graph nodes (N<20), but for large number of nodes (N>20) execution time is enormously large.
Therefore, this paper describes improvement of "nearest neighbor" method, which gives suboptimal solutions (heuristic), but has O(n2) execution time.
AMS Subject Classifications:
90C27 Combinatorial programming
90C35 Network programming
90-08 Computational methods (optimization)
Back to Jozef's Papers Home Page | Back to Jozef's Home Page | Full paper - PDF (62 KB)