Greedy सोच

एक greedy कलनविधि उत्तर को चरण-दर-चरण बनाती है और हर बार वही विकल्प चुनती है जो उसी क्षण सबसे अच्छा दिखाई देता है; बाद में उसे कभी वापस नहीं लेती। ⚡

हर क्षण आप एक ही बात पूछते हैं: कौन-सा एक विकल्प locally सबसे अधिक लाभ देगा? उसे चुनकर अगले निर्णय पर बढ़ जाइए।

लालची विधि किसी विकल्प को चुनकर उसे never reverses करती है। बैकट्रैकिंग के विपरीत, यह दूसरे रास्तों को नहीं आज़माती, और इसी कारण इतनी तेज़ होती है।

क्योंकि यह हर चरण में केवल एक बार निर्णय लेती है, इसलिए क्रमबद्ध करने के बाद लालची विधि सामान्यतः O(n) या O(n log n) में चलती है। प्रतियोगिताओं में इसकी सबसे बड़ी विशेषता यही गति है।

अधिकांश लालची समाधान वस्तुओं को sorting से शुरू होते हैं। क्रम से पता चलता है कि हर चरण में कौन-सा तत्व स्पष्ट रूप से सबसे अच्छा चुना जाना चाहिए।

लालची विधि तभी काम करती है जब कोई local सर्वोत्तम विकल्प किसी वैश्विक सर्वोत्तम उत्तर का भी भाग हो। इसे लालची चयन का गुण कहते हैं।

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

लालची विधि पर भरोसा करने से पहले उसे अदला-बदली वाले तर्क से justify कीजिए या छोटी प्रविष्टियों पर पूर्ण खोज के विरुद्ध तनाव-परीक्षण कीजिए।

एक exchange प्रमाण लालची चयन को सर्वोत्तम उत्तर में रखकर दिखाता है कि परिणाम उससे खराब नहीं होता। यदि यह सिद्ध हो जाए, तो लालची विधि सुरक्षित है।

लगभग हर लालची विधि का shape ऐसा होता है: क्रमबद्ध कीजिए, फिर एक बार पूरी सूची पर चलते हुए अपने नियम में फिट होने वाली वस्तु चुनते जाइए।

जब कोई स्पष्ट ordering विकल्पों को क्रम देता हो और एक नियम लगातार सबसे अच्छा साबित होता हो, तब लालची विधि आज़माइए। यदि विकल्प जटिल तरीके से एक-दूसरे पर निर्भर हों, तो DP की ओर झुकिए।

लालची विधि best local step चुनती है और सामान्यतः पहले क्रमबद्ध करने के बाद पीछे मुड़कर नहीं देखती। यह तेज़ है, लेकिन तभी सही होती है जब आप सिद्ध कर सकें कि लालची चयन का गुण लागू होता है। 🚀