Travelling Salesman | Dynamic Programming | Part 18

Hello guys, welcome back to “code with asharam”. I am really sorry for not writing any tutorial for last 3 days. Actually, I took part in a hackathon and was pretty busy. Though I didn’t win it, yet I learned a lot from it. I made an android music player which shows you live lyrics. If you like, you can check out my app at Lyricsify. So, yeah!, hackathon is over and I am back to competitive programming again. This is 18th part of my dynamic programming tutorials. If at any moment if it feels like that things are going over your head, then, take a break and read all the last tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment. I will answer your query as soon as possible. So, in this tutorial, I am going to discuss a really famous problem – Travelling Salesman. This problem is really interesting as it has been bothering computer scientists for a long time. This problem falls under category of NP-Hard problems. NP-Hard problems are the ones which don’t have any known polynomial time algorithms. I will discuss only brute force and dynamic programming solution in this tutorial. So, without any further delay, Let’s take a dive into deep oceans of dynamic programming.

Travelling Salesman

You are given with n cities and distance between each pair pair of cities. The task is to find the shortest possible route that visits every city exactly once and returns to the starting point. Note that distance from city i to j can be different from distance from city j to city i.

Give it a try on your own before moving forward

Brute force solution

It is quite simple. Suppose the source city is 1. Then, we can move to one of (n-1) cities. After that, we can move to one of (n-2) cities and so on. If you observe carefully, then, you will see that We will have total of (n-1)! different ways possible. Finding minimum route among these (n-1)! path requires O((n-1)!) which is a lot worse than O(2n). You might appreciate the fact that n! > 2n for all n>4. As you can see we need to improve upon this method a lot. So, that’s where dynamic programming comes into picture.

Dynamic Programming Solution

As I always tells you that our way of solving problems using dynamic programming is a universal constant. We will play our game of guessing what is happening, what can or what cannot happen if we know something. So, let’s take city 1 as the source city for ease of understanding. Now, let’s note down few observations which we can make by just looking at the problem:

  1. Since we have to return back to city 1, we can do so by any vertex i. If dist(i, j) denotes distance from city i to j and cost(haveVisited, i) denotes the minimum path length to travel from source to i such that all other cities are visited exactly once. Also, haveVisited stores all the visited vertices. Using all the assertions, we can design an algorithm as follows:
    requiredAnswer = min( cost(haveVisited, i) + dist(i, 1) ) i <> 1 and i <= n
    
  2. As you can see we have designed a basic outline of our algorithm. But we have to find cost() to calculate final answer. You can see that we can reach i from any city j provided that we do not visit city i before visiting city j. In the language of algorithms, this assertion can be written as:
    cost(haveVisited, i) = cost(haveVisited-{i}, j) i, j <> 1 and i, j <= n
    

We have designed our algorithm but we are still left with problems of overlapping subproblems and base cases. Clearly, if haveVisited is empty, then, we have only 2 cities, i.e., 1 and i. Hence, in that case cost(haveVisited, i) = dist(1, i). Now, let's see how many distinct subproblems can we have for a given starting problem.

**cost() function deals with 2 parameters, i.e., i , haveVisited
**i  can take n-1 different values.
**Also, haveVisited can have atmost n-1 different elements and for
  each element we have 2 choices - either include or exclude.
  Hence, there can be 2n-1 different values for haveVisited.
**Clearly, number of subproblems will be n*2n-1.

Hence, we have to use a n X 2n-1 sized subarray. Also, for each subproblem we have to iterate over j which can have n-2 distinct values. Hence, time complexity of this algorithm for travelling salesman will be O(n2*2n) and space complexity will be O(n*2n-1). Though, time complexity is a lot better than the brute force solution, this is an inefficient algorithm. There are some approximation algorithms which I will discuss in future posts.
So, that's it guys for today. I hope you would have found this tutorial insightful. If you like reading my tutorials, then, please follow my blog and share it with your friends. Meanwhile, don't forget to solve ALTARAY.
You can subscribe to my YouTube channel for video tutorials on dynamic programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: