외판원 문제: (TSP: Traveling Salesman problem)

[fineman999]

외판원 문제의 이해:

• 외판원이 20개 도시로 판매 출장을 계획하고 있다고 가정하자.
• 외판원은 출발 도시에서 모든 도시를 방문하고 다시 되돌아와야 한다.
• 출장시간(또는 비용)을 최소로 줄이기 위한 방문 계획을 구하고 싶다.
• 주어진 그래프는 가중치 있는 방향 그래프라고 가정
• 가중치 있는 그래프에서 #94 의 최적화 문제

외판원 문제의 사례

• 가중치 있는 방향 그래프에서,
• 완전 그래프라면 가능한 경로의 총 수는 얼마일까?
• (n-1)(n-2) ... 1 = (n-1)!
• 팩토리얼 시간 복잡도: 지수시간 보다 더 나쁘다!
• (아무도 다항 시간에 증명 못함, 다항시간에 풀 수도 없다도 증명 못함)

외판원 문제: 동적 계획법으로 풀기

• W: 주어진 그래프 G = (V, E)의 인접 행렬
• V: 모든 도시의 집합
• A: V의 부분 집합
• D[Vi][A]: A에 속한 도시를 각각 한 번씩만 거쳐서 Vi에서 V1으로 가는 최단 경로의 길이

[fineman999]

1 << N: 비트 연산자 <<는 왼쪽 시프트(shift) 연산을 수행합니다. 1 << N은 이진수로 표현했을 때 오른쪽에서 N번째 비트를 1로 설정하는 것을 의미합니다. 이 코드에서는 DP 테이블의 두 번째 차원 크기를 2^N으로 설정하고 있습니다. 이는 비트마스크(bitmask)를 사용하여 부분 집합(subset)을 표현하기 위함입니다. 예를 들어, N=3인 경우, 1 << N은 8을 의미하며, DP 테이블의 두 번째 차원 크기는 8로 설정됩니다.