2차원 평면상에 n 개의 점이 주어져 있을 때,

어느 한 점부터 시작하여 모든 점을 한 번만 방문한 다음,

다시 그 점으로 돌아오는 가장 짧은 사이클(closed cycle)을 찾는 문제(이를 판매원 여행 문제(Travel Salesman Problem)이라 한다.)는

잘 알려진 NP-hard 문제로서 다항 시간(Polynomial time)내에 이 문제를 해결하는 알고리즘은 아직 존재 하지 않는다.

그러나, 이 문제를 다음과 같이 제한을 가하여 단순화하면 다항시간에 해결될 수 있음이 알려져 있다.

즉, 가장 왼쪽점부터 시작하여 x-좌표값이 증가하는 순서로 점을 방문하여 가장 오른쪽 점까지 도달한 다음,

다시 그 점부터 가장 왼쪽 점까지 x-좌표값이 감소하는 정렬의 순서대로 방문하는 가장 짧은 사이클을 찾는 것이다.

이러한 사이클을 Bitonic Cycle 이라고 부른다.

위 두 그림 중 위의 그림은 일반적인 TSP의 최적해이며, 아래의 그림은 Bitonic Cycle 이다.

TSP cycle 는 bitonic cycle 보다 전체길이가 더 짧거나 같다.

n 개의 점이 임의의 순서로 주어졌을 때 (단, 같은 x-좌표를 갖는 점들이 없다고 가정한다),

이의 bitonic cycle 을 다항시간에 구하는 프로그램을 작성하라.

Bitonic timer 1초 memory 64MB

Bitonic 1초 64MB