Question

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? Justify your answer with very well defined and sound reasoning in either case. Select the correct answer from above options

Answer 1

Greedy and dynamic techniques are optimization techniques. Although Dynamic approach is much faster and reduced time complexity but it proves impractical for any large n and still exponential. Therefore a greedy algorithm tries to find an optimal solution by making a sequence of greedy choices.Greedy algorithm makes the choice that looks best at that time, ʙᴇ sᴍᴀʀᴛ……………^_^