Programming Assignment: Traveling Salesman using A* algorithm Introduction: Let V = {v1, . . . , vn} be a set of citie

[answerhappygod]

Programming Assignment: Traveling Salesman using
A* algorithm
Introduction:
Let V = {v1, . . . , vn} be a set of cities and let d(vi, vj ) =
d(vj , vi) be the (symmetric) distance between city vi and vj . The
optimal traveling salesman tour of the cities is a sequence of
cities that visits every city in V exactly once and returns to the
city at which the sequence started, it has to minimize the total
distance traveled. The TSP problem is the computational problem of
finding such an optimal tour. The TSP problem is NP-complete, which
means that it’s unlikely that an efficient algorithm exists for
this problem. In this assignment, you will implement a heuristic
search algorithm to find the optimal tour.
Assignment:
Write a program that finds the optimal traveling salesman tour.
Input will be provided as a graph. The graph is undirected and
guaranteed to be complete (there’s an edge between every pair of
nodes). Every edge will have an attribute ‘weight’ that gives the
length of the edge.
Output should consist of two lines of the following
format:
Tour: A B F G H I L K M
Cost: 180.5