O(n!) Combinatorial Explosion 극복을 위한 Approximation 전략 분석

Context

TSP는 모든 정점을 한 번씩 방문하는 최단 경로를 찾는 NP-hard 문제로, 정밀 해를 위한 Brute Force 적용 시 O(n!)의 시간 복잡도가 발생함. n=40 규모에서 우주 나이 이상의 연산 시간이 소요되는 Combinatorial Explosion으로 인해 Exact Solution 도출이 현실적으로 불가능함.

Technical Solution

• Polynomial-time 내 해 도출을 위해 최적해를 포기하고 근사치를 찾는 Approximation Algorithm 도입
• 초기 해 생성을 위해 단순 규칙 기반의 Constructive Heuristic 적용
• 생성된 해의 품질을 높이기 위해 엣지를 교체하는 2-opt 및 k-opt 기반의 Improvement Heuristic 수행
• Local Minima 탈출을 위해 소수 개체의 유전자를 변형하는 Mutation 및 Crossover 기반의 Genetic Algorithm 설계
• Metric TSP 특성인 Triangle Inequality를 활용하여 MST 기반 DFS Traversal로 2-approximation 보장 구조 채택
• 실행 시간과 근사 정확도의 Trade-off 최적화를 위해 Adaptive k-opt 방식인 Lin-Kernighan Heuristic 적용