옛날에 후배들을 위해 작성한 글인 관계로 경어체가 아니네요. 양해 부탁드립니다~ ^^
TernarySearch (터너리 서치라고 읽는다) 는, BinarySearch 와 비슷한 검색 알고리즘이다. 사실 BinarySearch 는
정렬된 상태의, 임의 접근이 가능한 수열에서 원소를 찾아내기 위한 알고리즘으로 많이 일컬어지기 때문에, 정확하게는 BisectionMethod
와 비슷한 검색 기법이라고 할 수 있다.
기본 개념
TernarySearch 는 어떤 연속적인 unimodal function f(x) 의 최대값, 혹은 최소값
(최적해 라고 한다) 을 찾는 것을 목표로 한다. 여기서는 최대값을 갖는 함수의 최대값을 찾는 것만을 대상으로 해 이야기하자. 만약 최소값을
갖는 함수의 최소값을 찾고 싶다면, 정확히 반대로 하면 된다.
unimodal 함수란 한 개의 지역 극대점만을 갖는 함수를 의미한다. 쉽게 이해하자면, 극대점에 이르기까지는 단조 증가하고, 그 후부터는 단조
감소하는 함수를 의미한다. 예를 들면 다음과 같이 생긴 함수를 들 수 있다.

단, 다음과 같은 제약이 있다.

• 수직선이나 수평선은 있을 수 없다: 수직선은 함수의 정의에 어긋나므로 안 되고, 수평선은 단조 증가/단조 감소라는 조건에 어긋나므로 안 된다.
• 지역 극대는 하나만 있어야 한다. 이런 지역 극대를 피크(peak) 라고 부르는데, peak 는 양쪽 옆의 점이 모두 자기 자신보다 작아야 한다. (주: 위 그림에 오타가 있습니다: 지역 극소가 아니라 극대라고 해야 하지요 ^^;;;) 이런 함수의 최적해를 구하는 것은 LocalSearch 로도 가능할 거라고 생각하겠지만, TernarySearch 는 전체 탐색 범위가 한번에 2/3 으로 줄어들기 때문에 로컬 서치보다 훨씬 빨리 수렴하고, 함수가 수렴했음을 판단하는 것도 간단한 편이다. 접근 방법 TernarySearch 는 답의 범위 안에서 해당 함수가 unimodal 임을 루프불변조건으로 유지하며, 종료 조건이 만족될 때까지 루프를 반복하며 답의 범위 [left, right] 를 줄여간다. 루프의 각 iteration 에서, 두 개의 값 a = (left*2 + right) / 3 과 b = (left + right*2) / 3 에서의 함수 값을 샘플링한다. 이때, f(a) 와 f(b) 에 대한 값을 비교하자. a. 만약 f(a) < f(b) 라면 (그림과 같이)
• 주어진 함수는 unimodal 이므로 f(a) < f(b) 인 경우, [left, a] 구간 안에 f(b) 보다 큰 값이 없음은 자명하다.
• 그러므로, left = a 를 도입하여 구간을 2/3 으로 줄일 수 있다. b. 만약 f(a) > f(b) 라면
• 주어진 함수는 unimodal 이므로 f(a) > f(b) 인 경우, [b, right] 구간 안에 f(a) 보다 큰 값이 없음은 자명하다.
• 그러므로, right = b 를 도입하여 구간을 2/3 으로 줄일 수 있다. [left,right] 범위가 충분히 작아질 때까지 이를 반복하여 답을 찾는다.

샘플 코드

// [min,max] 구간에서 f(x) 가 최대인 x를 찾는다. 

double ternary(double min, double max, Function& f) 
{ 
  while(max - min > max * 1e-9) 
  { 
    double a = (min*2 + max) / 3.0; 
    double b = (min + max*2) / 3.0; 
    if(f(a) < f(b)) 
      min = a; 
    else 
      max = b; 
  } 
  return (min+max)*.5; 
}

유의할 점
위 예제 코드에서, 종료 조건이 max - min > 1e-9 가 아니라 max - min > max * 1e-9 인 것을 유의해서 보라. 예를 들어 max = 1e50, min = 1e40 이라고 하자. 종료조건을 max - min > 1e-9 로 하면 어떻게 될까? 숫자가 워낙 크기 때문에 실수연산의 오차로 아무리 반복해도 1e-9 이하로 차이가 줄어들지 않는 경우가 있는 경우가 생긴다. 그러므로, 이와 같은 경우에는 상대적인 크기로 종료 조건을 설정해 주면 된다.
이외에, 한번의 TernarySearch 로 프로그램이 종료되는 경우 그냥 무조건 200번 정도 루프를 반복해 주는 것도 좋은 방법이다. (2/3)^200 > 1e-32 이기 때문에, 200번 정도 루프를 돌고 나면 double 실수 범위 내에서 반드시 수렴하기 때문이다.