Speeding Up The Traveling Salesman Using Dynamic Programming

Vaidehi Joshi
Nov 13, 2017 · 15 min read
Using dynamic programming to speed up the traveling salesman problem!

No Fun Factorials

When we first stumbled upon the traveling salesman problem, we were dealing with a salesman who had a fairly easy task: to visit four cities in some order, as long as he visited each city once and ended up at the same city that he started in.

How a factorial algorithm scales from an input of 4 elements to 5 elements.
O(n!) runtime is unsustainable.

If constant, logarithmic, and linear time are good, and quadratic and exponential time are bad, there is only one thing left to explore: the ugly. Factorial algorithms are exactly that: the ugly.

For an algorithm that runs in factorial, or O(n!) time, any operations that need to run will end up taking n! more time in relation to the data that is being operated upon, or the input data set.

Factorial time is super slow and inefficient as input size grows
Using brute-force takes a top-down approach to solving TSP.

Turning TSP on its head

If we look at our top down methodology from last week, we’ll see that we have enumerated through all of the permutations of paths — that is to say, we have brute-forced our way to determine every single route that our traveling salesman could take.

The brute-force approach to solving TSP.
Rethinking the brute-force approach by identifying the simplest problem, or function call.
Flipping TSP on its head, part 1.

If we are at the simplest possible version of this function call and cannot call anything recursively from within this function, what other function could possibly call this one?

Flipping TSP on its head, part 2.
Flipping TSP on its head, part 3.

Dynamic programming to the salesman’s rescue

Now that we’ve identified our overlapping and recurring subproblems, there’s only one thing left to do: eliminate the repetition, of course!

Flipping TSP on its head, part 4.
Flipping TSP on its head, part 5.
Using dynamic programming makes our 5 city example a little faster.
The Held-Karp algorithm uses dynamic programming to approach TSP.

Resources

The traveling salesman problem has been written about, researched, and taught extensively. As it turns out, there are many different approaches when it comes to attempting to solve it, and the Held-Karp algorithm is just one of them. If you want to dig deeper into this particular topic, here are some good places to start.

  1. Traveling Salesman Problem Dynamic Programming Held-Karp, Tushar Roy
  2. What is an NP-complete in computer science?, StackOverflow
  3. Big O Notation and Complexity, Kestrel Blackmore
  4. A Dynamic Programming Algorithm for TSP, Coursera
  5. Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches, Rajesh Matai, Surya Singh, and Murari Lal Mittal

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

Writing words, writing code. Sometimes doing both at once.

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.