Speeding Up the TSP by using an opposite approach?

I began my google search with the simple “traveling salesman problem”, and after reading a few articles, I found this one to be rather interesting.

In this article, the author Joshi describes solving the TSP by using the top-down approach. This is the same approach we used in class, using the largest parts of the graph to find a solution.

Then, the author mentions trying the same problem, but instead with a bottom-up approach. Joshi calls this the “bottom-up dynamic programming approach”, which begins with the smallest possible subproblems and their solutions, then progresses upward to solve the more complicated subproblem. In the end, the bottom-up approach brought Joshi to an answer sooner than the top-down method.


Leave a Reply