I've always been fascinated by the conceptual simplicity of the Traveling Salesman Problem and the ingenuity of its solutions. In this side project I try to implement some well-known algorithms for the problem as I use it to learn Go.
- Nearest Neighbor (code: nn)
- Farthest Insertion (code: farthest-insertion)
- Nearest Insertion (code: nearest-insertion)
- Min Max Insertion (code: min-max-insertion)
Modify the tsp-data.json file depending on your needs. The file expects two inputs: the algorithm code name (check the values in parentheses in the previous section) and the instance nodes as x, y coordinates.
Execute go run main/main.go and the result should look like:
[{1 1} {0 0} {3 3} {20 20}]
24.041630560342615
Indicating the order of the route and the total distance.
The following algorithms are not part of the future plans of the repository, but it'd be a good idea to have them.
- Implement the nearest neighbor with precomputed neighbors
- Implement the double-sided nearest neighbor heuristic