Greedy Search (Greedy Search) Algoritme i C++- Forklaring, Eksempel og Kode

Greedy Search-algoritmen er en problemløsende tilgang, der altid vælger den bedst tilgængelige mulighed ved hvert trin uden at tage hensyn til beslutningens langsigtede virkning. Selvom det ikke garanterer at finde den globalt optimale løsning, fungerer denne metode ofte hurtigt og er ligetil at implementere.

Hvordan det virker

1. Initialisering: Start med en tom eller initial løsning.
2. Lokalt optimalt valg: På hvert trin skal du vælge det lokalt optimale valg baseret på den objektive funktion eller definerede kriterier.
3. Anvend valg: Anvend det optimale valg på den aktuelle løsning.
4. Gentag: Gentag gennem trin 2 til 4, indtil der ikke kan træffes et bedre lokalt valg.

Eksempel: Knapsack Problem

Overvej Knapsack Problem, hvor vi har en rygsæk med en maksimal vægt og en liste over varer med vægt og værdier. Målet er at vælge genstande for at maksimere den samlede værdi i rygsækken. En Greedy Search-tilgang til dette problem er at vælge varer baseret på det højeste værdi-til-vægt-forhold.

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 eksempel bruger vi Greedy Search-tilgangen til at løse Knapsack Problem. Vi sorterer varerne ud fra det faldende værdi-til-vægt-forhold og udvælger varer med det højeste forhold, som stadig passer inden for rygsækkens vægtgrænse.