12. 최적화 문제 결정 문제로 바꿔 풀기

12. 1 도입

  • 최적화 문제를 결정 문제로 바꿔 풀기(파라메트릭 서치): 유용한 디자인 원칙 중 하나, 최적화 문제를 결정 문제로 바꾼 뒤, 이를 이분법으로 해결하는 방법

    • 결정 문제(decision problem): yes, true or no, false 의 형태의 답만 나오는 문제들

    • 최적화 문제의 반환 값은 대개 실수 or 정수로 답이 무한한 데 반해, 결정 문제는 답이 두 가지만 존재

  • 최적화 문제와 결정 문제의 관계 1) 두 문제 형태가 똑같이 어려운 경우, 2) 최적화 문제가 더 여러운 경우

    • 결정 문제가 최적화 문제보다 어려울 수 없다.

    • 결정 문제 <= 최적화 문제 (Hardness)

    • 1
2
3
4
5

      fun optimize(graph: G): double {}

fun decision(graph: G, double: x) {
    return optimize(graph) <= x
}

12.2 최적화 문제와 결정 문제

  • decision() 은 “답 x가 존재하는가? (b)” 라는 질문 대신 "x 또는 그 보다 좋은 답이 있는가? (a)", 라는 질문에 대답한다.
  • (a) 같은 형태의 질문을 이용해, 최적화 문제를 푸는 쉬운 방법이 존재하기 때문에 두 개의 차이는 중요하다.
  • 최적화 문제를 결정 문제로 변형 하는 것은 더 쉽고 빠른 방법이 있기를 기대하기 때문이다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def decision(input, midValue) {
    # decision 판별 logic with midValue
    # ...
    return False
    or
    return True
}

def optimize(input) { # decsion() 을 호출한다.
  	start, end = 초기화, 초기화 
    
    # 이분법 사용
    while True:
        mid = (start + end) // 2
        if decision(input, mid): # 결정 문제 해결 함수 사용
            start = mid
        else:
            end = mid
    
    return start or end or something
}

12.3. 최적화 문제 결정 문제로 바꾸기(파라메트릭 서치) 레시피

  1. “가장 좋은 답은 무엇인가?” 라는 최적화 문제를 "x 혹은 그보다 좋은 답이 있는가?" 라는 결정 문제 형태로 변경
  2. 결정 문제를 쉽게 풀 수 있는 방법을 찾는다
  3. 결정 문제를 내부적으로 이용하는(decision 함수 호출) 이분법 알고리즘 (optimize 함수) 을 구현한다.

12.4, 12.5 캐나다 여행, CANADATRIP, 난이도: 중

  • 최적화 문제는 아니지만, 이 문제 또한 원래 문제를 결정 문제로 바꿀 수 있다.
  • “K번째 표지판의 위치는 어디인가” 라는 문제를 다음과 같이 바꾼다.
    • decision(x) = 시작점부터 x미터 지점까지 가면서 K개 이상의 표지판을 만날 수 있는가?
  • 중요: 우리가 원하는 답이 ‘D’라고 하면, ‘D’는 decision()이 True를 반환하는 첫 번째 지점이다.
    • 이전 부터, D-1까지 계속 False 이다가, D 이후부터 계속 True 라는 의미
    • decision(D-1) = false, decision(D) = True 여야 한다.
    • ..... / D-1 / D / D+1 /...
    • ... False / False / True / True ...

Reference