여행하는 세일즈맨 문제 (TSP)
Source
Evernote/Technote scraps/ Travelling Salesman Problem (여행하는 세일즈맨 문제).md
Summary
여행하는 세일즈맨 문제(TSP)는 직관적으로 쉬워 보이지만 모든 경우의 수를 검토하는 것은 계산적으로 불가능할 정도로 어려운 대표적인 NP-hard 문제이다. 가장 짧은 경로를 차례로 선택하는 탐욕적 접근법(Greedy approach)이나 시작점 변경과 같은 단순 변형은 실제 적용 시 불만족스러운 결과를 자주 초래하므로 유효하지 않다. 이 문제는 단순한 여행 계획을 넘어 공장 자동화 및 생산 자동화 등 산업 현장에서 빈번하게 발생하며, 효율적인 해결 방안이 필수적이다.
Key Points
- TSP는 알고리즘 입문에서 자주 등장하지만, 전수 조사(Brute-force)는 시간 복잡도 문제로 사실상 불가능하다.
- 가장 짧은 간선을 우선 선택하는 탐욕적 알고리즘은 로컬 최적해에 갇혀 전역 최적해에서 벗어난 불만족스러운 결과를 자주 산출한다.
- 시작점 최적화 등 단순 변형 역시 근본적인 해결책이 되지 못한다.
- TSP는 이론적 난이도 외에도 공장 자동화, 생산 라인 최적화 등 실제 산업 자동화 분야에서 핵심적인 실용적 가치를 가진다.