외판원 문제: (TSP: Traveling Salesman problem) #95
Description
외판원 문제의 이해:
- 외판원이 20개 도시로 판매 출장을 계획하고 있다고 가정하자.
- 외판원은 출발 도시에서 모든 도시를 방문하고 다시 되돌아와야 한다.
- 출장시간(또는 비용)을 최소로 줄이기 위한 방문 계획을 구하고 싶다.
- 주어진 그래프는 가중치 있는 방향 그래프라고 가정
- 가중치 있는 그래프에서 해밀턴 회로와 해밀턴 경로: Hamiltonian Cycle or Path #94 의 최적화 문제
외판원 문제의 사례
- 가중치 있는 방향 그래프에서,
- 완전 그래프라면 가능한 경로의 총 수는 얼마일까?
- (n-1)(n-2) ... 1 = (n-1)!
- 팩토리얼 시간 복잡도: 지수시간 보다 더 나쁘다!
- (아무도 다항 시간에 증명 못함, 다항시간에 풀 수도 없다도 증명 못함)
외판원 문제: 동적 계획법으로 풀기
- W: 주어진 그래프 G = (V, E)의 인접 행렬
- V: 모든 도시의 집합
- A: V의 부분 집합
- D[Vi][A]: A에 속한 도시를 각각 한 번씩만 거쳐서 Vi에서 V1으로 가는 최단 경로의 길이