발견법(heuristic method)

발견법은 최적의 수를 엄밀하게 구하는 방법보다 충분히 좋은 수를 찾아내는데 초점을 두는 방법입니다. 일종의 차선책이라고 할 수 있습니다. 발견법 가운데 흔히 사용되는 방법은 탐욕법(greedy approach)입니다. 탐욕법은 선택의 순간마다 최선으로 보이는 선택을 합니다. 무엇이 최선의 선택인지의 기준은 프로그래머가 정합니다.

문제 하나를 예로 들어보겠습니다. 절도범이 제 집에 숨어들어와서 물건을 훔치려고 합니다. 하지만 절도범의 배낭에는 담아 갈 수 있는 무게에 한계가 있고 집에 머물러 있는 시간이 짧을수록 잡힐 확률도 줄어듭니다. 절도범은 배낭에 어떤 물건을 담아가야 좋을까요?

이 문제는 최적해를 구하려 한다면 시간복잡도가 O(2^n)인 NP 완전문제입니다. 그런데 절도범은 최적해를 구할 시간의 여유가 없습니다. 그리하여 나름대로의 기준으로 그때그때 최선의 선택을 해야합니다. 선택의 기준을 가치로 한다면 가장 값어치가 나가는 것부터 담으면 될 것입니다. 그게 아니라 무게당 가치로 한다면 무게당 가격이 제일 많이 나가는 것을 담으면 될 것입니다. 간단하게 값어치 순으로 담는다고 생각하고 javascript로 문제를 해결해보겠습니다.

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

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

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

console.log(greedyKnapsack(fruits,maxWeight))

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