tsp
Mathematical Programming with Python
https://people.sc.fsu.edu/~jburkardt/classes/...
python_2025/tsp/tsp.html

tsp: the Traveling Salesperson Problem, seeks the shortest round trip on a graph that visits every node exactly once. There is no algorithm that is guaranteed to produce the best solution. We will look at brute force for small problems, some simple approaches that seem likely to handle moderate problems, discover that even visiting the 48 "mainland" state capitals is NOT a moderate problem, and then see that an approach suggested by Cleve Moler does a very good job on that problem.

Lecture notes:

• tsp.pdf

• five_position.txt, lists the (x,y) coordinates of 5 cities.
• five_map.py, plots the locations, names, and connections between 5 cities.
• five_map.png, the location, name, and connection map.
• five.py, defines a distance table for 5 cities, and solves the TSP using the brute force approach.
• five_distance.dot.png, shows a distance table for 5 cities.

• fifteen_position.txt, lists the (x,y) coordinates of 15 cities.
• fifteen.py. defines a distance table for 15 cities, then tries to estimate a TSP solution using the greedy approach, and random sampling.

• fortyeight_position.txt, lists the (x,y) coordinates of 48 cities.
• fortyeight.py, defines a distance table for 48 cities, then tries to estimate a TSP solution using the greedy approach, random sampling, and Cleve Moler's traveler() program.