Αλγόριθμος αναζήτησης Greedy (Greedy Search) σε C++- Επεξήγηση, Παράδειγμα και Κώδικας

Ο αλγόριθμος Greedy Search είναι μια προσέγγιση επίλυσης προβλημάτων που επιλέγει πάντα την καλύτερη διαθέσιμη επιλογή σε κάθε βήμα χωρίς να λαμβάνει υπόψη τον μακροπρόθεσμο αντίκτυπο της απόφασης. Αν και δεν εγγυάται την εύρεση της παγκόσμιας βέλτιστης λύσης, αυτή η μέθοδος συχνά λειτουργεί γρήγορα και είναι απλή στην εφαρμογή.

Πως δουλεύει

1. Αρχικοποίηση: Ξεκινήστε με μια άδεια ή αρχική λύση.
2. Τοπική βέλτιστη επιλογή: Σε κάθε βήμα, επιλέξτε την τοπικά βέλτιστη επιλογή με βάση την αντικειμενική συνάρτηση ή καθορισμένα κριτήρια.
3. Εφαρμογή επιλογής: Εφαρμόστε τη βέλτιστη επιλογή στην τρέχουσα λύση.
4. Επαναλάβετε: Επαναλάβετε τα βήματα 2 έως 4 έως ότου δεν μπορείτε να κάνετε καλύτερη τοπική επιλογή.

Παράδειγμα: Knapsack Problem

Σκεφτείτε το Knapsack Problem, όπου έχουμε ένα σακίδιο με μέγιστο βάρος και μια λίστα αντικειμένων με βάρη και τιμές. Ο στόχος είναι να επιλέξετε αντικείμενα για να μεγιστοποιήσετε τη συνολική αξία στο σακίδιο. Μια προσέγγιση Greedy Search για αυτό το πρόβλημα είναι η επιλογή στοιχείων με βάση την υψηλότερη αναλογία αξίας προς βάρος.

Παράδειγμα κώδικα σε 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;  
}  

Σε αυτό το παράδειγμα, χρησιμοποιούμε την προσέγγιση Greedy Search για να λύσουμε το πρόβλημα Knapsack Problem. Ταξινομούμε τα αντικείμενα με βάση την φθίνουσα αναλογία αξίας προς βάρος και επιλέγουμε αντικείμενα με την υψηλότερη αναλογία που εξακολουθούν να ταιριάζουν στο όριο βάρους του σακιδίου.