close

C++의 Greedy 검색 (Greedy Search) 알고리즘- 설명, 예제 및 코드

Greedy Search 알고리즘은 결정의 장기적인 영향을 고려하지 않고 항상 각 단계에서 사용 가능한 최상의 옵션을 선택하는 문제 해결 방식입니다. 전역적으로 최적의 솔루션을 찾는 것을 보장하지는 않지만 이 방법은 종종 빠르게 작동하고 구현하기 쉽습니다.

작동 방식

  1. 초기화: 비어 있거나 초기 솔루션으로 시작합니다.
  2. 로컬 최적 선택: 각 단계에서 목적 함수 또는 정의된 기준을 기반으로 로컬 최적 선택을 선택합니다.
  3. 선택 적용: 현재 솔루션에 최적의 선택을 적용합니다.
  4. 반복: 더 나은 로컬 선택을 할 수 없을 때까지 2-4단계를 반복합니다.

예: Knapsack Problem

Knapsack Problem 최대 무게가 있는 배낭과 무게와 값이 있는 항목 목록이 있는 를 고려하십시오. 목표는 배낭의 총 가치를 최대화하는 항목을 선택하는 것입니다. 이 문제에 대한 Greedy Search 접근 방식은 가장 높은 가치 대 무게 비율을 기준으로 항목을 선택하는 것입니다.

C++의 코드 예제 

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
struct Item {  
    int weight;  
    int value;  
};  
  
bool compare(Item a, Item b) {  
    double ratioA =(double)a.value / a.weight;  
    double ratioB =(double)b.value / b.weight;  
    return ratioA > ratioB;  
}  
  
double greedyKnapsack(int maxWeight, std::vector<Item>& items) {  
    double totalValue = 0.0;  
  
    std::sort(items.begin(), items.end(), compare);  
  
    for(const Item& item: items) {  
        if(maxWeight >= item.weight) {  
            totalValue += item.value;  
            maxWeight -= item.weight;  
        } else {  
            totalValue +=(double)maxWeight / item.weight * item.value;  
            break;  
        }  
    }  
  
    return totalValue;  
}  
  
int main() {  
    int maxWeight = 10;  
    std::vector<Item> items = {{2, 6}, {5, 12}, {3, 8}, {7, 14}, {4, 10}};  
    double maxValue = greedyKnapsack(maxWeight, items);  
  
    std::cout << "Max value in knapsack: " << maxValue << std::endl;  
  
    return 0;  
}

이 예제에서는 Greedy Search 접근 방식을 사용하여 Knapsack Problem. 가치 대 무게 비율이 내림차순으로 항목을 정렬하고 배낭의 무게 제한에 맞는 가장 높은 비율의 항목을 선택합니다.