Greedy Search (Greedy Search) Algoritm i C++- Förklaring, exempel och kod

Algoritmen Greedy Search är ett problemlösningssätt som alltid väljer det bästa tillgängliga alternativet vid varje steg utan att ta hänsyn till beslutets långsiktiga inverkan. Även om det inte garanterar att hitta den globalt optimala lösningen, fungerar den här metoden ofta snabbt och är enkel att implementera.

Hur det fungerar

1. Initiering: Börja med en tom eller initial lösning.
2. Lokalt optimalt val: Vid varje steg, välj det lokalt optimala valet baserat på den objektiva funktionen eller definierade kriterier.
3. Använd val: Använd det optimala valet på den aktuella lösningen.
4. Upprepa: Upprepa steg 2 till 4 tills inget bättre lokalt val kan göras.

Exempel: Knapsack Problem

Tänk på Knapsack Problem, där vi har en ryggsäck med en maxvikt och en lista över föremål med vikter och värden. Målet är att välja föremål för att maximera det totala värdet i ryggsäcken. En girig sökningsmetod för detta problem är att välja artiklar baserat på det högsta värde-till-vikt-förhållandet.

Kodexempel 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 det här exemplet använder vi Greedy Search-metoden för att lösa Knapsack Problem. Vi sorterar föremålen utifrån det fallande förhållandet mellan värde och vikt och väljer ut föremål med det högsta förhållandet som fortfarande ryms inom ryggsäckens viktgräns.