40. traveling salesman problem [14 2주차]

40. Traveling Salesman Problem [14-2주차]

2024년 1월 14일 일요일

오후 5:26

<Traveling Salesman Problem(외판원 문제)>

NP-Complete 문제.

가중치 그래프 G와 시작 노드 s가 주어진다.

s에서 시작하여 s에서 끝나고, s를 제외한 모든 노드를 한 번씩만 방문하고, 가중치 합이 최소가 되는 경로를 구하는 문제이다.

Search Tree는 다음과 같이 정의된다.

• Search Tree의 노드는 루트에서 시작하는 깊이 우선 탐색의 방문 순서대로 형성된다.

• 루트 노드는 s에 그대로 있는 경로를 나타낸다.
• 깊이 1의 노드들은 s에서 간선 하나를 타고 이동한 경로를 나타낸다.
• 일반적으로 정의하면, 자식 노드는 부모 노드의 경로에서 간선 하나를 타고 이동한 경로를 나타낸다.
• 그래프의 모든 노드를 다 지난 뒤 s로 돌아온 상태를 트리의 리프 노드로 한다.

다음과 같은 경우 cutoff한다.

• 이미 방문한 노드를 다시 방문하는 경우 cutoff한다.

• Search Tree 각각의 노드에 대해, 해당 노드가 나타내는 경로의 가중치 합을 P라 한다. 현재까지 구한 리프 노드의 P값 최솟값을 m이라 한다. 특정 노드의 P값이 m 이상이 되면 cutoff 한다.

<Traveling Salesman - Fancy Cutoff>

외판원 문제에서 Cutoff를 좀 더 효율적으로 하는 방법.

• 시작 노드를 s
• 이미 방문한 노드들의 집합을 S
• 방문하지 않은 노드들의 집합을 X
• 현재 방문하고 있는 노드를 u

라고 하자.

그래프에서, 다음과 같이 간선을 선택한다.

a.     X의 각 노드 i에 대해, i와 {노드 s, 노드u, X-i의 노드}를 잇는 간선 중 1, 2번째로 작은 두 간선을 선택한다. (들어가는 간선, 나가는 간선을 의미함)

b.     u와 X의 노드를 연결하는 간선 중 가장 작은 것 하나를 고른다.

c.      s와 X의 노드를 연결하는 간선 중 가장 작은 것 하나를 고른다.

같은 간선이 중복해서 선택될 수 있으며, 만약 2번 중복 선택되었다면 그 간선은 2개로 친다.

고른 간선들의 가중치를 모두 더해 2로 나눈 값을 C라 하자.

2로 나누는 이유는 다음과 같다.

• 만약 5개의 노드가 남아있다면 12개의 노드를 고르게 된다. 실제로 지나야 하는 간선은 6개이므로, 가중치 합을 cutoff에 쓰려면 2로 나누는 것이 좋다.

Search Tree의 현재 노드에서, (P + C) 가 m보다 크면 cutoff한다.

이러한 cutoff가 정상적으로 작동한다는 근거 :

• 현재 상태에서 정답으로 가는 어떤 경로든 C보다 크다는 것을 증명하면 된다.

정답으로 가기 위한 임의의 경로에 대해, 그 경로 내의 간선을 절반으로 자른다(절반의 가중치를 가진 두 개의 간선으로 나눔). 그러면 X의 노드마다 경로 내의 간선을 두 개씩 할당할 수 있다.

X의 각 노드에 대해, 가장 작은 간선 두 개의 가중치 합을 2로 나눈 것은, 경로 내의 두 개의 절반 간선의 가중치 합보다 작음이 명백하다.

s와 u에 연결된 간선에 대해서도 마찬가지 원리가 적용된다.

따라서, 정답으로 가는 어떤 경로의 가중치 합이든, C보다 작을 수 밖에 없다.