कृपया "पहाड़ी चढ़ाई" और "लालची" एल्गोरिदम के बीच का अंतर बताएं।"पहाड़ी चढ़ाई" और "लालची" एल्गोरिदम के बीच क्या अंतर है?
ऐसा लगता है कि दोनों समान हैं, और मुझे संदेह है कि "पहाड़ी चढ़ाई" एक एल्गोरिदम है; यह एक अनुकूलन प्रतीत होता है। क्या ये सही है?
हिल-क्लाइंबिंग और लालची एल्गोरिदम दोनों ही ह्यूरिस्टिक्स हैं जिनका उपयोग ऑप्टिमाइज़ेशन समस्याओं के लिए किया जा सकता है। अनुकूलन समस्या में, हम आमतौर पर समस्या तत्वों के कुछ इष्टतम संयोजन या ऑर्डरिंग की तलाश करते हैं। एक दिया संयोजन या आदेश एक समाधान है। किसी भी मामले में, अन्य समाधानों के मुकाबले इसकी तुलना करने के लिए एक समाधान का मूल्यांकन किया जा सकता है।
पहाड़ी चढ़ाई हेरिस्टिक, आप प्रारंभिक समाधान से शुरू करते हैं। एक या अधिक पड़ोसी समाधान उत्पन्न करें। सर्वश्रेष्ठ चुनें और तब तक जारी रखें जब तक कोई बेहतर पड़ोसी समाधान न हो। यह आम तौर पर एक समाधान पैदा करेगा। पहाड़ी चढ़ाई में, हमें यह जानने की जरूरत है कि समाधान का मूल्यांकन कैसे करें, और "पड़ोसी" कैसे उत्पन्न करें।
लालची हेरिस्टिक में, हमें समस्या के बारे में कुछ विशेष जानकारी जाननी चाहिए। एक लालची एल्गोरिदम एक एकल समाधान का उत्पादन करने के लिए जानकारी का उपयोग करता है।
एक अच्छा उदाहरण अनुकूलन समस्या का 0-1 knapsack है। इस समस्या में, एक निश्चित वजन सीमा के साथ एक knapsack है, और knapsack में रखने के लिए वस्तुओं का एक गुच्छा है। प्रत्येक आइटम में वजन और मूल्य होता है। वस्तु को सीमा के नीचे वजन रखते हुए, नापसंद में वस्तुओं के मूल्य को अधिकतम करना है।
एक लालची एल्गोरिदम उच्च घनत्व की वस्तुओं को उठाएगा और उन्हें तब तक रखेगा जब तक कि नापसंद भरा न हो जाए। उदाहरण के लिए, एक ईंट की तुलना में, हीरे का उच्च मूल्य और एक छोटा वजन होता है, इसलिए हम पहले हीरे को रखेंगे।
यहाँ जहां एक लालची एल्गोरिथ्म विफल हो जाएगा का एक उदाहरण है:
लालची एल्गोरिथ्म हीरा जाते थे और उसके बाद से किया जा, 1000 के एक मूल्य दे रही है लेकिन इष्टतम समाधान शामिल करने के लिए किया जाएगा 5 स्वर्ण सिक्के, मूल्य 1050 दे रहे हैं।
हिल-क्लाइंबिंग एल्गोरिदम प्रारंभिक समाधान उत्पन्न करेगा - केवल यादृच्छिक रूप से कुछ आइटम चुनें (सुनिश्चित करें कि वे वजन सीमा के नीचे हैं)। फिर समाधान का मूल्यांकन करें - यानी, मान निर्धारित करें। पड़ोसी समाधान उत्पन्न करें।उदाहरण के लिए, एक आइटम को दूसरे के लिए आदान-प्रदान करने का प्रयास करें (सुनिश्चित करें कि आप अभी भी वज़न सीमा के नीचे हैं)। यदि इसका उच्च मूल्य है, तो इस चयन का उपयोग करें और शुरू करें।
हिल चढ़ाई एक लालची एल्गोरिदम नहीं है।
हाँ आप सही हैं। हिल चढ़ाई एक सामान्य गणितीय अनुकूलन तकनीक है (देखें: http://en.wikipedia.org/wiki/Hill_climbing)। एक लालची एल्गोरिदम कोई एल्गोरिदम है जो उस समय देखे जाने वाले सर्वोत्तम विकल्प को चुनता है और इसे लेता है।
सिक्कों की संख्या को कम करने (कम से कम अमरीकी डालर के साथ) इसका एक उदाहरण बदल रहा है। जब तक आप आवश्यक राशि तक नहीं पहुंच जाते, तब तक आप सिक्का का सबसे ज्यादा मूल्यवान मूल्य लेते हैं, फिर अगले सबसे अधिकतम तक।
इस तरह, हिल चढ़ाई एक लालची एल्गोरिदम है।
आपका निष्कर्ष भ्रामक लगता है। आपके द्वारा वर्णित विशिष्ट लालची एल्गोरिदम धीरे-धीरे समाधान का निर्माण करता है, जबकि पहाड़ी चढ़ाई हेरिस्टिक एक स्थानीय ऑप्टिमा को लालची तक पहुंचता है। केवल अंतर यह है कि पहले व्यक्ति में लालची कदम में समाधान का निर्माण करना शामिल है, जबकि पहाड़ी चढ़ाई में लालची कदम में एक पड़ोसी (लालची स्थानीय खोज) का चयन करना शामिल है। हिल चढ़ाई एक लालची ह्युरिस्टिक है। यदि आप एक ह्युरिस्टिक से एल्गोरिदम को अलग करना चाहते हैं, तो मैं मिकोला के उत्तर को पढ़ने का सुझाव दूंगा, जो अधिक सटीक है। –