3차 검색

Ternary search

3차 검색 알고리즘은 단일 함수의 최소 또는 최대값을 찾기 위한 컴퓨터 과학 기술이다.3차 검색은 최소 또는 최대값이 도메인의 첫 번째 3분의 1에 있을 수 없거나 도메인의 마지막 3분의 1에 있을 수 없다고 결정한 후 나머지 3분의 2에 대해 반복한다.3차 검색은 분할 및 정복 알고리즘의 예다(검색 알고리즘 참조).

함수

최대 f(x)를 찾고 있으며 최대값이 A와 B 사이의 어딘가에 있다는 것을 알고 있다고 가정해 보십시오.알고리즘이 적용되려면 다음과 같은 값 x가 있어야 한다.

  • 모든 a,b에 대해, a ≤ a < b ≤ x, 우리는 f(a) < f(b)를 가지고 있다.
  • 모든 a,b에 대해, x ≤ a < b ≤ B, 우리는 f(a) > f(b)를 가지고 있다.

알고리즘.

f(x)를 어떤 간격[l; r]에서 단항 함수가 되게 한다.이2 세그먼트에서 l1 < m1 < m < r>의2 두 점을 취한다.그 다음 세 가지 가능성이 있다.

  • f(m1) < f(m2)>인 경우, 필요한 최대값은 왼쪽([l; m1]에 위치할 수 없다.그것은 [m1;r] 간격에서만 보는 것이 더 이상 타당하다는 것을 의미한다.
  • 만약 f(m1) > f(m2)이, 그 상황이 이전과 유사하다는 것을 대칭에 이르는 경우.이제 필요한 최대값이 오른쪽 [m2; r]에 있을 수 없으므로 세그먼트 [l2; m]으로 이동하십시오.
  • f(m1) = f(m2)이면 [m1; m]로2 검색해야 하지만, 이 경우는 (코드를 단순화하기 위해) 앞의 두 가지 중 하나에 기인할 수 있다.조만간 세그먼트의 길이가 미리 정해진 상수보다 약간 적을 것이며 공정을 중지할 수 있다.

선택12 지점 m 및 m:

  • m1 = l + (r-l)/3
  • m2 = r - (r-l)/3
런타임순서

재귀 알고리즘

반항하다 ternary_search(f, 남겨진, 맞다, 절대_영구) -> 둥둥 뜨다:     """좌우가 현재 한계임. 최대치는 그들 사이에 있다. """     만일 복근(맞다 - 남겨진) < 절대_영구:         돌아오다 (남겨진 + 맞다) / 2      좌/삼위 = (2*남겨진 + 맞다) / 3     right_three = (남겨진 + 2*맞다) / 3      만일 f(좌/삼위) < f(right_three):         돌아오다 ternary_search(f, 좌/삼위, 맞다, 절대_영구)     다른:         돌아오다 ternary_search(f, 남겨진, right_three, 절대_영구)

반복 알고리즘

반항하다 ternary_search(f, 남겨진, 맞다, 절대_영구) -> 둥둥 뜨다:     """[왼쪽, 오른쪽] 내에서 단일 함수 f()의 최대값 찾기 최소값을 찾으려면 if/else 문 또는 비교를 반대로 하십시오. """     하는 동안에 복근(맞다 - 남겨진) >= 절대_영구:         좌/삼위 = 남겨진 + (맞다 - 남겨진) / 3         right_three = 맞다 - (맞다 - 남겨진) / 3          만일 f(좌/삼위) < f(right_three):             맞다 = right_three         다른:             남겨진 = 좌/삼위       # 왼쪽과 오른쪽은 현재 한계치, 최대치는 그 사이      돌아오다 (남겨진 + 맞다) / 2

참고 항목

참조