Travelling Salesman Problem

Travelling Salesman Problem

CODING BLOCKS

Geeks for Geeks

Using Branch and Bound

visualgo-tsp 

Implementation 01:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include<bits/stdc++.h> using namespace std; int dp[1<<20][20]; int n = 4; int dist[10][10] = { {0,20,42,25}, {20,0,30,34}, {42,30,0,10}, {25,34,10,0} }; void takeInput() { cin >> n; // number of village. // now we input Cost Matrix. for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> dist[i][j]; } } } int VISITED_ALL = (1 << n) - 1; // mask = friends I already visited // At = last visited friend int tsp(int mask, int pos) { if(mask == VISITED_ALL) return dist[pos][0]; if(dp[mask][pos] != -1) return dp[mask][pos]; // Now from current node, we will try to go to every other node and take the min ans int ans = INT_MAX; for(int city = 0; city < n; city++){ if( (mask & (1 << city ) ) == 0){ int newAns = dist[pos][city] + tsp(mask | (1 << city), city); ans = min(ans, newAns); } } return dp[mask][pos] = ans; } int main() { //freopen("in.txt", "r", stdin); memset(dp, -1, sizeof(dp)); /// takeInput(); cout << "Total minimum Distance---> "<<tsp(1,0); return 0; }

Implementation 02:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include<bits/stdc++.h> using namespace std; int n; int dist[10][10]; int graph[20][20]; void takeInput() { cin >> n; // number of village. // now we input Cost Matrix. for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> graph[i][j]; } } } int tsp(int s) { vector<int>vertex; for(int i = 0; i < n; i++){ if(i != s) vertex.push_back(i); } int min_path = INT_MAX; do{ int current_pathweight = 0; int k = s; for(int i = 0; i < vertex.size(); i++){ current_pathweight += graph[k][vertex[i]]; k = vertex[i]; } current_pathweight += graph[k][s]; min_path = min(min_path, current_pathweight); }while(next_permutation(vertex.begin(), vertex.end())); return min_path; } int main() { takeInput(); int s = 0; cout << tsp(s)<<endl; return 0; }

Share: