Algoritmul Greedy Search (Greedy Search) în C++- Explicație, Exemplu și Cod

Algoritmul Greedy Search este o abordare de rezolvare a problemelor care alege întotdeauna cea mai bună opțiune disponibilă la fiecare pas, fără a lua în considerare impactul pe termen lung al deciziei. Deși nu garantează găsirea soluției optime la nivel global, această metodă funcționează adesea rapid și este ușor de implementat.

Cum functioneaza

1. Inițializare: Începeți cu o soluție goală sau inițială.
2. Alegerea optimă locală: la fiecare pas, alegeți alegerea optimă locală pe baza funcției obiective sau a criteriilor definite.
3. Aplicați alegerea: Aplicați alegerea optimă soluției curente.
4. Repetați: repetați pașii de la 2 la 4 până când nu se poate face o alegere locală mai bună.

Exemplu: Knapsack Problem

Luați în considerare Knapsack Problem, unde avem un rucsac cu o greutate maximă și o listă de articole cu greutăți și valori. Scopul este de a selecta articole pentru a maximiza valoarea totală din rucsac. O abordare Greedy Search pentru această problemă este de a selecta articole pe baza celui mai mare raport valoare-greutate.

Exemplu de cod în 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;  
}  

În acest exemplu, folosim abordarea Greedy Search pentru a rezolva problema Knapsack Problem. Sortăm articolele în funcție de raportul descendent valoare-greutate și selectăm articolele cu cel mai mare raport care încă se încadrează în limita de greutate a rucsacului.