Mohó keresési (Greedy Search) algoritmus C++ nyelven – magyarázat, példa és kód

A Greedy Search algoritmus egy olyan problémamegoldó megközelítés, amely minden lépésnél mindig az elérhető legjobb lehetőséget választja anélkül, hogy figyelembe veszi a döntés hosszú távú hatását. Bár nem garantálja a globálisan optimális megoldás megtalálását, ez a módszer gyakran gyorsan működik, és egyszerűen megvalósítható.

Hogyan működik

1. Inicializálás: Kezdje üres vagy kezdeti megoldással.
2. Helyi optimális választás: Minden lépésben válassza ki a helyileg optimális választást a célfüggvény vagy a meghatározott kritériumok alapján.
3. Választás alkalmazása: Alkalmazza az optimális választást az aktuális megoldásra.
4. Ismételje meg: Ismételje meg a 2–4. lépéseket, amíg nem lehet jobb helyi választást tenni.

Példa: Knapsack Problem

Tekintsük a Knapsack Problem, ahol van egy hátizsákunk maximális súllyal és egy listánk a súlyokkal és értékekkel. A cél az, hogy olyan elemeket válasszunk ki, amelyek maximalizálják a hátizsák összértékét. A Greedy Search megközelítés erre a problémára az, hogy a tételeket a legmagasabb érték-súly arány alapján választják ki.

Kódpélda C++ nyelven

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

Ebben a példában a Greedy Search megközelítést használjuk a Knapsack Problem. A cikkeket a csökkenő érték-tömeg arány alapján rendezzük, és a legmagasabb arányú tételeket választjuk ki, amelyek még beleférnek a hátizsák súlyhatárába.