Bitonic Tour
Bitonic Tour란 Traveling Salesperson Problem(TSP)의 특수한 경우중 하나이다. TSP에 제약을 걸어서 P로 풀 수 있게 한다고도 볼 수 있다. 편의를 위해 점들을 \(p_{0}, p_{1}, \cdots, p_{n-1}\) 이라고 하자. \(p_{0}\)에서 출발하여, 번호가 증가하는 순서대로 몇 개의 점들을 방문하고, \(p_{n-1}\)에 도달하면, 이번에는 번호가 감소하는 순서대로 몇 개의 점들을 방문하여 \(p_{0}\)으로 되돌아오는 사이클을 생각하자. (단, 갈 때와 올 때 방문하는 정점들은 양 끝 점(\(p_{0}, p_{n-1}\))을 제외하고는 겹쳐서는 안 되며, 모든 정점들은 갈 때와 올 때 중 한 번은 방문해야 한다.) 이 사이클의 길이의 최솟값을 ..
2013. 11. 24. 19:15