Donut Delivery
Project Overview
Graph Theory Optimization Suite
This project implements a sophisticated computational geometry solution that tackles three fundamental algorithmic problems:
1) Minimum Spanning Trees (MST)
2) Fast Traveling Salesman Problem (TSP) approximation
3) Optimal TSP solutions.
Despite sharing a name with the famous spinning ASCII donut, this is actually a graph theory project dealing with 2D coordinate optimization problems with geographical constraints.
Technical Architecture
The project features a constraint-based graph problem where vertices exist in three distinct regions: Canada (x>0, y>0), USA (x<0 or y<0), and Border (axes). The key constraint is that MST edges cannot directly connect Canadian and American vertices without passing through border vertices, adding a layer of complexity beyond standard graph algorithms
Core Algorithmic Components
MST Implementation: Uses Prim's algorithm with custom connectivity rules that respect the geographical constraints. The algorithm efficiently determines when an MST is impossible (when both Canadian and American vertices exist without any border vertices).
FASTTSP Mode: Employs a nearest-neighbor greedy construction followed by limited 2-opt local optimization. The implementation cleverly uses squared distances for comparisons to avoid expensive square root calculations, significantly improving runtime performance.
OPTTSP Mode: Implements a branch-and-bound algorithm with MST-based lower bounds for finding provably optimal TSP solutions. The solver includes multiple optimization heuristics (Or-opt, 3-opt) and uses various construction methods (nearest neighbor, cheapest insertion) to generate initial solutions and tight bounds for pruning.
Performance Optimizations
The codebase demonstrates several practical optimization techniques: avoiding floating-point operations where possible, using squared distance comparisons, limiting optimization iterations strategically, and implementing efficient data structures for path manipulation. The modular design allows easy switching between different solving modes via command-line arguments.