Grådig søkealgoritme (Greedy Search) i C++- Forklaring, eksempel og kode

Greedy Search-algoritmen er en problemløsende tilnærming som alltid velger det beste tilgjengelige alternativet ved hvert trinn uten å ta hensyn til den langsiktige konsekvensen av beslutningen. Selv om det ikke garanterer å finne den globalt optimale løsningen, fungerer denne metoden ofte raskt og er enkel å implementere.

Hvordan det fungerer

1. Initialisering: Start med en tom eller initial løsning.
2. Lokalt optimalt valg: På hvert trinn velger du det lokalt optimale valget basert på målfunksjonen eller definerte kriterier.
3. Bruk valg: Bruk det optimale valget på gjeldende løsning.
4. Gjenta: Gjenta trinn 2 til 4 til du ikke kan gjøre noe bedre lokalt valg.

Eksempel: Knapsack Problem

Tenk på Knapsack Problem, hvor vi har en ryggsekk med maksimal vekt og en liste over varer med vekter og verdier. Målet er å velge varer for å maksimere den totale verdien i ryggsekken. En Greedy Search-tilnærming for dette problemet er å velge varer basert på det høyeste verdi-til-vekt-forholdet.

Kodeeksempel i 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;  
}  

I dette eksemplet bruker vi Greedy Search-tilnærmingen for å løse Knapsack Problem. Vi sorterer varene basert på synkende verdi-til-vekt-forhold og velger varer med det høyeste forholdet som fortsatt passer innenfor ryggsekkens vektgrense.