Assignment: NP-Completeness and Heuristic Algorithms
1. NP-Completeness: Consider the Travelling Salesperson (TSP) problem that was covered in
the exploration.
Problem: Given a graph G with V vertices and E edges, determine if the graph has a TSP
solution consisting of a cost k.
Prove that the above stated problem is NP-Complete
2. Implement Heuristic Algorithm:
a. Below matrix represents the distance of 5 cities from each other. Represent it in the
form of a graph
A B C D E
A 0 2 3 0 0
B 2 0 15 2 0
C 3 15 0 0 13
D 0 2 0 0 9
E 0 0 13 9 0
b. Apply Nearest-neighbour heuristic to this matrix and find the approximate solution
for this matrix if it were for TSP problem.
c. What is the accuracy ratio of your approximate solution?
d. Write the pseudocode for the nearest neighbour heuristic
----------------------(Ungraded question: you can try this question if time permits)---------------
Implement the Minimum Spanning Tree-based approach for the TSP problem that was discussed in
the exploration. Name your function approx_tsp_algo(G). Name your file TSP.py
Debriefing (required!): --------------------------
Report:
1. Approximately how many hours did you spend on this assignment?
2. Would you rate it as easy, moderate, or difficult?
3. How deeply do you feel you understand the material it covers (0%–100%)?
4. Any other comments?
Note: ‘Debriefing’ section is intended to help us calibrate the assignments.
