발견법

발견법(heuristic method)은 최선.최적의 답을 구하기에는 시간적.물적 조건을 좋지 못 할때 사용하는 방법으로 정확한 답을 구하리란 보장은 없지만 그에 가까운 답을 훨씬 짧은 시간내에 찾을 수 있는 방법입니다.

발견법중에는 탐욕법(greedy approach)이 있습니다. 탐욕법은 최선의 선택의 모음을 구하고 싶을 때 쓰는 방법으로 매 선택을 선택의 순간만 따졌을 때 최선의 선택을 하도록 하며 역추적하여 다른 선택지를 탐색하지는 않습니다. 한 번 선택하면 끝인 것입니다.

무식하게 풀기에서 앞서 보았던 배낭문제를 봅시다.

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

이 문제를 풀기위해서 상품들로 멱집합을 만들어 모든 가능한 상품의 조합들에 대해 이윤을 계산하는 방법을 적용했습니다. 하지만 상인이 시간이 얼마 없다고 하면 어떻게 해야 할까요? 그때 그때 가장 값어치 나가는 걸 배낭에 담고 보면 됩니다. 이렇게 나름대로의 기준으로 최선의 선택을 한 이후 돌이키지 않는 방법을 탐욕법이라고 합니다. 이를 이용하여 배낭문제를 풀어보면 다음과 같습니다.

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))

이러한 탐욕법은 가끔은 최적해를 구해내기도 합니다. 다음과 같은 문제를 봅시다.

전력이 연결되지 않은 여러 마을에 전력을 공급하고 싶습니다. 한 마을에 드디어 발전소가 생겼습니다. 다른 마을들에 전기를 공급하고 싶은데 전깃줄을 가장 적게 들여 전력을 공급하기 위해선 전깃줄을 어떻게 연결해야 할까요??

모든 마을에 전력이 공급될 때까지 전력이 공급되지 않은 마을과 전력이 공급되는 마을중 가장 가까운 두 마을을 골라 연결하면 됩니다.