발견법(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
Author And Source
이 문제에 관하여(발견법(heuristic method)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@candyroom136/발견법heuristic-method저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)