Algoritem pohlepnega iskanja (Greedy Search) v C++ – razlaga, primer in koda

Algoritem Greedy Search je pristop k reševanju problemov, ki vedno izbere najboljšo razpoložljivo možnost na vsakem koraku brez upoštevanja dolgoročnega vpliva odločitve. Čeprav ne zagotavlja iskanja globalno optimalne rešitve, ta metoda pogosto deluje hitro in jo je enostavno implementirati.

Kako deluje

1. Inicializacija: Začnite s prazno ali začetno raztopino.
2. Lokalna optimalna izbira: Na vsakem koraku izberite lokalno optimalno izbiro na podlagi ciljne funkcije ali definiranih kriterijev.
3. Uporabi izbiro: Uporabi optimalno izbiro za trenutno rešitev.
4. Ponavljajte: Ponavljajte korake od 2 do 4, dokler ni mogoče izbrati boljše lokalne izbire.

primer: Knapsack Problem

Razmislite o Knapsack Problem, kjer imamo nahrbtnik z največjo težo in seznam predmetov z utežmi in vrednostmi. Cilj je izbrati predmete, ki bodo povečali skupno vrednost v nahrbtniku. Pristop Greedy Search za to težavo je izbira elementov na podlagi najvišjega razmerja med vrednostjo in težo.

Primer kode v 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;  
}  

V tem primeru uporabljamo pristop Greedy Search za rešitev Knapsack Problem. Predmete razvrstimo po padajočem razmerju med vrednostjo in težo in izberemo predmete z najvišjim razmerjem, ki še ustrezajo omejitvi teže nahrbtnika.