EECS 281, Data Structures and Algorithms
Zoo Routing: MST and Traveling Salesperson
Graph algorithms over 2D cage coordinates: a minimum spanning tree with a wild-area border rule, a fast heuristic TSP tour, and an exact TSP solved by branch and bound.
What I built
- Implemented Prim's algorithm in O(n^2) on a dense implicit graph, labeling each point as wild (third quadrant), wall (negative axes), or other, and forbidding direct wild-to-other edges so paths must cross the wall.
- Built FASTTSP from a nearest-neighbor tour refined by 2-opt edge swaps until no swap shortens the tour.
- Built OPTTSP as a depth-first permutation search seeded with the heuristic tour's length, pruning a branch when its cost plus half the sum of each unvisited node's two cheapest edges could not beat the best tour found.
- Wrote test inputs that caught 7 of 8 seeded buggy solutions.