In the Grand Tour problem you are given a list of n cities a

In the Grand Tour problem, you are given a list of n cities along with their pairwise distances (i.e., you know the distance between every two cities). All distances are positive and symmetric (the distance between A and B is equal to the distance between B and A). You begin at a specified city C0, and must perform a ‘tour’, in which you visit every other city exactly once, and then return to C0. The goal is to minimize the total distance traveled. Design a reasonable greedy algorithm for solving this problem. Does it always find the correct answer (i.e., the shortest tour)? If yes, prove that it is always correct, and if no, provide a counterexample.

Solution

desirable greedy algorithm: Travelling salesman problem

decription of travelling sales man problem:

Here we find  the shortest possible route that visits each city exactly once and returns to the origin city.In this grand tour problem also we have to do the same.So travelling salesman is the best approach.It uses heuristic approach and these heuristic approaches always depend on approximations and we know that approximation is not always exact.So it will not give the corrct answer/result.

so we can try branch and bound algorithms which is better..