파라메트릭 서치1 파라메트릭 서치 파라메트릭 서치(parametric search) 파라메트릭 서치란 최적화 문제를 결정 문제로 바꿔 이분 탐색을 이용해 해결하는 방법이다. 여기서 결정 문제란 예 혹은 아니오 형태의 답이 나오는 문제를 말한다. 예를 들어 외판원 문제를 최적화 문제와 결정 문제로 표현하면 아래와 같다. optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다. decision(G, \(x\)) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 길이가 \(x\)이상인 경로가 있는 있는가? 최적화 문제의 답은 보통 실수, 정수이므로 답의 경우의 수가 무한개이지만, 결정 문제의 답은 예 혹은 아니오 이므로 답의 경우의 수가 2개이다. 왜 결정문제로 바꿔.. 2022. 6. 8. 이전 1 다음