CS614 ASSIGNMENT 2 SOLUTION 2023

CS614 ASSIGNMENT 2 SOLUTION 2023, CS614 ASSIGNMENT 2 SOLUTION SPRING 2023. In this assignment, we were tasked with implementing a simple, yet efficient algorithm to solve the travelling salesman problem. To do this, we started by researching existing approaches and identifying their strengths and weaknesses. We then used this knowledge to design and implement our own solution, which leverages a combination of greedy heuristics and local search techniques.

Our algorithm begins by selecting a random starting point and iteratively choosing the nearest unvisited neighbour until all cities have been visited. At this point, we use a local search technique to optimize the tour by swapping adjacent cities and checking for an improvement in the overall distance. This process is repeated until no further improvements can be made.

One of the challenges we faced was balancing the trade-off between exploration and exploitation. On the one hand, we wanted to explore different paths to avoid getting stuck in local optima. On the other hand, we also wanted to exploit promising paths to converge quickly to a good solution. To overcome this, we used a temperature-based approach, where the probability of accepting a worse solution decreases as the temperature decreases.

Overall, our algorithm performed well on the provided test instances, achieving near-optimal solutions in a reasonable amount of time. However, there is still room for improvement, particularly in handling larger instances and incorporating more advanced techniques such as genetic algorithms or ant colony optimization.

In conclusion, the travelling salesman problem remains a challenging and important problem in computer science, with numerous practical applications. By leveraging a combination of heuristics and search techniques, we were able to design and implement a simple yet effective algorithm to tackle this problem. We hope that our solution can serve as a starting point for further research and exploration in this area.