TSP는 NP-Complete.

안녕하세요 :) 주말 잘 보내시고 계신가요 ㅎㅎ?

비도 오고 그래서 뭔가 코딩하기 싫은...날이라서 계속 쓰자고 쓰자고 마음먹었던 NP-Hardness의 3탄!!!!

바로 TSP(Traveling Salesman Problem)는 NP-Complete라는 것을 증명하는 글을 써보려고 해요 :)

아직 P, NP의 개념을 모르시는 분들은 <P와 NP의 개념>.

NP-Hard, NP-Complete의 개념을 모르시는 분들은 < NP-Hard, NP-Complete >를 읽고와주세요.

이제부터 말할 개념들은 위 두 글을 읽고오지 않으면, 이해가 전혀 되지 않을거에요 ㅠㅠ

제 글이 아니더라도, P, NP, NP-Hard, NP-Complete의 개념에 대해서 공부하고 이 글을 봐주세요 :)

시작할게요!

TSP(Traveling Salesman Problem)

---

먼저 TSP((Traveling Salesman Problem)을 모르시는 분들을 위해, 간단하게 TSP가 뭔지 설명드릴려고해요 :)

혹시 TSP는 안들어봤어도, "외판원 문제"라고 들어본적 없으신가요?

외판원문제 == TSP입니다. 

자, 외판원이 있어요. Salesman이죠. 

이 Salesman은 어떤 도시에 왔어요.

이 도시엔 여러개의 집이 있는데, 이 집을 전부 "한번씩만" 방문해야합니다.

하지만 이 Salesman은 빨리 퇴근하고싶어해요.

이 Salesman이 모든 집을 각각 한번씩만 방문하고,(= 방문 했던 집은 다시 방문 X) 이때 가장 짧은 경로(= 어떤 순서로 집을 방문해야하는지) 를 구하는 것이 TSP. 즉 외판원 문제입니다. 

TSP는 보통 무향 완전 가중 그래프로 나타내지곤 하는데요, "완전"그래프이니 모든 집들 사이에 경로가 존재한다고 보면됩니다. 

바로

이렇게 말이죠. 

우리는 여기서 어떻게 집들(노드)을 방문해야 가장 짧은경로로 방문할 수 있을까요?

위 그림은...너무 많아서 ㅎㅎ

3개로 줄여볼게요.

자, Salesman은 어떤 순서로 집들을 방문해야할까요?

모든 집은 반드시 한번씩은 방문해야 하며, 한번 갔던 집은 방문하지 않습니다. 

그럼 

1 > 2  > 3  또는 3 > 2  > 1순으로 방문하면, 총 가중치가 30으로 가장 작은 경로를 얻을 수 있습니다. 

다른 경로들의 가중치를 볼까요? 

1 > 3 > 2 => 50,

2 > 3 > 1 =>50,

2 > 1 > 3 => 60,

3 > 1  > 2 => 60,

왜 TSP가 난해 문제로 꼽히냐면, 가능한 모든 경로를 다 봐야 최단경로를 알 수 있기 때문입니다. 

위의 그림처럼 집이 3개일땐, 3!의 경우의 수가 있습니다.

즉, TSP는 집들의 개수(= 노드의 개수)의 팩토리얼인 O(N!)의 시간복잡도를 가지게 됩니다.

TSP(Traveling Salesman Problem)는 NP-Complete임을 증명해보자. 

---

TSP가 뭔지도 알았으니, 이제 증명을 시작해볼까요?

1. NP-Complete는 NP에 속해야 하므로 TSP ∈ NP임을 증명하자. 

NP-Hard이면서 NP에 속할때 NP-Complete라고 그랬죠?

일단 이 TSP가 NP에 속하는지 먼저 보자구요.

어떤 Certificate를 줬을때, 다항시간에 Verify할 수 있으면 클래스 NP에 속한다고 그랬죠?

이때, 주의할 점이 있습니다. 

※주의할 점

문제는 Optimization 버전과, Decision 버전이 있는 것. 아시나요?

Optimization문제는 이름에서 볼 수 있듯이, "최적"문제입니다.

TSP의 Optimization버전은, 

Q : (무향 완전 가중 그래프를 주고) 이 그래프에서 모든 집을 한번씩만 방문하고 돌아나오도록, "최단경로"를 구해.

위 문제에대해서 NP임을 증명한다고 해봅시다.

어떤 Certificate가 주어지겠죠? 이 Certificate는 집들의 목록일거에요. 

하지만 이 Certificate가 최단경로라고 말할 수 있을까요?

이 Certificate이 Optimal이라는 것을 보장할 수 없습니다.

결국, "최단경로"를 구할려면 그래프의 가능한 모든 경우의 경로를 봐야한다는 것이죠.

즉, 다항시간에 Verify할 수 없다 -> NP에 속하지 않게 된다.

==> NP-Complete가 될 수 없다.

NP-Hard까지 밖에 안되는 것입니다. 

즉, 정리하자면 "TSP의 Optimization 버전은 NP-Hard이다"라는 것이죠. 

NP에 속하지 않으니 이 버전은 NP-Complete가 될 수 없습니다..

그러면 TSP의 Desicion버전은 무엇일까요? 

Q :  (무향 완전 가중 그래프를 주고) 이 그래프에서 모든 집을 한번씩만 방문하고 돌아나오는데, 그 가중치의 합이 K인것이 존재해?

자, 위 질문은 Certificate에 대해서 어떻게 대답할 수 있을까요?

역시 Certificate는 집의 목록일거에요. 이 집들의 목록을 보면서 가중치를 합해가면 되겠죠? 그 가중치의 합을 아는것이 오래걸릴까요? 

다항시간이 걸리게 됩니다. 

만약 가중치를 합해서 K가 나온다면, YES!라고 대답하면 되는거고, 

아니면 가만히 있으면 된다고 그랬죠?

다항시간에 Verify할 수 있으므로 NP임을 증명할 수 있고, NP-Complete문제가 될 수 있는 조건을 만족하게 됩니다. 

즉, 우리는 지금 TSP가 NP-Complete임을 증명하고 싶은거죠? 

== TSP의 Decision 버전으로 증명하는 것을 가정하는것입니다. 

우리는 지금 증명 1번을 끝낸거에요.

"NP-Complete는 NP에 속해야 하므로 TSP ∈ NP임을 증명하자."

TSP(Decision버전)는 NP에 속한다.

2. Transformation Function고안 = NP-Hard임을 증명하는 과정

어떤 문제가 NP-Complete임을 증명하고싶을때는, 그 증명할 문제와 "비슷한" NP-Complete문제를 골라 증명하게 됩니다.

2-1 ) 알려진 NP-Complete문제 중에서 비슷한 것을 고른다.

==> 헤밀토니안 사이클 문제( Hamiltonian  Cycle  Problem)

헤밀토니안 사이클이 뭔지 모르는 사람들을 위해 간단하게 설명드리자면,

주어진 그래프에서 출발점과 종료점만 두 번 나타나는 것을 제외하고는 정점이 한 번씩만 나타나는 사이클을 해밀턴 사이클 (Hamiltonian cycle) 이라고 합니다.

더 간단하게, "모든 노드들을 한번씩만 지나는 경로"라고 생각하시면 됩니다. (물론 Cycle이니 출발점과 종료점이  같아야겠죠? 이 사실은 잊지말아주세요 XD)

뭔가 TSP랑 비슷한 문제 같지 않나요?

실제로, TSP는 

"가중치가 주어진 완전그래프에서 가장 작은 가중치를 가지는 헤밀턴 사이클을 구하라"라고 정의를 할 수 있답니다. 이건 Optimization버전이겠죠? 

Decision버전은 "가중치가 주어진 완전그래프에서 가중치가 K인 헤밀턴 사이클이 존재하는가?"가 되겠네요.

아무튼!! 우리는 TSP문제랑 헤밀토니안 사이클 문제가 굉장히 비슷하다는 것을 알겠어요.

헤밀토니안 사이클은 NP-Complete로 증명이 되어있는 문제니, 

우리는 TSP가 NP-Complete임을 증명하기 위해 가장 비슷한 NP-Complete문제인 헤밀토니안 사이클 문제를 골랐어요.

우리 NP-Hard, NP-Complete글에서 Transformation Function에 대해서 공부했었죠? 

P의 인풋을 Q의 인풋으로 바꿔주는 그 함수요. 

P가 NP안에 있는 문제들 중 가장 어려운 문제, 즉 NP-Complete였다고 가정해봅시다. 

만약 P의 인풋을 Transformation Function으로 Q의 인풋으로 바꾼 뒤, Q를 해결하는 알고리즘으로 해당 인풋에 대해 아웃풋을 낸 뒤, 그 아웃풋을 P의 모든 인스턴스에 대해서 모두 정확하게 대답하면,

우리는 Q를 푸는 알고리즘으로 문제 P를 푼것이죠? 

그럼 Q가 P보다 "어렵거나 같은" 문제였고, NP안에 있는 가장 어려운 문제 P를 Q를 푸는 알고리즘으로 푼것이니

Q는 NP-Hard가 됩니다. 

그럼 지금, 우리는 TSP가 NP-Hard인거만 증명하면 TSP가 NP-Complete가 되는 상황이죠?

즉, 위에서 Q가 TSP가 되면 됩니다. 

즉!!! TSP를 푸는 알고리즘으로 헤밀토니안 사이클 문제를 풀면, TSP는 NP-Complete인 헤밀토니안 사이클 문제를 푼 것이므로 NP-Hard가 됩니다. 1번에서 TSP가 NP임을 증명했으니 NP-Complete가 되겠네요.

그럼,

헤밀토니안 사이클 문제의 인풋 -> Transformation Function -> TSP의 인풋

을 해볼까요? 

참고로 헤밀토니안 사이클 문제의 인풋은 그냥 "무향 그래프"입니다. TSP의 인풋이 뭐였는지 기억나시나요? 

"무향 완전 가중 그래프"였죠? (인풋이 하나 더 있습니다. Decision버전에서는 가중치의 합인 K가 있었죠?)

즉, 헤밀토니안 사이클 문제에서의 인풋은 완전 그래프가 아니어도 됩니다. == 모든 노드들간에 간선이 없어도 됩니다.

그냥 "무향 그래프"이기만 하면 됩니다. 

우리 "무향 그래프"를 하나 만들어볼까요? 

자, 가중치도 없고 모든 노드들간에 간선이 존재하지도 않는 정말 "무향 그래프"에요.

이것이 헤밀토니안 사이클 문제의 인풋입니다.

이걸 Transformation Function을 통해서 TSP의 인풋으로 만들어볼게요.

무향 그래프 -> Transformation Function -> 무향 완전 가중 그래프, K

Transformation Function이 어떻게 구현되어있는지는 저도..모릅니다...

그냥 간단하게 생각하면 됩니다! 

일단 가중치의 합 K는 잠깐 뒤에 보도록하고,

지금 위의 그림의 무향그래프를 어떻게 하면 "무향 완전 가중 그래프" 로 만들 수 있을까요?

일단 위 그래프에서

1.  모든 노드들간에 간선이 없다 -> 모든 노드들간에 간선이 있도록 만들자!

2. 간선에 가중치가 없다 -> 간선에 가중치를 주자!

이렇게 하면, TSP의 인풋인 무향 완전 가중 그래프가 만들어 질 것 같네요!

모든 노드들간에 간선이 있도록 만들어주려면 현재 노드간 간선이 없는 곳에 선을 그어주면 되겠죠? 

바로 이렇게요!

자 1번이 끝났습니다.

2번을 해봅시다. 가중치?

가중치는 어떻게 줘야 할까요? 모든 간선에는 가중치가 있어야 할 것입니다.

그럼 이 간선은 10주고…여기는 20주고..이러면 될까요?

그러면 안되겠죠?

가중치는 주는데에는 조건이 있습니다.

1. 원래 있던 간선에는 가중치를 0을 준다.

2. 추가되는 간선에는 가중치를 1을 준다. 

바로

이렇게 말이죠!!

마지막으로, 우리 TSP의 인풋이 뭐라고 그랬죠? 지금 TSP의 Decision버전을 가지고 NP-Complete임을 증명한다고 그랬죠? 

그러면 여기서 K가 필요합니다.

도대체 얼마의 가중치의 합을 가지도록 할것인지 정해야겠죠?

이 K를 0으로 set해줍니다. 

자, 우리는 지금

헤밀토니안 사이클 문제의 인풋(무향그래프)을 TSP의 인풋(무향 완전 가중 그래프, K)으로 바꿨고,

이제 TSP를 푼 결과가 헤밀토니안 사이클 문제의 모든 인스턴스에 대해서 참인 결과를 낼 수 있다면,

우리는 TSP를 푸는 알고리즘으로 헤밀토니안 사이클 문제를 푼것이므로 TSP가 NP-Hard가 되겠네요.

TSP를 풀어봅시다.

Q : (무향 완전 가중 그래프를 주며) 이 그래프에서 모든 노드들을 한번씩만 방문하고, 그 가중치의 합이 0인게 있어? (Decision ver.)  (위에서 K는 0으로 set해줬기때문)

(== 이 그래프에서 K=0인 헤밀토니안 사이클이 있어?)

이제부터 가장 중요합니다! 주목하세요 :)

만약!!!!!!!!!

K가 0인 헤밀토니안 사이클이 있다고 가정해봅시다. 

우리 아까 추가된 간선에는 가중치를 1로 줬었죠?

만약!!!! K가 0인 헤밀토니안 사이클이!!!있다면!!!!!!

이 추가된 간선을 한번이라도 지날 수 있을까요?

이 추가된 간선의 가중치는 1이기때문에, 지나가는 순간 K는 0이 아니게 됩니다.

그러니까!!!!

 K가 0인 헤밀토니안 사이클이 있다면!!!

이 추가된 간선은 지나지 않았다!!!!라는 것이 되겠죠. 

또 주목해야할 점이 있습니다.

K가 0인 헤밀토니안 사이클이 존재한다면, 추가된 간선. 즉, weight가 1인 간선은 지나지 않았다고 방금 말씀드렸죠? 

그럼 저 추가된 간선을 생각하지 말아봅시다.

즉!!!!!! TSP의 인풋으로 바꾸기 전의, 헤밀토니안 사이클 문제의 인풋이었죠?

아니 우리 지금 K가 0이려면, 추가된 간선은 한번도 안지나야되는데, 

지금 우리가 헤밀토니안 사이클의 인풋을 TSP의 인풋으로 바꿨지만,

결국!!!!!!!!결국엔 추가된 간선을 한번도 사용하지 않았으므로 헤밀토니안 사이클의 인풋을 그대로 쓴 것이죠.

(가중치는 있지만)

 

그러니까!!! TSP가 YES이면, 당연하게 헤밀토니안 사이클 문제도 YES가 되는거죠.

가중치가 거슬리지만, 가중치가 0이나 가중치가 없는거나...똑같은거죠? 

우리는 지금 TSP를 풀었지만, 추가된 간선을 건드린게 없으니 헤밀토니안 사이클을 자연스럽게 푼것이죠. 

만약 TSP가 NO라면? 

TSP가 NO라는 소리는, K가 0인 헤밀토니안 사이클이 없다

== 가중치의 합이 0이 아니다 == 추가된 간선. 즉, weight가 1인 간선을 지났다.

== 원래 헤밀토니안 사이클 문제의 인풋에는 없던 간선 == 헤밀토니안 사이클 문제에서도 NO.

그렇습니다.. TSP가 NO라면, 헤밀토니안 사이클 인풋에서는 존재하지도 않던 간선을 지난 것과 마찬가지이므로 헤밀토니안 사이클 문제에 대한 대답도 NO가 되게 됩니다. 

결국, 우리는 TSP를 푸는 알고리즘으로 헤밀토니안 사이클 문제를 푼 것이죠?

즉!! “TSP는 NP-Hard”라고 할 수 있겠네요.

1과 2를 통해 최종 결론을 내자면,

TSP는 NP에 속하며 동시에 NP-Hard이므로 NP-Complete이다.

라고 할 수 있겠네요.

솔직히…이 글이 이렇게 길어질 줄 몰랐는데zzzz

쓰면서 뭔가 배울 때 기억도 나고 정말 좋았어요 :)

정말 처음 수업시간에 이거 증명할 때, 진짜 와..너무 신박하다.. 하면서 너무 재밌게 증명했었거든요.

아무튼..쓰면서 제가 어렵게 쓴 부분이 있을지도 모르겠어요 ㅠㅠ

최대한 풀어쓰려고 노력했는데 ㅜ_ㅜ

지적할점이나 궁금한점이 있다면, 댓글이나 PC화면 오른쪽 하단에서 볼 수 있는

채널 서비스를 이용해주세요 :)

그럼 오늘도 도움이 되었길 바라며…ㅎㅎ