[알고리즘] 매개 변수 탐색 ( Paramatric Search )

 

◇  설명

  :  최적화 문제를 결정 문제로 바꾼 뒤, 이것을 이분법( 이진 탐색( Binary Search ) )을 이용해 해결하는 방법

  -  최적화 문제 ( Optimization Problem )
    :  문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 ‘좋은’ 답을 찾아내는 문제
     ( 완전 탐색( brute-force )이 최적화 문제를 푸는 가장 직관적 방법 )

  -  결정 문제 ( Decision Problem )
    :  예 혹은 아니오 형태의 답만이 나오는 문제 ( ‘답 x가 존재하는가?’ 대신 ‘x 또는 그보다 좋은 답이 있는가?’ )

  -  최적화 문제의 반환 값은 대개 실수나 정수이므로 답의 경우의 수가 무한한 데에 반해, 결정 문제는 두 가지 답만이 있을 수 있음

  -  최적화 문제 결정 문제로 바꾸기 레시피
    1.  ‘가장 좋은 답은 무엇인가?’ 라는 최적화 문제를 ‘x 혹은 그보다 좋은 답이 있는가?’ 라는 결정 문제 형태로 바꿈
    2.  결정 문제를 쉽게 풀 수 있는 방법이 있는지 찾아보기
    3.  결정 문제를 내부적으로 이용하는 이분법 알고리즘 작성

 

◇  예시

ex)  여행하는 외판원 문제
 -  최적화 문제
   :  그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환
 -  결정 문제
   :  그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오면서 길이가 x 이하인 경로의 존재 여부를 반환

ex)  DARPA Grand Challenge 
   ( 도로에 n개의 카메라를 설치하려 하는데, 설치할 수 있는 곳이 m군데로 제한됨.
     그 중 n군데에 설치하여 가장 가까운 두 카메라 사이의 간격을 최대화 하는 문제 )
 -  최적화 문제  =>  optimize( locations, cameras )
   :  카메라를 설치할 수 있는 위치와 카메라의 수가 주어질 때, 카메라 간 최소 간격의 최대치
    ( 카메라를 설치할 수 있는 방법은 여러 가지 인데, 그 중 최소 간격을 가장 크게 하는 방법을 찾으려는 것이므로 )
-  결정 문제  =>  decision( locations, cameras, gap )
   :  카메라를 설치할 수 있는 위치와 카메라의 수가 주어질 때, 이들을 적절히 배치해 모든 카메라의 간격이
      gap 이상이 되도록 하는 방법이 있는가?

 

◇  코드

  ex)  DARPA Grand Challenge

public class ParameticSearch {
	
	static boolean decision( double[] location, int cameras, double gap ) {
		double limit = -1; 	// 카메라를 설치 할 수 있는 최소 간격
		int installed = 0;
		for( int i = 0; i < location.length; ++i ) {
			if( limit <= location[i] ) {
				++installed;
				limit = location[i] + gap;
			}
		}
		return installed >= cameras; 
	}
	
	static double optimize( double[] location, int cameras ) {
		double low = 0, high = 241;
		for( int i = 0; i < 100; ++i ) {
			double mid = ( low + high ) / 2.0;
			if( decision( location, cameras, mid ) )  
				low = mid;
			else
				high = mid;
		}
		return low;
	}

	public static void main(String[] args) {

		double locations[] = { 0, 70, 90, 120, 200, 210, 220 };
		//Arrays.sort( locations );
		System.out.println( optimize( locations, 4 ) );
	}
}

 

-  이분법의 함정
    -  문제의 답은 유한함. 항상 입력으로 주어진 두 장소 간의 거리이기 때문에, 존재할 수 있는 답은 최대 (n-1)n / 2 가지 밖에 없음.
    -  하지만 이렇게 탐색의 범위가 유한해지면 이분법은 수치적 안정성을 잃어버리게 됨
    -  고정된 수의 후보만을 탐색하는 이분법에서는 수치적 오차가 생길 경우 후보 값이 바뀌기 때문에 오차가 커질 수 있음

-  다른 해법
    -  m개의 위치 중 n개를 선택해 카메라를 설치하는 문제를 n조각으로 쪼개, 각 조각마다 어느 위치에 카메라를 설치할지 정한다고 하자
    -  재귀 호출 알고리즘 -- 메모이제이션
    -  동적 계획법

 

◇  출처  :  알고리즘 문제 해결 전략 ( 구종만 )