- DAA - Discussion
- DAA - Useful Resources
- DAA - Quick Guide
- DAA - Hill Climbing Algorithm
- NP Hard & NP-Complete Classes
- DAA - Cook’s Theorem
- DAA - P and NP Class
- DAA - Vertex Cover
- DAA - Max Cliques
- Deterministic vs. Nondeterministic Computations
- DAA - Sublist Search
- DAA - Fibonacci Search
- DAA - Exponential Search
- DAA - Jump Search
- DAA - Interpolation Search
- DAA - Binary Search
- DAA - Linear Search
- Searching Techniques Introduction
- DAA - Radix Sort
- DAA - Counting Sort
- DAA - Bucket Sort
- DAA - Heap Sort
- DAA - Shell Sort
- DAA - Selection Sort
- DAA - Insertion Sort
- DAA - Bubble Sort
- DAA - Extract Method
- DAA - Heapify Method
- DAA - Insert Method
- DAA - Binary Heap
- Optimal Cost Binary Search Trees
- DAA - Multistage Graph
- DAA - Shortest Paths
- DAA - Spanning Tree
- Travelling Salesperson Approximation Algorithm
- Set Cover Problem
- Vertex Cover Problem
- Approximation Algorithms
- Fisher-Yates Shuffle
- Karger’s Minimum Cut
- Randomized Quick Sort
- Randomized Algorithms
- Travelling Salesman Problem | Dynamic Programming
- Longest Common Subsequence
- DAA - 0-1 Knapsack
- Floyd Warshall Algorithm
- Matrix Chain Multiplication
- DAA - Dynamic Programming
- DAA - Optimal Merge Pattern
- DAA - Job Sequencing with Deadline
- DAA - Fractional Knapsack
- Map Colouring Algorithm
- Dijkstra’s Shortest Path Algorithm
- Kruskal’s Minimal Spanning Tree
- Travelling Salesman Problem
- DAA - Greedy Method
- Towers of Hanoi
- Karatsuba Algorithm
- Strassen’s Matrix Multiplication
- DAA - Binary Search
- DAA - Merge Sort
- DAA - Max-Min Problem
- DAA - Divide & Conquer
- DAA - Space Complexities
- Master’s Theorem
- Time Complexity
- Asymptotic Notations & Apriori Analysis
- DAA - Methodology of Analysis
- DAA - Analysis of Algorithms
- DAA - Introduction
- Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Travelpng Salesman Problem | Dynamic Programming
Travelpng salesperson using greedy approach had been discussed in the same tutorial above. To learn more about it, please
Travelpng salesman problem is the most notorious computational problem. We can use brute-force approach to evaluate every possible tour and select the best one. For n number of vertices in a graph, there are (n−1)! number of possibipties. Thus, maintaining a higher complexity.
However, instead of using brute-force, using the dynamic programming approach will obtain the solution in lesser time, though there is no polynomial time algorithm.
Travelpng Salesman Dynamic Programming Algorithm
Let us consider a graph G = (V,E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-negative.
Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence, this is a partial tour. We certainly need to know j, since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don t repeat any of them. Hence, this is an appropriate sub-problem.
For a subset of cities S $epsilon$ {1,2,3,...,n} that includes 1, and j $epsilon$ S, let C(S, j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j.
When |S|> 1 , we define ?C(S,1)= $propto$ since the path cannot start and end at 1.
Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We should select the next city in such a way that
$$Cleft ( S,j ight ), =, min, Cleft ( S, -, left{j ight},i ight ), +, dleft ( i,j ight ): where: i: epsilon : S: and: i eq j$$
Algorithm: Travepng-Salesman-Problem C ({1}, 1) = 0 for s = 2 to n do for all subsets S є {1, 2, 3, … , n} of size s and containing 1 C (S, 1) = ∞ for all j є S and j ≠ 1 C (S, j) = min {C (S – {j}, i) + d(i, j) for i є S and i ≠ j} Return minj C ({1, 2, 3, …, n}, j) + d(j, i)
Analysis
There are at the most 2n.n sub-problems and each one takes pnear time to solve. Therefore, the total running time is O(2n.n2).
Example
In the following example, we will illustrate the steps to solve the travelpng salesman problem.
From the above graph, the following table is prepared.
1 | 2 | 3 | 4 | |
1 | 0 | 10 | 15 | 20 |
2 | 5 | 0 | 9 | 10 |
3 | 6 | 13 | 0 | 12 |
4 | 8 | 8 | 9 | 0 |
S = $Phi$
$$Costleft ( 2,Phi ,1 ight ), =, dleft ( 2,1 ight ),=,5$$
$$Costleft ( 3,Phi ,1 ight ), =, dleft ( 3,1 ight ), =, 6$$
$$Costleft ( 4,Phi ,1 ight ), =, dleft ( 4,1 ight ), =, 8$$
S = 1
$$Cost(i,s)=minleft{Cosleft ( j,s-(j) ight ), +,dleft [ i,j ight ] ight}$$
$$Cost(2,left{3 ight},1)=d[2,3], +, Costleft ( 3,Phi ,1 ight ), =, 9, +, 6, =, 15$$
$$Cost(2,left{4 ight},1)=d[2,4], +, Costleft ( 4,Phi ,1 ight ), =, 10, +, 8, =, 18$$
$$Cost(3,left{2 ight},1)=d[3,2], +, Costleft ( 2,Phi ,1 ight ), =, 13, +, 5, =, 18$$
$$Cost(3,left{4 ight},1)=d[3,4], +, Costleft ( 4,Phi ,1 ight ), =, 12, +, 8, =, 20$$
$$Cost(4,left{3 ight},1)=d[4,3], +, Costleft ( 3,Phi ,1 ight ), =, 9, +, 6, =, 15$$
$$Cost(4,left{2 ight},1)=d[4,2], +, Costleft ( 2,Phi ,1 ight ), =, 8, +, 5, =, 13$$
S = 2
$$Cost(2,left{3,4 ight},1)=minleft{egin{matrix} dleft [ 2,3 ight ],+ ,Costleft ( 3,left{ 4 ight},1 ight ), =, 9, +, 20, =, 29 \ dleft [ 2,4 ight ],+ ,Costleft ( 4,left{ 3 ight},1 ight ), =, 10, +, 15, =, 25 \ end{matrix} ight., =,25$$
$$Cost(3,left{2,4 ight},1)=minleft{egin{matrix} dleft [ 3,2 ight ],+ ,Costleft ( 2,left{ 4 ight},1 ight ), =, 13, +, 18, =, 31 \ dleft [ 3,4 ight ],+ ,Costleft ( 4,left{ 2 ight},1 ight ), =, 12, +, 13, =, 25 \ end{matrix} ight., =,25$$
$$Cost(4,left{2,3 ight},1)=minleft{egin{matrix} dleft [ 4,2 ight ],+ ,Costleft ( 2,left{ 3 ight},1 ight ), =, 8, +, 15, =, 23 \ dleft [ 4,3 ight ],+ ,Costleft ( 3,left{ 2 ight},1 ight ), =, 9, +, 18, =, 27 \ end{matrix} ight., =,23$$
S = 3
$$Cost(1,left{2,3,4 ight},1)=minleft{egin{matrix} dleft [ 1,2 ight ],+ ,Costleft ( 2,left{ 3,4 ight},1 ight ), =, 10, +, 25, =, 35 \ dleft [ 1,3 ight ],+ ,Costleft ( 3,left{ 2,4 ight},1 ight ), =, 15, +, 25, =, 40 \ dleft [ 1,4 ight ],+ ,Costleft ( 4,left{ 2,3 ight},1 ight ), =, 20, +, 23, =, 43 \ end{matrix} ight., =, 35$$
The minimum cost path is 35.
Start from cost {1, {2, 3, 4}, 1}, we get the minimum value for d [1, 2]. When s = 3, select the path from 1 to 2 (cost is 10) then go backwards. When s = 2, we get the minimum value for d [4, 2]. Select the path from 2 to 4 (cost is 10) then go backwards.
When s = 1, we get the minimum value for d [4, 2] but 2 and 4 is already selected. Therefore, we select d [4, 3] (two possible values are 15 for d [2, 3] and d [4, 3], but our last node of the path is 4). Select path 4 to 3 (cost is 9), then go to s = ϕ step. We get the minimum value for d [3, 1] (cost is 6).
Example
The complete C++ implementation of Travelpng Salesman Problem using Dynamic Programming Approach is given below −
#include<iostream> using namespace std; #define MAX 9999 int n=4; int distan[20][20] = {{0, 22, 26, 30}, {30, 0, 45, 35}, {25, 45, 0, 60}, {30, 35, 40, 0} }; int completed_visit = (1<<n) -1; int DP[32][8]; int TSP(int mark, int position){ if(mark==completed_visit) { return distan[position][0]; } if(DP[mark][position]!=-1) { return DP[mark][position]; } int answer = MAX; for(int city=0; city<n; city++) { if((mark&(1<<city))==0) { int newAnswer = distan[position][city] + TSP( mark|(1<<city),city); answer = min(answer, newAnswer); } } return DP[mark][position] = answer; } int main(){ for(int i=0; i<(1<<n); i++) { for(int j=0; j<n; j++) { DP[i][j] = -1; } } cout << "Minimum Distance Travelled -> " << TSP(1,0); return 0; }
Output
Minimum Distance Travelled -> 122Advertisements