I have displayed visualizations of several inputs of data. I am using data from the TSPLIB as input and the Hamiltonian paths we create as outputs. I am focusing on the visualizations of the paths created by the Nearest Neighbor, Greedy, Convex Hull, and Christofides algorithms. The last visualization corresponds to that of the optimal path. Code for the computation of the paths and visualizations can be found here. For the graphs, the % difference is calculated by abs(optimal path length - algorithm path length)/ optimal path length. For the first and last dataset, I used the adjacency matrix provided with the TSP instance. For the rest
of the data sets, I calculated the adjacency matrix based on euclidean distance.
1. P01 (15 nodes)
Our smallest dataset that I tested. Below are the algorithms and their respective costs.
The next four vids show the performance of Christofides on the dataset.
2. ATT48 (48 nodes)
A dataset containing 48 of the US state capitals. Below are the algorithms and their respective costs.
The next four vids show the performance of Christofides on the dataset.
3. ch150 (150 nodes)
A dataset involving 150 mining locations. Below are the algorithms and their respective costs.
The next four vids show the performance of Christofides on the dataset.
4. a288 (150 nodes)
A dataset involving 288 city locations. Below are the algorithms and their respective costs.
The next four vids show the performance of Christofides on the dataset.
Extra DataSets (Not included in data! Just done for fun!) pcb442 (442 nodes)
A dataset involving 442 city locations. Below are the algorithms and their respective costs.
The next four vids show the performance of Christofides on the dataset.