લોભી શોધ અલ્ગોરિધમ એ સમસ્યાનું નિરાકરણ કરવાનો અભિગમ છે જે નિર્ણયની લાંબા ગાળાની અસરને ધ્યાનમાં લીધા વિના હંમેશા દરેક પગલા પર શ્રેષ્ઠ ઉપલબ્ધ વિકલ્પ પસંદ કરે છે. જ્યારે તે વૈશ્વિક સ્તરે શ્રેષ્ઠ ઉકેલ શોધવાની બાંયધરી આપતું નથી, આ પદ્ધતિ ઘણીવાર ઝડપથી કામ કરે છે અને અમલમાં મૂકવા માટે સીધી છે.
તે કેવી રીતે કામ કરે છે
- પ્રારંભ: ખાલી અથવા પ્રારંભિક ઉકેલ સાથે પ્રારંભ કરો.
- સ્થાનિક શ્રેષ્ઠ પસંદગી: દરેક પગલા પર, ઉદ્દેશ્ય કાર્ય અથવા નિર્ધારિત માપદંડના આધારે સ્થાનિક રીતે શ્રેષ્ઠ પસંદગી પસંદ કરો.
- પસંદગી લાગુ કરો: વર્તમાન ઉકેલ માટે શ્રેષ્ઠ પસંદગી લાગુ કરો.
- પુનરાવર્તન કરો: જ્યાં સુધી કોઈ સારી સ્થાનિક પસંદગી ન કરી શકાય ત્યાં સુધી પગલાં 2 થી 4 દ્વારા પુનરાવર્તન કરો.
ઉદાહરણ: Knapsack Problem
ધ્યાનમાં લો Knapsack Problem, જ્યાં અમારી પાસે મહત્તમ વજન અને વજન અને મૂલ્યો સાથેની વસ્તુઓની સૂચિ છે. ધ્યેય નેપસેકમાં કુલ મૂલ્ય વધારવા માટે વસ્તુઓ પસંદ કરવાનું છે. આ સમસ્યા માટે લોભી શોધનો અભિગમ સૌથી વધુ મૂલ્ય-થી-વજન ગુણોત્તરના આધારે વસ્તુઓ પસંદ કરવાનો છે.
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;
}
આ ઉદાહરણમાં, અમે હલ કરવા માટે લોભી શોધ અભિગમનો ઉપયોગ કરીએ છીએ Knapsack Problem. અમે ઉતરતા મૂલ્ય-થી-વજન ગુણોત્તરના આધારે વસ્તુઓને સૉર્ટ કરીએ છીએ અને ઉચ્ચતમ ગુણોત્તર સાથે આઇટમ પસંદ કરીએ છીએ જે હજી પણ નેપસેકની વજન મર્યાદામાં બંધબેસે છે.