외판원 문제 솔버 (TSP)

외판원 문제 솔버 (TSP) 정보

외판원 문제 솔버는 고전적인 외판원 문제(Traveling Salesman Problem, TSP)를 위한 실용적이고 교육적인 계산기입니다. 외판원 문제란 여러 도시와 각 도시 사이의 거리가 주어졌을 때, 모든 도시를 정확히 한 번씩 방문하고 다시 출발지로 돌아오는 최단 경로를 찾는 문제입니다. 이 솔버는 평면 좌표 또는 사용자 정의 거리 행렬을 입력받아 문제 크기에 따라 자동으로 최적의 알고리즘을 선택하며, 결과 경로를 애니메이션 SVG 지도로 렌더링합니다.

외판원 문제란 무엇인가요?

형식적으로, 정점 집합 V = {1, 2, ..., n}과 간선 가중치 d(i, j)를 가진 완전 가중 그래프 G = (V, E)가 주어졌을 때, TSP는 다음을 최소화하는 정점의 순열 π를 찾습니다:

마지막 항은 루프를 닫는 역할을 합니다. TSP는 조합 최적화 분야에서 가장 오래되고 많이 연구된 문제 중 하나로, 일반적인 경우 NP-난해(NP-hard)에 속합니다. 이는 모든 사례를 다항 시간 내에 해결하는 알고리즘이 없음을 의미합니다. 그럼에도 불구하고 차량 경로 최적화, PCB 드릴링, DNA 시퀀싱, 창고 피킹 경로, 천체 관측 일정, 우편 배달 등 수많은 실무 분야에서 활용됩니다.

이 솔버의 작동 원리

Held–Karp 동적 프로그래밍 (정확한 해)

소규모 사례(최대 12개 도시)의 경우, 솔버는 1962년 Richard Bellman과 Michael Held 및 Richard Karp가 각각 독립적으로 발표한 Held–Karp 알고리즘을 사용하여 증명 가능한 최적 경로를 계산합니다. 핵심 점화식은 다음과 같습니다 (여기서 C(S, j)는 부분 집합 S를 방문하고 정점 1에서 정점 j로 가는 최단 경로임):

최적 경로 비용은 min_j [C({1,...,n}, j) + d(j, 1)]이 됩니다. Held–Karp는 O(2ⁿ · n²)의 시간 복잡도와 O(2ⁿ · n)의 메모리를 사용합니다. 이는 브루트 포스 방식인 n!보다는 훨씬 개선된 것이지만 여전히 지수적입니다. 약 20개 도시를 넘어가면 메모리 사용량이 감당할 수 없을 정도로 커집니다.

Nearest-Neighbor + 2-opt (휴리스틱)

더 큰 사례의 경우 솔버는 2단계 휴리스틱을 사용합니다. 먼저 Nearest-Neighbor 알고리즘이 각 시작 정점에서 가장 가까운 미방문 도시를 탐욕적으로 선택하여 빠른 경로를 구축합니다. 솔버는 여러 시작 정점을 시도하여 가장 좋은 경로를 유지합니다. 그 후 2-opt 국소 탐색을 통해 두 개의 간선을 반복적으로 제거하고 결과 경로를 다른 방식으로 재연결하여 경로를 개선합니다:

기하학적으로 2-opt는 경로 내의 모든 "교차"를 제거합니다. 교차하는 두 세그먼트는 항상 교차하지 않게 재연결하여 전체 길이를 단축할 수 있습니다. 알고리즘은 더 이상 개선할 수 없는 국소 최적 상태(이를 2-최적 경로라 함)에서 멈춥니다. 실제 유클리드 사례에서 2-opt는 수 밀리초 내에 실제 최적해의 2~5% 이내인 경로를 찾아냅니다.

입력 형식

좌표 모드 (x, y)

한 줄에 하나의 도시를 입력합니다. 각 줄은 라벨, x, y 형식이며 라벨은 선택 사항입니다. 솔버는 유클리드 거리를 자동으로 계산하고 실제 위치에 도시를 시각화합니다.

거리 행렬 모드

비음수 거리로 구성된 n × n 정사각 행렬을 입력합니다. 각 행은 한 줄씩 입력하며 값은 공백이나 쉼표로 구분합니다. 행렬은 대칭일 수도, 비대칭일 수도 있습니다. 비대칭 행렬은 일방통행로, 가용성에 따른 항공권 가격, 바람의 영향을 받는 이동 등을 모델링할 때 쓰입니다. '행렬 라벨' 필드에서 라벨을 별도로 제공할 수 있습니다.

알고리즘 비교

솔버 사용 방법

1. 입력 모드 선택: 도시가 유효한 (x, y) 위치를 가지면 '좌표'를, 비용이 비유클리드적이거나 비대칭이면 '거리 행렬'을 선택합니다.
2. 데이터 입력: 한 줄에 한 도시 또는 한 행씩 입력합니다. 폼 위의 빠른 예제 버튼을 클릭하여 유효한 예시를 채워볼 수 있습니다.
3. 알고리즘 선택: '자동'으로 두는 것이 좋습니다. 사례가 충분히 작으면 Held-Karp를, 그렇지 않으면 NN + 2-opt를 사용합니다. 비교를 위해 특정 알고리즘을 강제할 수도 있습니다.
4. 폐쇄형 또는 개방형 선택: 폐쇄형 경로는 출발지로 다시 돌아오는 전통적인 TSP입니다. 개방형 경로는 외판원이 다른 도시에서 끝나는 관련 문제인 '해밀턴 경로' 문제를 해결합니다.
5. 해결 클릭: 결과 페이지에는 총 경로 길이, 경로 애니메이션 SVG('애니메이션 재생'으로 다시 볼 수 있음), 전체 방문 순서, 간선별 상세 분석, 경로가 강조된 거리 행렬이 표시됩니다.

작업 예시

직사각형과 꼭대기로 구성된 5개 도시 A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5)를 가정해 봅시다. 솔버 결과:

• 경로: A → D → E → C → B → A
• 길이: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• 최적인가요? 예 — Held–Karp가 이보다 더 짧은 경로는 없음을 증명합니다.
• 왜 이 순서인가요? 이 경로는 다섯 개의 점의 볼록 껍질(convex hull)을 따라갑니다. 유클리드 TSP의 고전적 특징 중 하나는 최적 경로가 볼록 껍질 위의 점들을 순환 순서대로 방문하고 내부 점들을 인접한 껍질 이웃 사이에 배치한다는 점입니다. A → C → B → D → E → A (길이 ≈ 21.8)와 같이 경로가 교차하는 경우에는 2-opt를 통해 교차를 풀어 더 짧은 결과를 얻을 수 있습니다.

실세계 적용 사례

• 물류 및 배송 — 연료와 시간을 최소화하기 위해 운전자의 하루 15개 경유지 경로 최적화.
• 제조 — 헤드 이동을 최소화하기 위한 PCB 기판의 CNC 드릴 구멍 순서 결정.
• 게놈 조립 — 거리 행렬로 인코딩된 중첩 유사성에 따른 DNA 조각 순서 지정.
• 천문학 — 관측 시간을 최대화하기 위해 대상 별 사이의 망원경 회전 일정 예약.
• 창고 피킹 — 최소한의 단계로 주문을 이행하기 위한 통로 방문 순서 지정.
• 여행 계획 — 이동 시간과 요금을 최소화하는 다도시 여행 계획.

자주 묻는 질문

외판원 문제란 무엇인가요?

외판원 문제(Traveling Salesman Problem, TSP)는 모든 도시를 정확히 한 번 방문하고 다시 출발 도시로 돌아오는 최단 경로를 찾는 문제입니다. 조합 최적화의 대표적인 난제이며 일반적인 경우 NP-난해입니다.

Held–Karp 알고리즘이란 무엇인가요?

Held–Karp는 TSP를 정확하게 해결하는 동적 프로그래밍 알고리즘으로 시간 복잡도는 O(2ⁿ · n²)입니다. 브루트 포스보다 빠르지만 여전히 기하급수적이라 대략 20개 도시 이하일 때 주로 쓰입니다. 본 솔버는 12개 이하일 때 이 방식을 사용합니다.

2-opt란 무엇이며 왜 사용되나요?

2-opt는 두 개의 간선을 끊고 다르게 연결하여 경로를 개선하는 휴리스틱입니다. 계산이 빠르고 최적해에 근접한 결과를 내놓기 때문에 대규모 TSP에서 가장 널리 사용되는 표준 기법입니다.

언제 좌표 모드를 사용하고 언제 거리 행렬 모드를 사용하나요?

지도상의 점이나 회로 기판 구멍처럼 직선 거리가 중요한 경우 좌표를 사용하세요. 항공권 가격, 교통량이 포함된 시간, 일방통행 등 기하학적으로 설명되지 않는 비용이 있다면 거리 행렬을 사용하세요.

2-opt 솔루션이 항상 최적인가요?

아니요, 2-opt는 국소 최적해를 찾습니다. 결과가 최적에 매우 가깝긴 하지만 완벽한 최단 경로를 보장하지는 않습니다. 보장된 최적해가 필요하면 소규모 사례에서 Held-Karp를 선택하십시오.

이 도구는 비대칭 거리 행렬을 지원하나요?

네. 비대칭 행렬을 지원하며 Held-Karp와 2-opt 모두 비대칭 비용을 정확하게 계산합니다. 이는 일방통행로나 기류의 영향을 받는 항공편 등 실무적인 경로 문제에 유용합니다.

더 읽어보기

• 외판원 문제 — 위키백과
• Held–Karp 알고리즘 — Wikipedia (영문)
• 2-opt — Wikipedia (영문)
• 최근접 이웃 알고리즘 — 위키백과

고급 수학 연산 도구:

• 앤티로그 계산기
• 베타 함수 계산기
• 이항 계수 계산기
• 이항 확률 분포 계산기
• 비트-계산기
• 중심극한정리 계산기
• 조합 계산기
• 상보 오차 함수 계산기
• 복소수 계산기
• 엔트로피 계산기
• 오차 함수 계산기
• 지수 붕괴 계산기 - 높은 정밀도
• 지수 성장 계산기 높은 정밀도
• 지수 적분 계산기
• 지수 계산기 (높은 정확도)
• 팩토리얼 계산기
• 감마 함수 계산기
• 황금비율 계산기
• 반감기 계산기
• 백분율 성장 계산기 추천
• 순열 계산기
• 포아송 분포 계산기
• 다항식 근 계산기와 상세한 단계
• 확률 계산기 추천
• 확률 분포 계산기
• 비례식 계산기 추천
• 이차 공식 계산기
• 공학용 계산기 추천
• 과학적 표기법 계산기
• 유효숫자 계산기 새로운
• 큐브 합계 계산기
• 연속 숫자의 합 계산기
• 제곱합 계산기
• 진리표 생성기
• 집합론 계산기
• 벤 다이어그램 생성기 (3세트)
• 중국인의 나머지 정리 계산기
• 오일러 피 함수 계산기
• 확장 유클리드 알고리즘 계산기
• 모듈러 곱셈 역원 계산기
• 연분수 계산기
• 다익스트라 최단 경로 계산기
• 최소 신장 트리 계산기
• 그래프 차수열 검증기
• 완전순열 (부분계승) 계산기
• 스털링 수 계산기
• 비둘기집 원리 계산기
• 마르코프 체인 정상 상태 계산기
• 반올림 계산기 새로운
• 음이항분포 계산기 새로운
• 중복순열 계산기 새로운
• 모듈러 거듭제곱 계산기 새로운
• 원시근 계산기
• 불 대수 간소화기 새로운
• 카르노 맵 (K-Map) 솔버 새로운
• 그래프 채색 계산기 새로운
• 위상 정렬 계산기 새로운
• 인접 행렬 계산기 새로운
• 포함배제 계산기 새로운
• 선형 계획법 솔버 새로운
• 외판원 문제 솔버 (TSP) 새로운
• 해밀턴 경로 검사기 (Hamiltonian Path Checker) 새로운
• 평면 그래프 검사기 새로운
• 네트워크 플로우 계산기 (최대 유량) 새로운
• 안정된 결혼 문제 해결기 새로운
• 군론 위수 계산기 새로운
• 환과 체 계산기 새로운