Godus paieškos (Greedy Search) algoritmas C++ – paaiškinimas, pavyzdys ir kodas

„Greedy Search“ algoritmas yra problemų sprendimo būdas, kuris kiekviename žingsnyje visada pasirenka geriausią galimą variantą, neatsižvelgdamas į ilgalaikį sprendimo poveikį. Nors jis negarantuoja rasti visuotinai optimalų sprendimą, šis metodas dažnai veikia greitai ir yra nesudėtingas įgyvendinti.

Kaip tai veikia

1. Inicijavimas: pradėkite nuo tuščio arba pradinio sprendimo.
2. Vietinis optimalus pasirinkimas: kiekviename žingsnyje pasirinkite lokaliai optimalų pasirinkimą pagal tikslo funkciją arba apibrėžtus kriterijus.
3. Taikyti pasirinkimą: pritaikykite optimalų pasirinkimą esamam sprendimui.
4. Pakartokite: kartokite 2–4 veiksmus, kol nebebus geresnio vietos pasirinkimo.

Pavyzdys: Knapsack Problem

Apsvarstykite Knapsack Problem, kur turime kuprinę su didžiausiu svoriu ir daiktų sąrašą su svoriais ir vertėmis. Tikslas yra pasirinkti daiktus, kad maksimaliai padidintumėte bendrą kuprinės vertę. Greedy Search metodas šiai problemai spręsti yra pasirinkti elementus pagal didžiausią vertės ir svorio santykį.

Kodo pavyzdys 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;  
}  

Šiame pavyzdyje mes naudojame Greedy Search metodą, kad išspręstume Knapsack Problem. Prekes rūšiuojame pagal mažėjančią vertės ir svorio santykį ir parenkame daiktus su didžiausiu santykiu, kurie vis dar telpa kuprinės svorio ribose.