farthest insertion

[1. 개요]

TSP 에서 N (노드) 개수가 커질 수록 완전탐색으로는 현실적인 시간 안에서 해결이 불가능 하다.

따라서 최적해를 구하기 위한 휴리스틱 알고리즘 중 하나.

• Nearest insertion
• Cheapest insertion
• 등 이 더 있음.

farthest insertion 알고리즘은 기본적으로 가장 멀리 있는 방문지를 먼저 선택하고,

이 방문지 사이에 그 다음으로 멀리 있는 방문지를 삽입 함 으로서 전체 방문 순서를 결정한다.

 

물론, best solution 이 아닐 수 있다.

그러나, 현실적인 시간 안에서 optimal solution 을 낼 수 있는 방법 중 하나이다.

---

[2. 알고리즘]

일단, 모든 정점 간에 소요되는 비용이 있는 테이블을 D 라 정의하고,

D[S][T] 는 S->T 로 가는 비용이라 하면

1. 모든 쌍 중에서 가장 비용이 큰 S 와 T 를 먼저 선택한다.
   # 탐색 과정 중 완성 된 방문 순서를 tour 라고 명명,
2. S 와 T 사이에 가장 멀리 있는 노드 (C) 를 선택하여 이 사이에 삽입한다.
   # 현재 tour : S -> C -> T
   # 사실 이 과정은 아래 3,4,5 와 같은 맥락이다.
3. S 와 C 사이에 아직 tour 에 속하지 않은 노드 중,
   전체 tour 의 비용을 가장 적게 증가 시키는 어떤 노드(A) 를 선택한다.
4. C 와 T 사이에 아직 tour 에 속하지 않은 노드 중, 
   전체 tour 의 비용을 가장 적게 증가 시키는 어떤 노드 (B) 를 선택한다.
5. A 와 B 중 전체 tour 의 비용을 가장 높게 증가 시키는 노드를 선택하여 tour 에 삽입한다.
   # A 가 선택 된다면, S -> A -> C -> T
   # B 가 선택 된다면, S -> C -> B -> T
   # 가장 멀리 있는 작업을 먼저 tour 에 속하게 한다는 원칙(?) 이라고 보면 되나,
6. 이러한 작업을 모든 노드가 tour 에 속할 때 까지 반복한다.
   # 현재 tour 가 S -> A -> C ->T 일 때,
   # S-A 에서 어떤 노드 찾고, A-C 에서 찾고, C-T 에서 찾고
   # 이 들 중, 조건에 맞는 노드를 해당 구간에 삽입하고, 
   # 이러한 과정을 계속 반복

시간복잡도는 O(N²) 이다.

• 완전탐색이 O(N!) 이므로 훨씬 빠르다.

---

[3. 고찰]

farthest insertion 이 구현된 몇가지 소스 코드를 살펴보다 약간 이해가 되지 않는 부분이 있었는데,

const auto dist_from = dist_table(*from_node, new_loc);
const auto dist_to = dist_table(new_loc, *to_node);

if (dist_from == INVALID_EDGE_DURATION || dist_to == INVALID_EDGE_DURATION)
    continue;

const auto trip_dist = dist_from + dist_to - dist_table(*from_node, *to_node);

if (trip_dist < min_trip_distance)
{
    min_trip_distance = trip_dist;
    next_insert_point_candidate = to_node;
}

 

from 과 to 사이에 어떤 노드를 삽입하여 전체 trip 을 최소로 증가시키는 부분을 찾는 곳에 대한 부분인데,

전체 trip 의 비용으로 따지는 것이 아니라, 증가 된 양을 가지고 최소 여부를 판단하는 것이다.

 

가령, 현재 tour 가  A->B->C 이고, A 와 B 사이에 넣을 어떤 노드(D)를 찾는 중이라고 했을 때,

새로운 tour 의 비용은 AD + DB + BC 가 될 것이다.

trip_dist 가 의미하는 바는

=> 증가 된 tour 의 비용 - 이전 tour 의 비용 이므로

=> AD+DB+BC - (AB+BC) = AD + DB - AB 가 된다.

 

아, 현재 총 비용은 그대로이고, 이 때 증가량이 가장 적으면 가장 적게 증가 하니까..

---

[4. ref]

• https://users.cs.cf.ac.uk/C.L.Mumford/howard/FarthestInsertion.html
• https://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP003__.HTM
• https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/trip/trip_farthest_insertion.hpp
•