TSP_Algorithms_Comparison

This project compares the running time of three TSP problem algorithms and visualizes them.

Introduction

In this project, we used three different backtracking algorithms to solve the Travelling salesman problem, which is an NP-hard problem in combinatorial optimization, and compared the running time of the three algorithms and visualize them.

Introduction of the algoithms

The three algorithms are introduced as follows:

I. Bounding

After completing the general algorithm for TSP problems, a distance function was added as the bound function to do prunning which would reduce the time complexity. And this part is also used to generate data examples.

II. Branch and Bound

In this algorithm a function sort_tries is used to sort the feasible nodes and then we could prioritize promising paths. This strategy can solve the TSP problem with less running time in some cases.

III. Approximation

This algorithm use a greedy algorithm (similar to Prim's algorithm) to find the Minimum Spanning Tree (MST) of the input gragh and then Performs a depth-first traversal of the MST to generate a traversal path. Finally removes duplicate nodes from the traversal path to produce a valid TSP route. This algorithm has low time complexity, but there are some restrictions on the input graph, and the final result is not necessarily the shortest path, which is usually only an approximate value.

Introduction of the testing and visualization

We wrote a function to generate a large number of matrices and data groups that meet the TSP problem, input them into each algorithm to get the solution. And there are another two functions, one is to draw the graph of each solution and the other is to count the running time of each algorithm and draw it as a line graph like the following:

File information

You can find that we divide the Python code of each algorithm block into different files. tsp_report.ipynb is a Jupyter Notebook file, it describes the whole process of implementing each algorithm and visualizing its runtime, and includes all the python code and detailed interpretation for the codes. At the same time, you can modify and run the code in this file to complete the visualization process. Here is also a PDF file generated from the jupyter notebook file which can be used in study. This project is used for recording and self-learning, but everyone is welcome to use it!😉