व्यवहार में गतिशील प्रोग्रामिंग।

इस तरह के विषयों पर यह मेरा पहला लेख है, इसलिए कृपया समझ के साथ व्यवहार करें। मुझे किसी भी टिप्पणी और टिप्पणी पर खुशी होगी।



मुझे लगता है कि आप में से कई लोगों ने सुना है, और कई ने गतिशील प्रोग्रामिंग विधि के रूप में कुछ समस्याओं को हल करने की ऐसी विधि भी दी है। जो लोग नहीं जानते, उनके लिए यहाँ विकिपीडिया परिभाषा है:

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

http://ru.wikipedia.org/wiki/_

बहुत अच्छा और समझ में आता है, लेकिन चलो बेहतर एक उदाहरण लेते हैं। मुझे लगता है कि सबसे सरल बात जो दिमाग में आती है, वह है फाइबोनैचि संख्या। इसके लिए कुछ प्रारंभिक आंकड़े दिए गए हैं - A [1] = 1, A [2] = 1, जिसके बाद तत्व A [i] = A [i-1] + A [i-2]। इसके अलावा, ए [i] को अक्सर एक राज्य कहा जाता है, और गणना डेटा के संबंध में एक निश्चित संबंध एक संक्रमण कहा जाता है। इस स्थिति में, A [i] - से A [i-1] और A [i-2] से 2 संक्रमण होते हैं। कार्य के आधार पर संक्रमण की संख्या भिन्न हो सकती है।

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

NxM और संख्या K की संख्या A का एक मैट्रिक्स है। इसकी पहली पंक्ति दी गई है - A [1,1] .. A [1, M]। उसके बाद, पहली पंक्ति के नीचे प्रत्येक तत्व के लिए, मान को त्रिभुज के ऊपर के सभी तत्वों के योग के रूप में परिभाषित किया जाता है। यह मैट्रिक्स A [N, 1] .. A [N, M] की अंतिम पंक्ति को आउटपुट करने के लिए आवश्यक है। सीमाएँ: 1, एन, एम: 2000; 2 ≤ K ≤ 10 ⁹ ।

तो, किसी भी लाइन में तत्वों के अर्थ का पता लगाने के लिए, हमें इसके ऊपर सभी लाइनों में तत्वों के मूल्यों को जानने की आवश्यकता है। सबसे सरल समाधान जो मन में आता है, वह प्रत्येक तत्व के लिए बस त्रिकोण में सभी तत्वों के माध्यम से लेने और जाने के लिए है, योग की गिनती। हां, यह तब किया जा सकता है जब समय महत्वपूर्ण नहीं होता है या जब एन और एम पर प्रतिबंध छोटे होते हैं, क्योंकि ऐसा एल्गोरिथ्म ऑर्डर ओ (एन ⁴ ) के एसिम्पोटिक्स के लिए काम करता है (यदि हम एन = एम लेते हैं)। यानी एन = एम = 100 के साथ भी यह 5-10 सेकंड के आदेश पर काम करेगा (कंप्यूटर पर निर्भर करता है), मैं पहले से ही एन = 1 = 2000 के बारे में चुप हूं। इसलिए हमें किसी तरह इस कारोबार को तेज करने की जरूरत है। और ऐसा करते हैं। हमारे पास एक त्रिकोण है जिसे गिनने की आवश्यकता है। और हमारे पास इसके ऊपर के सभी तत्वों के लिए पूर्व-गणना त्रिकोण हैं। तो चलो पहले से गणना की गई का उपयोग करके एक नया त्रिकोण बनाते हैं! हम तस्वीर को देखते हैं:



यानी अगर हमें A [i, j] में शुरुआत के साथ एक त्रिकोण की गणना करने की आवश्यकता है, तो यह सूत्र द्वारा गणना की जाएगी:

A [i, j] = (A [i-1, j] + 2 * A [i-1, j-1] + 2 * A [i-1, j + 1] -2 * A [i-2 , j]) mod K. (जहां mod k को modulo K लिया जाता है)

हम त्रिकोण A [i-2, j] को घटाते हैं यह दो त्रिभुजों A [i-1, j-1] और A [i-1, j + 1] का प्रतिच्छेदन क्षेत्र है, अन्यथा हम इसे 2 बार गिनेंगे। वैसे, अपने लिए सोचें कि हम कुछ मूल्यों को 2 से क्यों गुणा करते हैं।

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