TSP 외판원 문제 2-Opt, 3-Opt(TSP Problem)

2-Opt 및 TSP 기본 개념

---

 

외판원 문제는 NP-Hard 문제로 유명하다, 모든 경로를 확인할 경우 최선의 방법으로 메모이제이션과 비트마스크를 통해서 풀 수 있다. 하지만, 노드의 수가 증가하면 모든 경로를 방문하는 것은 불가능하게 된다.

 

 

따라서, 노드의 수가 엄청 많아질 경우에는 정확한 해를 구하는 것이 불가능해진다. 이 경우에 생각할 수 있는 것이, 지역 탐색 알고리즘인 2-Opt이다. 2-Opt를 사용하기전에 출발점에서 모든 노드를 거쳐서 출발점으로 돌아오는 임의의 경로를 구한다.

 

 

 

구글 이미지 검색 참고

 

위의 그림을 떠올려 보자, 연결된 A와 B, C와 D를 잇는 방식을 변경해서 거리가 더 감소된다면, 해당 경로를 선택하는 것이 2-Opt의 기본이다. 2-Opt의 '2'는 2개의 연결된 선분을 변경한다는 의미이다. 이제 2-Opt로 변경되는 경로의 총 합을 구해보자.

 

 

 

변경되는 경로의 총 합 = (A-B, C-D)를 제외한 기존 경로의 합 + (A-C, B-D) - (A-B, C-D)

 

 

 

위의 식으로, 표현할 수 있다, (X-Y는 X에서 Y까지의 경로의 값을 의미한다)

 

 

 

변경되는 경로의 총 합이 기존 경로의 합보다 작게 된다면, 2-Opt가 성공적이라고 생각할 수 있다. 이 상태로 끝나면 안된다, 2-Opt가 진행되면, 경로가 변경되게 된다. A는 이제 C를 거쳐서 B로 갈 수 있는 것을 보면 된다.

 

 

 

즉 이제 경로는, AC....BD....A가 될 것이다. 기존의 AB...CD...A에서 B와 C가 변경됐다. 단순히 B와 C만 변경한 것이 아니라, B와 C를 잇는 사이에 있는 점들의 순서도  역전된 것이다. 따라서 B와 C를 포함한 경로를 역전시켜주는 것이 필요하다.

 

 

 

2-Opt의 순서를 정리해보자면,

 

 

1. 임의의 2개의 점 고르기(B, C)

 

 

2. 변경되는 경로의 총 합 계산하기

 

 

3. 합이 작아졌다면, B와 C를 연결하는 경로를 역전해서 경로를 갱신

 

 

 

 

3-Opt, K-Opt의 개념

---

 

tsp-basics.blogspot.com/2017/03/3-opt-move.html

3-opt move

 

 

위 페이지를 참고하도록 하자.

 

 

 

3-Opt에서 발생할 수 있는 가지수는 몇 가지일까? 단순히 2가지씩 조합을 만드는 것이 아니고, 특정 형태의 그래프가 되어야 한다. 3-Opt는 2-Opt의 확장이라고 생각하면 된다. 2-Opt를 적용하면 경로의 순서가 역전된다. 3-Opt에서 경로가 역전될 수 경우를 생각해보자.

 

 

 

 

구글 이미지 출처

 

 

(b), (c), (d)는 경로 하나씩 역전된 것을 의미한다. (e), (f), (g)는 경로가 두개 역전된 것을 의미한다. (h)는 경로 3개가 모두 역전된 것을 의미한다.

 

 

 

즉, 나타날 수 있는 가지수는 각 역전된 경로의 개수 조합을 의미한다. 따라서, 3-Opt일 경우에는, 1(기존) + 3C1 + 3C2 +3C3이므로 총 8가지가 된다.

 

 

 

2-Opt일 경우에 공식을 적용해보면, 2C1 + 2C2가 되어야 한다고 생각할 수 있다. 하지만, 직접 그려보면, 2C1은 똑같은 모양을 나타내고, 2C2는 원래와 동일하게 되므로 의미가 없다.

 

 

 

3-Opt의 경우에도, 경로가 변경되었을때 값이 기존 경로의 합보다 더 작으면 변경하도록 설정하면 된다. 3-Opt의 작성된 코드는 위의 링크를 추천한다.

 

 

 

이제 생각을 넓혀서, k-Opt에도 도달할 수 있다. k-Opt에서 발생할 수 있는 가지수는, 1 + kC1 + kC2 + ... + kCk 일 것이다.

 

 

 

k가 크더라도, 공식에 따라서 변경된 총 경로의 값을 확인하고, 값이 더 작아졌다면 관련 경로들을 역전시켜주면 된다.

 

 

 

SA(Simulated Annealing, 담금질 기법)

---

TSP 문제와 관련해서 담금질 기법을 아는대로 설명하려고 한다.

 

 

 

TSP 문제에서 k-Opt는 Global Optimal(전역적 최적해)를 찾는다고 보장할 수 없다. Local Optimal(지역적 최적해)을 구하는 알고리즘으로 소개된다. 

 

 

 

k-Opt를 하다가, Local Optimal에 빠져버리면 k-Opt를 아무리 해도 값의 변화가 없을 수 있다. 이럴때, 담금질 기법으로 Local Optimal 벗어날 수 있도록 해준다.

 

 

 

Local Optimal을 벗어나기 위해서, k-Opt를 하면서 값을 작게하는 것이 아니라, 일정 시기에는 기존의 경로의 값보다 커도 경로를 변경할 수 있도록 한다.