ओवरलैपिंग कार्ड के साथ गेम को हल करने के लिए संरचना/एल्गोरिदम

Question

टावर सॉलिटेयर, ट्राइपैक्स, या फेयरवे सॉलिटेयर की तर्ज पर एक कार्ड गेम पर विचार करें: तालिका में कुछ कार्ड शामिल हैं जो तुरंत उपलब्ध हैं, जिनमें से प्रत्येक अन्य कार्ड को कवर कर सकता है इसके नीचे (उन्हें खेले जाने से रोकना)। आपके पास एक "नींव" कार्ड है, और यदि आप अपने नींव कार्ड के ऊपर या नीचे एक रैंक है, तो आप तालिका से कार्ड हटा सकते हैं, जिस बिंदु पर यह आपका नया नींव कार्ड बन जाता है। जब आप तालिका से कार्ड नहीं खेल सकते हैं, तब से आपके पास आकर्षित करने के लिए सीमित संख्या में प्रतिस्थापन कार्ड होते हैं, इसलिए आप आम तौर पर कार्ड का सबसे लंबा अनुक्रम खेलना चाहते हैं।

सबसे पहले, समाधान खोजने में सुविधा के लिए आप बोर्ड का प्रतिनिधित्व कैसे करेंगे? दूसरा, आप सबसे लंबे समय तक चलने योग्य अनुक्रम खोजने के लिए किस एल्गोरिदम का उपयोग करेंगे?

उदाहरण: निकाले जाने से ऊपर नीचे ब्लॉक कार्ड पर

 -4a- -5- 
-3- -2- -4b-

कार्ड: आप जब तक 3 और 2 दोनों चले गए हैं 4a नहीं निकाल सकते। मान लें कि आपका शुरुआती कार्ड एक इक्का है, इष्टतम खेल यहां 2, 3, 4 बी, 5, 4 ए होगा। (आप इसके बजाय 2, 3, 4 ए खेल सकते हैं, लेकिन यह उतना अच्छा नहीं है।)

मुझे लगता है कि इसे किसी प्रकार के निर्देशित ग्राफ के रूप में प्रदर्शित किया जाना चाहिए। आपके पास किनारों को 3 और 2 से 4 ए और 2 और 4 बी से 5 तक, लेकिन क्या आपके पास 3 और 2 के बीच और 4a और 5 के बीच किनारे होंगे, क्योंकि एक दूसरे के बाद बजाने योग्य है? यदि हां, तो क्या यह तथ्य होगा कि उन्हें किसी भी क्रम में खेला जा सकता है (3 फिर 2, या 2 फिर 3) ग्राफ में एक चक्र बनाता है जो आपको कुशल "सबसे लंबा पथ" एल्गोरिदम का उपयोग करने से रोकता है? (मुझे लगता है कि ग्राफ़ में सबसे लंबा रास्ता खोजना एनपी-पूर्ण है यदि ग्राफ़ में चक्र होते हैं।)

Answer 1

क्या होगा यदि आप इसे गेम-स्टेटस के ग्राफ के रूप में प्रस्तुत करते हैं (फ्लाई पर गणना की गई संभावित अगले राज्यों के साथ) - जो होगा लूप नहीं है, जिसका अर्थ यह है कि यह प्रारंभ बिंदु से खेल के संभावित राज्यों (जो अभी भी काफी असंख्य हो सकता है) पर एक सीधा डीएफएस है।

Answer 2

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

मैं तालिका में शेष कार्ड की संरचना के आकार के आधार पर एक एन्कोडिंग का सुझाव देता हूं।

राज्य का पहला डेटा बाएं सबसे ऊपर वाले कार्ड का अद्वितीय आईडी हो सकता है। (उदाहरण के लिए 4 ए की तरह, यह एक अर्थ में अद्वितीय है कि केवल एक कार्ड 4 ए है)। प्रत्येक उपलब्ध कार्ड (कार्ड जो लेने के लिए तैयार है) के लिए शेष आकार को -1,0,1 में से एक द्वारा दर्शाया जा सकता है, यह बताते हुए कि क्या अगला कार्ड बाईं ओर एक ही 'स्तर' पर है या यह एक स्तर है गहरा या उच्च। (यह इस धारणा का शोषण कर रहा है कि एक कार्ड केवल 2 अन्य कार्ड ओवरलैप करता है और यह कि संरचना उदाहरण में आपके द्वारा दी गई एक जैसी दिखती है)।