Traveling Salesman Problem Solutions
-
Developed a comprehensive suite of 6 algorithms to tackle the Traveling Salesman Problem (TSP), a classic NP-hard optimization challenge:
- Brute Force
- Nearest Neighbor (Greedy Algorithm)
- Christofides Algorithm
- Dynamic Programming
- Genetic Algorithm
- Linear Programming Relaxation
- Implemented the entire project in C++, leveraging the Standard Template Library (STL) and Boost Graph Library to ensure efficient data structures and graph operations.
- Designed the algorithms to effectively solve TSP instances with moderately sized graphs, balancing performance and scalability.
- Conducted comparative analysis of algorithm performance across various graph sizes and complexities, providing insights into trade-offs between solution quality and computational efficiency.
- Demonstrated proficiency in advanced algorithm design, optimization techniques, and C++ programming, while gaining practical experience in solving real-world combinatorial optimization problems.
Technologies
- C++ STL
- Unix CLI