Travelling Salesman Problem (TSP) is a classic algorithmic problem in the field of computer science, where a set of cities and distance between every pair of cities are given and it is required to find the shortest possible route that visits every city exactly once and returns to the starting point.
In terms of optimal solution, greedy algorithms are used for solving TSPs, but it becomes more complex and takes exponential time when numbers of vertices (i.e. cities) are very large.
Being an algorithm analyst what do you think, "If TSP problem is solved by using dynamic programming approach, will it provide feasible solution better than greedy approach?
Answers
Answer:-
Both time and space complexity should be considered when comparing greedy and dynamic programming techniques to solve TSP. While time for dynamic programming is O(n2*2n). For greedy algorithm it is O(n!). The time complexity in dynamic programming is less than greedy algorithm, but still it is exponential. Space required is also exponential. So this approach is also infeasible even for slightly higher number of vertices. I will prefer using greedy approach.
The Hamiltoninan cycle mainly efficient to find if there exist a tour that visits every city exactly once.
Hamiltonian Tour exists (because the graph is complete) and in fact many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle. Consider city 1 as the starting and ending point.
Generate all (n-1)! Permutations of cities and Calculate cost of every permutation and keep track of minimum cost permutation.