You should write a single program which implements the greedy algorithm based on nearest neighbours and a branch-and-bound algorithm to find approximate and optimal solutions for the Travelling Salesman Problem, respectively.
Program
Your program should read a symmetric matrix from a text file that describes weighted edges of an undirected, complete graph and find the Hamiltonian cycles using the greedy and branch-and-bound algorithms. Your program should also read a list of city names corresponding to the vertices of the graph represented by the adjacency matrix. The program will display the tour and related information.
Since this assignment focuses on the algorithmic solution of the problem, STL or Java Collection or other collection framework of the programming language of your choice can be used. Library functions can also be used.
Your program should be readable and well commented.
Data Structures and Algorithms
• Greedy algorithm
Strategy: Nearest neighbour
• Branch-and-bound algorithm
Upper bound: weight by nearest neighbours Lower bound: minimal weight without constraints Strategies:
1. Breadth-first;
2. Depth-first.
Choose suitable data structures for the algorithms and strategies, to be described in your report
