[결정 문제] 최적화 문제를 결정문제로 바꿔 풀기

1. 결정 문제(decision problem)

 

결정 문제란 예 아니오 현태의 답만이 나오는 문제들을 가리킴.

 

최적화 문제의 반환 값은 답의 경우의 수가 무한한 데 반해, 결정 문제는 두가지 답만 있음.

 

그러므로 결정 문제가 최적화 문제보다 더 어렵거나 시간 복잡도가 더 클 일도 없다.

 

 

2. 결정 문제로 바꾸기

 

 어떤 문제에서 최대가 되는 x를 구하자고 하자

 

 이를 결정 문제로 바꾸는 것은 다음과 같다.

 

 y이상일때 문제가 해결되는지?

 

 이 결정 문제를 이분법을 사용하여 10번 100번 반복하면 결국 원래 문제인 x를 구할 수 있다.

 

3. 이분법의 함정

 

답이 가질 수 있는 가지수가 유한일 때

 

이분법은 수치적 안정성을 잃어버리게 된다.

 

최적화 문제는 아주 미세한 차이가 나더라도 답과 가까운 값을 반환하지만

 

결정 문제는 답이 true false 두가지 밖에 없으므로 그 미세한 차이 때문에 답이 완전 달라진다.

 

4, 최적화 문제 결중문제로 바꾸기 레시피

 

- "가장 좋은 답은 무엇인가?" 라는 최적화 문제를 "x 혹은 그보다 좋은 답이 있는가?" 라는 형태로 변형한다.

 

- 결정 문제를 쉽게 풀 수 있는 방법이 있는지 찾아본다.

 

- 결정 문제를 내부적으로 이용하는 이분법 알고리즘을 작성한다.

 

 

 

  

-알고리즘 문제해결전략 450p