गतिशील प्रोग्रामिंग

Question

के साथ एक चेकरबोर्ड पेबब्लिंग मैं खुद को गतिशील प्रोग्रामिंग सिखाने की कोशिश कर रहा हूं, और एमआईटी से इस समस्या में भाग गया।

हमें एक चेकरबोर्ड दिया गया है जिसमें 4 पंक्तियां और एन कॉलम हैं, और प्रत्येक वर्ग में एक पूर्णांक लिखा गया है। हमें 2 एन कंकड़ का एक सेट भी दिया जाता है, और हम को चेकरबोर्ड पर इनमें से कुछ या सभी को रखना चाहते हैं (प्रत्येक कंकड़ को एक वर्ग पर रखा जा सकता है) ताकि वर्गों में पूर्णांक के योग को अधिकतम करने के लिए कंकड़ से ढंका हुआ। एक बाधा है: कंकड़ की नियुक्ति के लिए कानूनी होने के लिए, उनमें से कोई भी क्षैतिज या लंबवत आसन्न वर्गों (विकर्ण आसन्नता ठीक है) पर हो सकता है।

(ए) किसी भी कॉलम में होने वाले कानूनी पैटर्न की संख्या निर्धारित करें (अलगाव में, आसन्न कॉलम में कंकड़ को अनदेखा कर) और इन पैटर्न का वर्णन करें। दो पैटर्न को संगत कॉल करें यदि उन्हें कानूनी प्लेसमेंट बनाने के लिए आसन्न कॉलम पर रखा जा सकता है। आइए उन सबप्रोबम्स पर विचार करें जो आरएसटी के कॉलम 1 के एन से युक्त हैं। प्रत्येक subproblem एक प्रकार असाइन किया जा सकता है, जो अंतिम कॉलम में होने वाला पैटर्न है।

(बी) संगतता और प्रकार के विचारों का उपयोग करके, एक इष्टतम प्लेसमेंट की गणना के लिए ओ (एन) -टाइम गतिशील प्रोग्रामिंग एल्गोरिदम दें।

ठीक है, इसलिए भाग के लिए: 8 संभावित समाधान हैं।

भाग बी के लिए, मैं अनिश्चित हूं, लेकिन यह वह जगह है जहां मैं नेतृत्व कर रहा हूं: उप-समस्याओं में स्प्लिट। मुझे एन में मान लीजिए। 1. सीजे को परिभाषित करें [i] स्तंभ 0 को कंकड़ करके इष्टतम मूल्य होने के लिए, ..., i, ऐसे कॉलम में मेरे पास पैटर्न प्रकार जे है। 2. प्रत्येक पैटर्न प्रकार के लिए एन तत्वों के 8 अलग-अलग सरणी बनाएं।

मुझे यकीन नहीं है कि यहां से कहाँ जाना है। मुझे एहसास है कि इस समस्या के समाधान ऑनलाइन हैं, लेकिन समाधान मेरे लिए बहुत स्पष्ट नहीं लगते हैं।

Answer 1

आप सही रास्ते पर हैं। जैसा कि आप प्रत्येक नए कॉलम की जांच करते हैं, आप उस बिंदु तक सभी संभव सर्वोत्तम स्कोर कंप्यूटिंग समाप्त कर देंगे।

मान लें कि अपने संगतता सूची (एक 2 डी सरणी) बनाया गया है और यह एल बुलाया करते _मैं [y] ऐसी है कि प्रत्येक पैटर्न के लिए मैं वहाँ एक या अधिक संगत पैटर्न एल _मैं [y हैं ]।

अब, आप कॉलम जे की जांच करें। सबसे पहले, आप प्रत्येक पैटर्न i के लिए कॉलम के पृथक स्कोर की गणना करते हैं। इसे एस _जे [i] पर कॉल करें। प्रत्येक पद्धति के लिए मैं और संगत पैटर्न एक्स = एल _मैं [y], आप कुल स्कोर सी अधिकतम करने के लिए की जरूरत है _जे ऐसी है कि सी _जे [x] = सी _{जम्मू 1} [i] + एस _जे [x]। यह एक साधारण सरणी परीक्षण और अद्यतन (यदि बड़ा है) है।

इसके अतिरिक्त, आप कंकड़ पैटर्न को स्टोर करते हैं जो प्रत्येक स्कोर को जन्म देता है। आप सी _जे अद्यतन करते हैं [x] (यानी आप अपने वर्तमान मूल्य से अपने स्कोर को बढ़ाने) तो आरंभिक तथा अनुवर्ती पैटर्न कि पी _जे के रूप में अद्यतन की वजह से याद [x] = मैं। यह कहता है "पैटर्न x ने पिछले पैटर्न i दिए गए सर्वोत्तम परिणाम दिए"।

आप सभी जब से किया जाता है, बस पैटर्न मैं सबसे अच्छा के साथ खोजने के स्कोर सी _n [i]। इसके बाद आप पी _जे का उपयोग करके प्रत्येक कॉलम से कंकड़ पैटर्न को पुनर्प्राप्त करने के लिए बैकट्रैक कर सकते हैं जिससे परिणामस्वरूप पहुंचे।