लालची एल्गोरिदम आंशिक नैपसैक (fractional knapsack) के लिए क्यों काम करता है लेकिन 0/1 नैपसैक के लिए नहीं?

आंशिक नैपसैक में, वस्तुओं को विभाजित किया जा सकता है, इसलिए पहले उच्चतम मूल्य-प्रति-भार वाली वस्तु को लेना हमेशा सुरक्षित और सिद्ध रूप से इष्टतम होता है। 0/1 नैपसैक में, वस्तुएं अविभाज्य होती हैं, लालची विकल्प एक बेहतर संयोजन को रोक सकता है, और एक सटीक इष्टतम के लिए गतिशील प्रोग्रामिंग की आवश्यकता होती है।

आप कैसे सिद्ध करते हैं कि एक लालची एल्गोरिदम सही है?

दो मानक तकनीकें विनिमय तर्क (exchange argument) हैं, जो किसी भी इष्टतम समाधान को खराब किए बिना लालची में बदल देती हैं, और 'लालची आगे रहता है' तर्क, जो दर्शाता है कि लालची आंशिक समाधान हर कदम पर किसी भी अन्य की तुलना में कम से कम उतना ही अच्छा है। मैट्रोइड सिद्धांत एक सामान्य पर्याप्त शर्त प्रदान करता है।

लालची एल्गोरिदम (Greedy Algorithms)

लालची एल्गोरिदम (Greedy algorithms) वर्तमान चरण में सबसे अच्छा दिखने वाला विकल्प चुनकर वृद्धिशील रूप से एक समाधान का निर्माण करते हैं, और वे ठीक तभी सही होते हैं जब ऐसे स्थानीय रूप से इष्टतम विकल्प सिद्ध रूप से वैश्विक रूप से इष्टतम समाधान की ओर ले जाते हैं।

PaperMind से विषय खोजेंजल्द हीFind papers & topics

Tools & resources

स्लाइड डाउनलोड करें

Learn & explore

वीडियोजल्द ही

Definition

एक लालची एल्गोरिदम विकल्पों के अनुक्रम के माध्यम से एक समाधान का निर्माण करता है, प्रत्येक को कुछ स्थानीय मानदंड को अनुकूलित करने के लिए चुना जाता है, पहले के विकल्पों पर कभी भी दोबारा विचार नहीं किया जाता है; यह तभी सही होता है जब स्थानीय रूप से इष्टतम विकल्प वैश्विक रूप से इष्टतम परिणाम देते हैं।

Scope

यह विषय लालची प्रतिमान (greedy paradigm) को शामिल करता है: लालची-विकल्प गुण (greedy-choice property) और इष्टतम उपसंरचना (optimal substructure) जो इसे उचित ठहराते हैं, मानक प्रमाण तकनीकें (विनिमय तर्क (exchange arguments) और मैट्रोइड ढाँचा (matroid framework)), और हफमैन कोडिंग (Huffman coding), न्यूनतम स्पैनिंग ट्री (Kruskal और Prim), डाइकस्ट्रा का सबसे छोटा पथ (Dijkstra's shortest paths), और अंतराल शेड्यूलिंग (interval scheduling) सहित प्रामाणिक लालची एल्गोरिदम। यह तब भी संबोधित करता है जब लालची रणनीतियाँ सटीक तरीकों के बजाय केवल सन्निकटन अनुमानी (approximation heuristics) के रूप में कार्य करती हैं।

Core questions

लालची-विकल्प गुण (greedy-choice property) क्या है, और किसी दिए गए समस्या के लिए इसे कैसे सिद्ध किया जाता है?
एक विनिमय तर्क (exchange argument) कैसे दर्शाता है कि एक लालची विकल्प सुरक्षित है?
किन समस्याओं में मैट्रोइड संरचना (matroid structure) होती है जो लालची इष्टतमता (greedy optimality) की गारंटी देती है?
एक लालची विधि कब एक सटीक एल्गोरिदम के बजाय केवल एक सन्निकटन (approximation) होती है?
एक ही समस्या के लिए लालची एल्गोरिदम गतिशील प्रोग्रामिंग (dynamic programming) से कैसे तुलना करता है?

Key concepts

लालची-विकल्प गुण (greedy-choice property)
इष्टतम उपसंरचना (optimal substructure)
विनिमय तर्क (exchange argument)
मैट्रोइड्स (matroids)
हफमैन कोडिंग (Huffman coding)
न्यूनतम स्पैनिंग ट्री (minimum spanning tree)
अंतराल शेड्यूलिंग (interval scheduling)
आंशिक नैपसैक (fractional knapsack)

Key theories

लालची-विकल्प गुण (Greedy-choice property) और विनिमय तर्क (exchange arguments): एक समस्या एक लालची समाधान को स्वीकार करती है जब एक वैश्विक रूप से इष्टतम समाधान को हमेशा इष्टतमता के नुकसान के बिना लालची पहले विकल्प से सहमत होने के लिए संशोधित किया जा सकता है; विनिमय (या 'लालची आगे रहता है') तर्क इसे औपचारिक बनाते हैं।
मैट्रोइड्स (Matroids) और लालची इष्टतमता (greedy optimality): जब व्यवहार्य समाधान एक भारित मैट्रोइड (weighted matroid) के स्वतंत्र सेट बनाते हैं, तो लालची एल्गोरिदम हमेशा अधिकतम-भार स्वतंत्र सेट पाता है; यह क्रुस्कल के न्यूनतम-स्पैनिंग-ट्री एल्गोरिदम की इष्टतमता जैसे परिणामों को एकीकृत करता है।

Clinical relevance

लालची एल्गोरिदम व्यापक रूप से उपयोग किए जाने वाले सिस्टम को संचालित करते हैं: डेटा संपीड़न प्रारूपों में हफमैन कोडिंग, नेटवर्क डिज़ाइन में न्यूनतम-स्पैनिंग-ट्री एल्गोरिदम, रूटिंग और नेविगेशन में डाइकस्ट्रा का एल्गोरिदम, और ऑपरेटिंग सिस्टम और संसाधन आवंटन में लालची शेड्यूलिंग और सेट-कवर अनुमानी।

History

लालची तर्क क्रुस्कल (1956) और प्रिम (1957) के न्यूनतम-स्पैनिंग-ट्री एल्गोरिदम, हफमैन (1952) के इष्टतम उपसर्ग कोड (optimal prefix codes), और डाइकस्ट्रा (1959) के सबसे छोटे-पथ एल्गोरिदम जैसे क्लासिक परिणामों में दिखाई देते हैं। जब लालची तरीके सफल होते हैं, तो मैट्रोइड-सैद्धांतिक व्याख्या एडमंड्स और अन्य द्वारा 1960 और 1970 के दशक में विकसित की गई थी।

Key figures

David A. Huffman
Joseph Kruskal
Robert Prim
Edsger W. Dijkstra

Seminal works

dijkstra1959
cormen2009

Frequently asked questions

लालची एल्गोरिदम आंशिक नैपसैक (fractional knapsack) के लिए क्यों काम करता है लेकिन 0/1 नैपसैक के लिए नहीं?: आंशिक नैपसैक में, वस्तुओं को विभाजित किया जा सकता है, इसलिए पहले उच्चतम मूल्य-प्रति-भार वाली वस्तु को लेना हमेशा सुरक्षित और सिद्ध रूप से इष्टतम होता है। 0/1 नैपसैक में, वस्तुएं अविभाज्य होती हैं, लालची विकल्प एक बेहतर संयोजन को रोक सकता है, और एक सटीक इष्टतम के लिए गतिशील प्रोग्रामिंग की आवश्यकता होती है।
आप कैसे सिद्ध करते हैं कि एक लालची एल्गोरिदम सही है?: दो मानक तकनीकें विनिमय तर्क (exchange argument) हैं, जो किसी भी इष्टतम समाधान को खराब किए बिना लालची में बदल देती हैं, और 'लालची आगे रहता है' तर्क, जो दर्शाता है कि लालची आंशिक समाधान हर कदम पर किसी भी अन्य की तुलना में कम से कम उतना ही अच्छा है। मैट्रोइड सिद्धांत एक सामान्य पर्याप्त शर्त प्रदान करता है।