분기한정법 : 답의 법위를 좁히며 풀기

김정빈·2021년 6월 3일
0

문제해결전략

목록 보기
8/8

분기한정법은 최단 경로탐색, 이윤 최대화등 최적화 문제(optimization problem)에서 최적화 문제에서 구하려는 것이 선택의 모음일 때 선택의 분기중 나쁜 선택을 미리 한정하여 프로그램의 시간성능을 높이는 방법입니다.

나쁜 선택은 어떻게 알 수 있을까요? 상한과 하한을 통해 알 수 있습니다. 상한(upper bound)는 값의 최대치를 한정하는 것이고, 하한(lower bound)는 값의 최소치를 한정하는 것입니다.

하한과 상한은 최적해를 바로 구하는 것보다는 구하기 좀더 쉽습니다. 최적의 이윤을 구하는 것은 어렵지만 나름대로의 기준으로 큰 이윤을 구하는 것은 그리 어렵지 않습니다. 적당하다 생각하는 기준으로 하한과 상한을 구해 선택을 할 때 하한보다는 크게 상한보다는 작게 선택을 해나가는 방법입니다.

문제해결전략 시리즈중 무식하게 풀기에서 나온 문제를 분기한정법으로 해결해봅시다.

한 상인이 상품을 배낭에 담아 팔려고 한다. 각 상품에는 무게와 가격이 존재합니다. 배낭은 무게 제한이 있습니다. 배낭에 담은 상품들의 총 가격을 제일 크게 하려면 어떤 상품을 골라야 할까?

하한은 발견법에서 예시로 들었던 배낭문제를 탐욕법으로 해결했던 방법으로 구할 수 있습니다.
상한은 어떻게 할 까요? 만약 모든 상품이 가루로 되어 있다면 상품의 일부만을 배낭에 담을 수 있을 것입니다. 그렇다면 가치/무게 비율이 가장 높은 상품부터 가방에 가득 찰 때까지 담으면 될 것입니다.

자바스크립트로 구현하면 다음과 같습니다.

function backpackPouder(items, maxWeight){                  //items는 훔칠 수 있는 물건들의 이름, 가치, 무게를 배열로 저장한 것들을 요소로 갖는 배열, maxWeight는 가방의 무게제한
    let bagWeight=0;
    let bagItems=[];
    let bagValue=0;

    items.sort((before,after)=>(after[1]/after[2]-before[1]/before[2]));       //items를 가치/무게순으로 내림차순으로 배열했다.
    for(let item of items){                                 //items의 item들을 0번째 인덱스부터 무게제한에 걸리지 않을 만큼 bagItems에 push합니다.
        if(bagWeight+item[2]<=maxWeight){
            bagWeight=bagWeight+item[2]
            bagItems.push(item.slice());
            bagValue=bagValue+item[1];
        }else{
            if(maxWeight===bagWeight){
                break;
            }else{
                bagItems.push(item.slice());
                bagValue=bagValue+(maxWeight-bagWeight)*item[1]/item[2]
                bagWeight=maxWeight;
                
            }
        }
    }
    return {bagItems,bagValue};                                        //bagItems,bagValue를 리턴합니다.
}

let fruits=[['apple',10,10],['banana',5,7],['orange',8,5]]; //간단한 test 코드입니다. 결과값은 apple, orange, (banana일부)가 가방에 담긴것을 나타내는 배열입니다.
let maxWeight=19;

console.log(backpackPouder(fruits,maxWeight))
	

가령 물건들과 배낭의 상황이 다음과 같다고 합시다.

위에서 말했던 방법으로 하한과 상한을 구하면 39와 52(정확히는52.6666이지만 구해야할 답이 정수인것이 자명하므로)가 나옵니다.

위 사진에서 볼 수 있는 것처럼 6개의 상품에 대한 배낭문제는 5개의 상품을 취급하는 부분 문제 두개로 나눌 수 있습니다. 만약 부분문제 두개중 하나의 하한이 다른 문제의 상한보다 크다면 다른 문제는 고려하지 않습니다. 이 번에는 둘다 고려해야합니다.
왼쪽과 오른쪽 부분문제를 다시 부분문제로 나누면 다음과 같습니다.

A를 선택하고 B를 제거한 부분문제의 하한은 나머지 세개의 부분문제의 상한보다 큽니다. 고로 나머지 세개는 고려하지 않습니다. 그리고 A를 선택하고 B를 제거한 부분문제의 상한과 하한은 같습니다. 즉 최적해가 두개의 사이에 있는데 상한과 하한이 같으므로 최적해가 49라는 것을 알 수 있습니다.

분기한정법의 원리를 정리하면 다음과 같습니다.
1. 문제를 부분 문제로 나눕니다.
2. 각 부분 문제의 상한과 하한을 구합니다.
3. 각 부분 문제의 상한과 하한을 비교하여 가장 최적의 부분 문제를 선택하여 1단계로 돌아갑니다.

참고자료
1. 한 권으로 그리는 컴퓨터 과학 로드맵, 지은이 : 블라드스톤 페헤이라 필루 옮긴이 : 박연오 107P-112P

0개의 댓글