4.3 활용 사례 - 외판원 문제 해결하기
1930년대에 고안되어 널리 알려진 외판원 문제(Traveling Salesman Problem, TSP)를 예제로 살펴봅시다. 외판원 문제는 NP-난해 문제입니다. 이 문제를 어떻게 접근하면 좋을까요? 처음부터 바로 최적해를 구하려고 노력하는 대신, 모든 도시를 방문해야 한다는 조건만 만족하는 투어 일정을 무작위로 생성합니다. 그러고 나서 이 투어 일정을 점진적으로 개선합니다. 이 과정에서 반복해서 생성되는 투어 일정이 바로 후보 해결책이자 증명서가 됩니다. 방문해야 하는 도시 개수가 늘어나면 후보 해결책이 최적해인지 검증하는 데 걸리는 시간은 기하급수적으로 증가합니다. 그 대신 간편한 추론 방식을 이용하면 비록 최적해는 얻을 수 없어도 그것에 근접한 투어 일정을 생성할 수 있습니다.
▼ 표 4-1 외판원 문제
|
입력 |
n개의 도시로 된 리스트(도시는 V로 표기)와 도시 간 거리 dij (1 ≤ i, j ≤ n) |
|
출력 |
모든 도시를 한 번씩 방문하고 출발지로 되돌아오는 가장 짧은 투어 |
외판원은 주어진 리스트에 적힌 도시들을 모두 방문해야 합니다. 문제의 조건은 두 가지입니다.
• 리스트에 적힌 도시들 사이의 거리는 알려져 있습니다.
• 각 도시는 반드시 한 번만 방문해야 합니다.