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

Question

का उपयोग कर 8-रानी समस्या मैं गतिशील प्रोग्रामिंग का उपयोग करके 8-रानी समस्या को लागू करने के विचार से काफी उलझन में हूं। ऐसा लगता है कि डीपी के लिए एक तरफ संभव नहीं है "अगर समस्या उपप्रोब्लेम की एक श्रृंखला में टूट गई थी और प्रत्येक सबप्रोबलेम के लिए इष्टतम समाधान पाया गया था, तो परिणामस्वरूप समाधान इन उपप्रवाहों के समाधान के माध्यम से महसूस किया जाएगा। एक समस्या इसमें इस संरचना को गतिशील प्रोग्रामिंग के साथ हल नहीं किया जा सकता है "(Reference)। इसे ध्यान में रखते हुए, 7x7 बोर्ड के लिए इष्टतम समाधान 8x8 के लिए इष्टतम (यहां तक ​​कि गलत) भी नहीं हो सकता है। इसलिए, समस्या का नतीजा उप-समस्या के इष्टतम समाधान के माध्यम से महसूस नहीं हो सकता है।

दूसरी तरफ, डीपी बैकट्रैकिंग समस्याओं के लिए अनुकूलन है ... यदि ऐसा है तो 8-रानी समस्या को बैकट्रैकिंग द्वारा हल किया जा सकता है ... क्या इसका मतलब यह है कि केवल मृत-सिरों को संग्रहित करके बैकट्रैकिंग समाधान को डीपी में परिवर्तित कर सकते हैं? यदि ऐसा है, तो हो सकता है कि 2,1 माता-पिता के लिए संभव नहीं है 1,1 लेकिन संभवतः 1,2 के लिए संभव हो सकता है।

अद्यतन

किसी को भी है कि क्या 8-रानी या एन-रानी समस्या गतिशील प्रोग्रामिंग का उपयोग करके हल किया जा सकता पता नहीं है? यदि हां, तो ऊपर दिए गए अवलोकनों पर आपकी टिप्पणियां क्या होंगी?

Answer 1

इष्टतम समाधान।

हाँ, आप सही हैं। लेकिन समस्या को विभाजित करने का यह एक अच्छा तरीका नहीं है। paper yi_H posted in his answer, प्रमेय 2.4 में देखें, और एल्गोरिदम विवरण देखें। वे समाधानों को बंद लाइनों के सेट के अनुसार समकक्ष वर्गों में विभाजित करते हैं (यानी लाइनें जिन्हें रानियों द्वारा धमकी दी जाती है)। प्रमेय 2.4 गारंटी देता है कि एक बार जब वे बंद लाइनों के विशेष सेट पर उप-समस्या हल करते हैं, तो वे बाकी को अलग-अलग हल कर सकते हैं और फिर परिणाम जोड़ सकते हैं! बहुत चालाक।

Answer 2

बस स्पष्ट गूगल हिट पोस्टिंग:

A dynamic programming solution to the n-queens problem

नोट: यह अभी भी है बहुत के लिए बड़ी n के धीमी गति से, हे (च (एन) * 8^n), तो आप बेहतर कुछ अन्य का उपयोग एल्गोरिथ्म: हो सकता है नहीं इष्टतम के साथ-साथ (यहां तक ​​कि गलत) 8x8 के लिए 7x7 बोर्ड के लिए

A Polynomial Time Algorithm for the N-Queens Problem