Chciwy (Greedy Search) algorytm wyszukiwania w C++- wyjaśnienie, przykład i kod

Algorytm Greedy Search to podejście do rozwiązywania problemów, które zawsze wybiera najlepszą dostępną opcję na każdym kroku, bez uwzględnienia długoterminowego wpływu decyzji. Chociaż nie gwarantuje to znalezienia globalnie optymalnego rozwiązania, metoda ta często działa szybko i jest łatwa do wdrożenia.

Jak to działa

1. Inicjalizacja: Zacznij od pustego lub początkowego rozwiązania.
2. Lokalny wybór optymalny: na każdym etapie wybierz lokalnie optymalny wybór w oparciu o funkcję celu lub zdefiniowane kryteria.
3. Zastosuj wybór: Zastosuj optymalny wybór do bieżącego rozwiązania.
4. Powtarzaj: powtarzaj kroki od 2 do 4, aż nie będzie można dokonać lepszego lokalnego wyboru.

Przykład: Knapsack Problem

Weźmy pod uwagę Knapsack Problem, gdzie mamy plecak z maksymalną wagą oraz listę przedmiotów z wagami i wartościami. Celem jest wybranie przedmiotów, aby zmaksymalizować całkowitą wartość w plecaku. Podejście Chciwego Wyszukiwania dla tego problemu polega na wybieraniu przedmiotów na podstawie najwyższego stosunku wartości do wagi.

Przykład kodu w 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;  
}  

W tym przykładzie używamy podejścia Greedy Search do rozwiązania problemu Knapsack Problem. Sortujemy przedmioty na podstawie malejącego stosunku wartości do wagi i wybieramy przedmioty o najwyższym stosunku, które nadal mieszczą się w limicie wagi plecaka.