Traveling Salesman Problem 외판원 문제 (NP-Hard)

이 문제 풀다가 TSP로 환원 (reduction) 될 수 있음을 알게 됨.

(여러 알고리즘을 공부해야 하는 이유; 문제를 적절히 변형시켜서 이렇게 알고 있는 알고리즘으로 바꿔서 풀이 가능)

 

Traveling Salesman Problem :

"여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것"

 

NP-Hard 문제임.

완전 탐색은 모든 도시 조각으로 쪼개서 하나씩 나열해보는 것 : 경우의 수 N! 가지 O(N!)

 

이외 2가지 풀이가 있음

 

1. 동적 계획법

https://www.youtube.com/watch?v=wj44Dd0zdzM 

 

요약)

- DP[출발점][방문해야 하는 노드 set S] : 출발점에서 출발해서 S에 있는 노드들을 모두 거친 후, 시작점 (출발점과 다름; 사이클의 진짜 시작점) 으로 돌아오는 min path

- DP[출발점][S] = min (Edge[출발점][도착점] + DP[도착점][S-{도착점}]) (for 도착점 in S)

S = 공집합, 크기 1, 크기 2, ... 일때 TC 만들어보며 점화식 느끼기

 

부분 문제 수 : N * 2^N (테이블 사이즈)
각 부분 문제 풀이 시간 : N (출발점에서 다른 모든 노드 체크해서 갈 수 있으면 가기) 

최종 Time complexity : O(N^2 * 2^N)

 

 

또 다른 참고할만한 자료) 삼성 SWEA - SW 문제해결 응용 - 07 DP-2 4차시 TSP DP

 

 

2. 분기한정법 (공부 아직 안함)

https://www.youtube.com/watch?v=v558MViN0AU 

---

* 모든 노드를 방문해서 다시 시작점으로 돌아온다는 점에서 해밀턴 순환 (Hamilton cycle)

+ 가장 작은 가중치를 찾는다는 점에서 최적화 문제 (Optimization problem)

TSP = "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라" (위키피디아)

 

* TSP 최적화 버전은 NP-Hard지만, 결정 문제 버전은 NP-Complete (블로그)(stackoverflow)

 

💡 출발지점으로 돌아와야 한다는 제약 조건을 없애는 방법 - 모든 노드와 weight 0으로 연결되는 dummy node 하나를 만들어서 거기서 시작하기

(매우 유용 - 다른 문제들에서도 쓰이는 테크닉; ex. 종만북 FIRETRUCKS)

https://stackoverflow.com/questions/6733999/what-is-the-problem-name-for-traveling-salesman-problemtsp-without-considering