Ahne (Greedy Search) hakualgoritmi C++:ssa- selitys, esimerkki ja koodi

Greedy Search -algoritmi on ongelmanratkaisutapa, joka valitsee aina parhaan mahdollisen vaihtoehdon kussakin vaiheessa ottamatta huomioon päätöksen pitkän aikavälin vaikutusta. Vaikka se ei takaa maailmanlaajuisesti optimaalisen ratkaisun löytämistä, tämä menetelmä toimii usein nopeasti ja on yksinkertaista toteuttaa.

Kuinka se toimii

1. Alustus: Aloita tyhjällä tai alkuperäisellä ratkaisulla.
2. Paikallinen optimaalinen valinta: Valitse jokaisessa vaiheessa paikallisesti optimaalinen valinta tavoitefunktion tai määriteltyjen kriteerien perusteella.
3. Käytä valintaa: Käytä optimaalista valintaa nykyiseen ratkaisuun.
4. Toista: Toista vaiheet 2–4, kunnes parempaa paikallista valintaa ei voida tehdä.

Esimerkki: Knapsack Problem

Harkitse Knapsack Problem, jossa meillä on reppu maksimipainolla ja luettelo tavaroista painoineen ja arvoineen. Tavoitteena on valita kohteita maksimoimaan repun kokonaisarvo. Greedy Search lähestymistapa tähän ongelmaan on valita kohteet korkeimman arvo-painosuhteen perusteella.

Esimerkki koodista C++:ssa

#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;  
}  

Tässä esimerkissä käytämme Greedy Search -lähestymistapaa ratkaistaksemme Knapsack Problem. Lajittelemme tavarat laskevan arvo-painosuhteen perusteella ja valitsemme tuotteet, joiden suhde on korkein ja jotka silti mahtuvat repun painorajaan.