👌🏾 👩🏿‍💻 💭 पुस्तक "परफेक्ट अल्गोरिथम। लालची एल्गोरिदम और गतिशील प्रोग्रामिंग

हैलो, हब्रोज़िटेली! नई किताब में, टिम राफगार्डन लालची एल्गोरिदम (नियोजन समस्या, न्यूनतम फैले हुए पेड़, क्लस्टरिंग, हफ़मैन कोड) और डायनेमिक प्रोग्रामिंग (बैकपैक समस्या, अनुक्रम संरेखण, सबसे छोटे रास्ते, इष्टतम खोज पेड़) के बारे में बात करता है। यह पोस्ट एक अंश "लालची एल्गोरिथ्म का विकास करना" प्रस्तुत करता है।

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

हमारी योजना का पहला चरण सामान्य समस्या के दो विशेष मामलों को हल करना है। इन मामलों के हमारे समाधानों से पता चलेगा कि सामान्य मामले में एक लालची एल्गोरिथ्म कैसा दिख सकता है। फिर हम डोमेन को एक उम्मीदवार एल्गोरिथ्म तक सीमित कर देते हैं और यह साबित करते हैं कि यह वही उम्मीदवार है जो समस्या को सही ढंग से हल करता है। जिस प्रक्रिया से हम इस एल्गोरिथ्म में आते हैं, वह एल्गोरिथम की तुलना में याद रखने के लिए अधिक महत्वपूर्ण है; यह प्रक्रिया दोहराई जा सकती है और आप इसे अपने स्वयं के अनुप्रयोगों में उपयोग कर सकते हैं।

13.3.1। दो विशेष मामले

चलो मान लेते हैं कि पूरा होने की तारीखों के भारित योग को कम करने के कार्य के लिए, वास्तव में एक सही लालची एल्गोरिथ्म है। यदि हम यह मान लें कि सभी कार्यों में समान लंबाई (लेकिन संभवतः अलग-अलग वजन) है या, इसके विपरीत, एक ही वजन (लेकिन संभवतः अलग-अलग लंबाई) है तो यह कैसा दिखेगा?

13.2

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.

सामान्य तौर पर, काम में अलग-अलग वजन और अलग-अलग लंबाई हो सकती है। जब भी हमारे अंगूठे के दो नियम - छोटे काम को प्राथमिकता देना और अधिक वजन के साथ काम करना - एक दो नौकरियों के लिए भाग्यशाली हैं, तो हम जानते हैं कि पहले किसकी योजना है (अधिक वजन के साथ कम)। लेकिन अगर ये दो नियम परस्पर विरोधी सलाह दें तो क्या होगा? हमें कम वजन के साथ एक काम और उच्च वजन के साथ एक लंबे काम के साथ क्या करना चाहिए?

सबसे सरल लालची एल्गोरिथ्म क्या होगा जो इसे करना चाहिए? प्रत्येक कार्य के दो पैरामीटर हैं, और एल्गोरिथ्म दोनों को देखना चाहिए। सबसे अच्छा विकल्प एक सूत्र विकसित करना होगा जो प्रत्येक कार्य की लंबाई और वजन को एक ही निशान (योगदान) में संकलित करता है, ताकि उच्चतम से सबसे कम अंक तक की योजना बनाने का काम भारित पूर्ण तिथियों की मात्रा को कम करने की गारंटी हो। यदि ऐसा कोई सूत्र मौजूद है, तो हमारे दो विशेष मामलों से यह इस प्रकार है कि इसमें दो गुण होने चाहिए: (i) निश्चित लंबाई को छोड़कर, यह कार्य के भार से बढ़ना चाहिए; (ii) निर्धारित वजन को छोड़कर, यह कार्य की लंबाई से कम होना चाहिए (याद रखें कि निशान जितना अधिक होगा, उतना ही अच्छा होगा)। एक मिनट बिताएं जिसमें कई सूत्र हैं जो इन दोनों गुणों के हैं।

शायद सबसे सरल कार्य, जो वजन में बढ़ता है और लंबाई में घटता है, उनके बीच का अंतर है:
काम के चिह्न के लिए प्रस्ताव नंबर 1।

संकेतित चिह्न नकारात्मक हो सकता है, लेकिन यह उच्चतम से निम्नतम निशान तक कार्यों के लगातार निर्माण में कोई बाधा नहीं डालता है। । हालांकि, कई अन्य विकल्प हैं। उदाहरण के लिए, दो मापदंडों का अनुपात एक और उम्मीदवार है:

काम को चिह्नित करने के लिए प्रस्ताव संख्या 2।

मार्क की गणना के लिए ये दो कार्य दो अलग-अलग लालची एल्गोरिदम को जन्म देते हैं।

GREEDYDIFF GREED DIFFERENCE

योजना अवरोही क्रम में कार्य करती है
(मनमाने ढंग से संयोगों को तोड़ती हुई)।

GREEDYRATIO

( ).

इस प्रकार, पहले से ही हमारा पहला अध्ययन अध्ययन लालची प्रतिमान (धारा 13.1.2) के पहले विषय को दर्शाता है: आमतौर पर एक कार्य के लिए कई प्रतिस्पर्धी लालची एल्गोरिदम को प्रस्तावित करना मुश्किल नहीं है। लेकिन दोनों में से कौन सा एल्गोरिदम, यदि कोई है, तो सही है? उनमें से एक को बाहर करने का एक त्वरित तरीका एक उदाहरण खोजना है जिसमें दो एल्गोरिदम उद्देश्य फ़ंक्शन के विभिन्न मूल्यों के साथ अलग-अलग कार्यक्रम प्रदर्शित करते हैं। किसी भी एल्गोरिथ्म के लिए जिसके परिणाम इस उदाहरण में बदतर हैं, हम यह निष्कर्ष निकाल सकते हैं कि यह हमेशा इष्टतम नहीं है। एक ही वजन या एक ही लंबाई के कार्यों के साथ दो विशेष मामलों में, दोनों एल्गोरिदम सही ढंग से कार्य करते हैं। उनमें से एक के बहिष्कार का सबसे सरल संभव उदाहरण एक कार्य का उदाहरण हो सकता है जिसमें दो कार्यों में अलग-अलग वजन और लंबाई होती है,नतीजतन, दोनों एल्गोरिदम विपरीत क्रम में काम करने की योजना बनाते हैं। यही है, हम दो कामों की तलाश कर रहे हैं, जिनमें से भिन्नता का क्रम संबंध में उनके क्रम के विपरीत है। उदाहरण:

पहले काम का एक बड़ा अनुपात है,

लेकिन एक बड़ा अंतर (-2 बनाम -1) है। इस प्रकार, एल्गोरिथ्म GreedyDiffपहले दूसरे काम की GreedyRatioयोजना बनाता है, जबकि एल्गोरिथम विपरीत योजना बनाता है।

उदाहरण 13.3

क्रमशः GreedyDiffऔर एल्गोरिदम द्वारा निर्धारित शेड्यूल में भारित पूरा होने की तारीख क्या है GreedyRatio?

a) 22 और 23
b) 23 और 22
c) 17 और 17
d) 17 और 11
(समाधान और स्पष्टीकरण के लिए, 13.3.3 देखें)।

हम एल्गोरिथ्म GreedyDiffको आगे के विचार से बाहर निकालकर आगे बढ़े । हालांकि, व्यायाम 13.3 का परिणाम सीधे इस तथ्य की ओर नहीं जाता है कि एल्गोरिथ्म GreedyRatioहमेशा इष्टतम होगा। जहां तक हम जानते हैं, ऐसे अन्य मामले हैं जब यह एल्गोरिथ्म एक गैर-इष्टतम शेड्यूल का उत्पादन करता है। आपको हमेशा एक एल्गोरिथ्म पर संदेह होना चाहिए जो कि इसकी शुद्धता के प्रमाण के साथ नहीं है, भले ही यह एल्गोरिथ्म कई परीक्षण मामलों में सही काम करता है और लालची एल्गोरिदम का बहुत संदेह है।

हमारे मामले में, एल्गोरिथ्म GreedyRatio, वास्तव में, भारित पूर्ण तिथियों की मात्रा को कम करने की गारंटी है।

प्रमेय 13.1 (एल्गोरिथ्म की शुद्धता GreedyRatio) । सकारात्मक कार्य भार के प्रत्येक सेट के लिएऔर सकारात्मक नौकरी की लंबाई, एल्गोरिथ्म GreedyRatioभारित पूर्ण तिथियों के सबसे कम संभव योग के साथ एक अनुसूची प्रदर्शित करता है।

यह तार्किक कथन स्पष्ट नहीं है, और आपको सबूत प्राप्त किए बिना उस पर भरोसा नहीं करना चाहिए। लालची प्रतिमान (धारा १३.१.२) के तीसरे विषय के अनुसार, यह प्रमाण पूरे अगले खंड को लेता है।

, . .

. — , ( ). — , , , . «» ( ) , .

लालची प्रतिमान का शेष विषय रनटाइम विश्लेषण की सरलता है (खंड 13.1.2)। यहाँ, ज़ाहिर है, यह है। GreedyRatio एल्गोरिथम केवल संबंध द्वारा नौकरियों को सॉर्ट करता है, जो O (n लॉग एन) समय लेता है, जहां n इनपुट में नौकरियों की संख्या है (पी 24 पर फुटनोट 1 देखें)।

13.3.3। व्यायाम समाधान 13.213.3

13.2 व्यायाम करने का उपाय

सही उत्तर: (क) । पहले, मान लीजिए कि सभी नौकरियों की लंबाई एक ही है, कहते हैं 1. फिर प्रत्येक अनुसूची में समय सीमा का एक ही सेट है - {1, 2, 3, ..., n} - और एकमात्र सवाल यह है कि किस तरह की नौकरी मिलती है पूरा होने की तारीख और क्या समय सीमा है। काम के वजन के लिए हमारे शब्दार्थ निश्चित रूप से इसका मतलब है कि अधिक वजन के साथ काम को कम समय पूरा करना चाहिए, और यह सच है। उदाहरण के लिए, आप 10 थर्ड के वजन के साथ काम की योजना नहीं बनाना चाहेंगे (3 की समय सीमा के साथ) और 20 पांचवें के वजन के साथ काम करें (5 की समय सीमा के साथ); आप इन दोनों कार्यों के पदों को बदलने से बेहतर होंगे, जिससे 20 तक भारित समय सीमा घट जाएगी (जैसा कि आप अपने लिए देख सकते हैं)।

दूसरा मामला, जिसमें सभी कामों का वजन समान है, थोड़ा पतला है। यहां आप छोटे काम को प्राथमिकता देना चाहते हैं। उदाहरण के लिए, 1 और 2 की लंबाई के साथ इकाई भार के दो कामों पर विचार करें। यदि आप पहले एक छोटे काम की योजना बनाते हैं, तो पूर्णता की समय सीमा 1 और 3 होगी। कुल मिलाकर 4. उल्टे क्रम में, समय सीमा 2 और 3 सबसे खराब परिणाम के साथ होगी। 5. सामान्य रूप से, नियोजित काम पहले सभी काम के पूरा होने में योगदान देता है, क्योंकि सभी काम को पहले पूरा होने का इंतजार करना चाहिए। सभी चीजें समान हैं, सबसे कम काम की योजना बनाना पहले इस नकारात्मक प्रभाव को कम करता है। पहली नौकरी को छोड़कर सभी पूरा होने की दिनांक से पीछे काम योगदान है, तो दूसरा सबसे छोटा काम अगले योजना बनाई जानी चाहिए, और इतने पर।

व्यायाम 13.3 का समाधान

सही जवाब बी है)। एल्गोरिथम GreedyDiffपहले दूसरी नौकरी की योजना बनाता है । इस काम को पूरा करने की समय सीमा है,

जबकि एक और काम पूरा करने की समय सीमा पूरी होने

के लिए भारित समय सीमा का योग है

एल्गोरिथम GreedyRatioपहले कार्य की योजना बनाता है , जिसके परिणामस्वरूप समय सीमा

और भारित समय सीमा के योग के बराबर है

चूंकि एल्गोरिथ्म इस उदाहरण के लिए GreedyDiffइष्टतम अनुसूची की गणना करने में विफल रहता है, इसलिए यह हमेशा सही नहीं होता है।

»किताब के बारे में अधिक जानकारी पर पाया जा सकता प्रकाशक की वेबसाइट
» सामग्री
» अंश

कूपन पर लिए Khabrozhiteley 25% छूट - एल्गोरिदम

पुस्तक के कागज संस्करण के भुगतान करने पर, एक इलेक्ट्रॉनिक पुस्तक ई-मेल द्वारा भेजा जाता है।

पुस्तक "परफेक्ट अल्गोरिथम। लालची एल्गोरिदम और गतिशील प्रोग्रामिंग »

13.3.1। दो विशेष मामले

13.3.2.

13.3.3। व्यायाम समाधान 13.213.3

More articles: