Greedy Search (Greedy Search) Algorithm f'C++- Spjegazzjoni, Eżempju u Kodiċi

L-algoritmu Greedy Search huwa approċċ għas-soluzzjoni tal-problemi li dejjem jagħżel l-aħjar għażla disponibbli f'kull pass mingħajr ma jikkunsidra l-impatt fit-tul tad-deċiżjoni. Filwaqt li ma jiggarantixxix li tinstab l-aħjar soluzzjoni globalment, dan il-metodu ħafna drabi jaħdem malajr u huwa faċli biex jiġi implimentat.

Kif taħdem

1. Inizjalizzazzjoni: Ibda b'soluzzjoni vojta jew inizjali.
2. Għażla Ottimal Lokali: F'kull pass, agħżel l-għażla ottima lokalment ibbażata fuq il-funzjoni oġġettiva jew kriterji definiti.
3. Applika Għażla: Applika l-aħjar għażla għas-soluzzjoni attwali.
4. Irrepeti: Irrepeti l-passi 2 sa 4 sakemm ma tkun tista' ssir l-ebda għażla lokali aħjar.

Eżempju: Knapsack Problem

Ikkunsidra l- Knapsack Problem, fejn għandna xkora b'piż massimu u lista ta 'oġġetti b'piżijiet u valuri. L-għan huwa li jintgħażlu oġġetti biex jimmassimizzaw il-valur totali fil-knapsack. Approċċ Greedy Search għal din il-problema huwa li jintgħażlu oġġetti bbażati fuq l-ogħla proporzjon tal-valur għall-piż.

Eżempju ta' Kodiċi f'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;  
}  

F'dan l-eżempju, nużaw l-approċċ Greedy Search biex insolvu l- Knapsack Problem. Aħna issortja l-oġġetti bbażati fuq il-proporzjon dixxendenti tal-valur għall-piż u nagħżlu oġġetti bl-ogħla proporzjon li għadhom joqogħdu fil-limitu tal-piż tal-knapsack.