Friday, March 21st, 2008
There are n! paths in a graph of size n. I can find the optimal TSP solution in O(n^2 2^n) time. Therefore, it is possible to do better than examine every path to find a TSP solution.http://www.algorithmist.com/index.php/Traveling_Salesperson_Problem