गतिशील प्रोग्रामिंग, बुनियादी सिद्धांतों

इष्टतम समाधान का चयन करने के लिए जब प्रदर्शन प्रोग्रामिंग कार्य कभी कभी कि पर्सनल कंप्यूटर की स्मृति को लोड करता है डेटा संयोजनों की बड़ी मात्रा में सॉर्ट करने के लिए आवश्यक हैं। इस तरह के तरीके उदाहरण के लिए, "बांटो और राज करो" की प्रोग्रामिंग विधि, शामिल हैं। इस मामले में एल्गोरिथ्म अलग छोटे उप-कार्य में जुदाई समस्या प्रदान करता है। यह विधि केवल उन मामलों में जहाँ छोटे उप-कार्य पारस्परिक रूप से स्वतंत्र हैं में लागू है। यदि अन्योन्याश्रित उप-कार्य अनावश्यक काम का प्रदर्शन करने से बचने के लिए 50 के दशक में अमेरिकी R.Bellmanom प्रस्तावित गतिशील प्रोग्रामिंग विधि का उपयोग करता।

विधि

गतिशील प्रोग्रामिंग इष्टतम समाधान n आयामी समस्या निर्धारित करने के लिए, उसे n अलग-अलग चरणों को बांटने है। उनमें से हर एक चर के संबंध में एक उप-कार्य है।

इस दृष्टिकोण का मुख्य लाभ यह है कि डेवलपर्स एक आयामी अनुकूलन समस्या में शामिल एक n आयामी समस्या के बजाय उप-कार्य है, और हमारे प्राथमिक उद्देश्य "बॉटम-अप" करने जा रहा है माना जा सकता है।

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

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

विधि विविधताओं या उसके प्रत्यावर्तन के माध्यम से हल किया कार्यों के प्रदर्शन को बेहतर बनाता है।

बिल्डिंग कार्य एल्गोरिथ्म

गतिशील प्रोग्रामिंग एल्गोरिथ्म इस तरह के कार्यों कि काम तो इसके समाधान के लिए दो या अधिक उप-कार्य में विभाजित है सभी उप-कार्य करने के लिए सर्वोत्कृष्ट समाधान से बना है के निर्माण शामिल है, यह भी शामिल है। इसके अलावा, यह एक आवर्ती संबंध में लिखने के लिए, और एक पूरे के रूप कार्य के लिए इष्टतम पैरामीटर मान की गणना के लिए आवश्यक है।

कभी कभी, 3 कदम पर प्रत्येक कार्य की प्रगति पर कुछ अतिरिक्त पृष्ठभूमि जानकारी याद करने के लिए है। इस वापसी स्ट्रोक कहा जाता है।

आवेदन विधि

जब दो विशेषता विशेषताएं हैं गतिशील प्रोग्रामिंग लागू किया जाता है:

• उप-कार्य के लिए इष्टतम;
• subproblems ओवरलैपिंग की समस्या में उपस्थिति।

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

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

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