मैं इस समस्या का समाधान कैसे कर सकता हूं?
मैं नीचे बताई गई समस्या के समाधान पर काम कर रहा हूं। मैं जानवर बल का उपयोग कर रहा हूं, मैं उस बिंदु पर पहुंच गया हूं जहां समाधान निषेधात्मक हैं, इसलिए मुझे अधिक (यदि संभव हो तो) का अनुकूलन करने की आवश्यकता है। बेशक, यह बेहतर होगा यदि समस्या को हल करने का एक बेहतर तरीका है (जानवर बल नहीं)।
क्या मेरे समाधान में सुधार करने के लिए मैं कुछ भी कर सकता हूं, या संदर्भ मैं (समान समस्याएं, आदि) देख सकता हूं?
समस्या
हम एक आयताकार बोर्ड से शुरू करते हैं। प्रत्येक कोशिका एन राज्यों में हो सकती है, और प्रत्येक सेल के लिए प्रारंभिक स्थिति प्रत्येक सेल के लिए यादृच्छिक (0 <= राज्य <एन) है। हमारे पास कई आकार हैं, जो सभी बोर्ड के अंदर फिट होते हैं। हर आकृति निरंतर है।
प्रत्येक आकृति को बोर्ड में एक बार (और केवल एक बार) रखा जाना चाहिए। जब कोई आकृति रखी जाती है, तो प्रत्येक कोशिका जो आकृति के अंतर्गत आती है, उसका मान 1 से बढ़ जाता है। यदि किसी सेल में बोर्ड का मान N तक पहुँच जाता है, तो इसे 0 में बदल दिया जाता है।
लक्ष्य यह है कि पदों को प्रत्येक आकार में रखा जाना चाहिए ताकि अंतिम बोर्ड में मान के साथ सभी कोशिकाएं हों। हमेशा कम से कम एक समाधान होता है। मान लें कि समस्या समाप्त बोर्ड से शुरू होकर यादृच्छिक पदों पर यादृच्छिक आकार लागू करने से उत्पन्न होती है।
बोर्ड का आकार, राज्यों की संख्या एन और आकार की संख्या खेल का सेटअप है, और प्रत्येक 'स्तर' के लिए (अलग-अलग दरों पर) बढ़ते रहते हैं।
वर्तमान में मैं क्या कर रहा हूं
मैं केवल ब्रूट बल का उपयोग करके समस्या को एक निश्चित आकार तक हल करने में सक्षम हूं। मेरी कुछ आशाएँ हैं। मैं एक ऐसे बिंदु पर पहुंच गया हूं जहां समाधान निषेधात्मक है, इसलिए मैं अपने तर्क में सुधार करना चाहूंगा।
पहली बात जो मैं कर रहा हूं वह आकार को बड़े से छोटे में क्रमबद्ध करना है, छोटे को आंतरिक पुनरावृत्तियों में स्थानांतरित किया जाएगा। धारणा (जो मैंने साबित नहीं की है, लेकिन तेज होने के लिए परीक्षण किया है) यह है कि छोटे आकार को अधिक स्थानांतरित करना बेहतर है, क्योंकि उनके पास समाधान उत्पन्न करने का एक उच्च मौका है।
दूसरे, बार-बार आकृतियों के लिए, मैं सभी क्रमपरिवर्तन की जांच करने से बचता हूं, क्योंकि वे समान परिणाम देते हैं। मैं भी केवल एक ही स्थिति की जाँच करता हूँ जब एक ही आकृतियों की एक जोड़ी ओवरलैप होती है (क्योंकि सभी ओवरलैप एक ही परिणाम देते हैं)।
एक अंतिम अनुकूलन जो मुझे लगता है कि बहुत मदद करेगा, लेकिन मैं अभी भी लागू कर रहा हूं: अनुक्रम में प्रत्येक आकार में, उन कोशिकाओं की कुल संख्या को गिनें, जो आकार में रहती हैं। यह संख्या, एक समाप्त बोर्ड प्राप्त करने के लिए आवश्यक कुल सेल फ़्लिप के शून्य से, एन की एक बहु होनी चाहिए। यदि नहीं, तो शेष आकृतियों की स्थिति को मजबूर करने के लिए कोई बिंदु नहीं है, और हमें बाहरी लूप में एक आकृति को फिर से बनाना होगा।
अतिरिक्त विवरण
मैं इसे कैसे अनुकूलित किया जाए, इसके बारे में किसी अन्य सुझाव में दिलचस्पी रखता हूं। ज्ञात एल्गोरिदम, यहां तक कि समस्या के इस सेट के लिए एक अच्छा नामकरण, जो कि मैं और अधिक शोध करने के लिए उपयोग कर सकता हूं वह बहुत अच्छा होगा।
जवाब
लीनियर प्रोग्रामिंग
आपकी समस्या निम्नलिखित तरीके से तैयार की जा सकती है: हमें वैक्टर दिए गए हैं $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, जहां बोर्ड है $d$ कोशिकाओं, और लक्ष्य है, एक वेक्टर दिया $c \in (\mathbb{Z}/N\mathbb{Z})^d$, एक फ़ंक्शन खोजें $f$ ताकि $\sum_i v_{i,f(j)}=c$। यह समस्या पूर्णांक लीनियर प्रोग्रामिंग द्वारा हल की जा सकती है। यह से संबंधित है$d$-डिमेटिक सब्मिट-सम प्रॉब्लम, इसलिए आप मल्टी-डायमेंशनल सबसेट-सम के लिए अन्य एल्गोरिदम भी खोज सकते हैं और उन्हें भी आज़मा सकते हैं।
हम इसे इस तरह कैसे तैयार करते हैं? अगर ग्रिड है$d$ कोशिकाओं, हम एक के रूप में एक आकार के बारे में सोच सकते हैं $d$आकार द्वारा कवर कोशिकाओं में 1 के साथ 0 और 1 के -vector। प्रत्येक आकृति को अलग-अलग स्थानों की एक संख्या में रखा जा सकता है, विभिन्न वैक्टर की उपज।$v_{i,j}$ से मेल खाती है $j$वें स्थान जहां आकार $i$ रखा जा सकता है। $c$ ग्रिड में मूल रूप से संख्याओं से मेल खाती है (अच्छी तरह से, उन संख्याओं की उपेक्षा, मोडुलो $N$) का है। सभी अंकगणित को मोडुलो किया जाता है$N$।
थोड़ा चालाक जानवर बल
वैकल्पिक रूप से, यहां समय के लिए ट्रेडिंग मेमोरी के द्वारा ब्रूट बल को थोड़ा सुधारने का एक तरीका है। मान लो तुम्हारे पास है$k$आकार। पहले स्थान के लिए सभी तरीकों की गणना करके शुरू करें$k/2$सभी शून्य के एक खाली बोर्ड पर आकृतियाँ, और सभी परिणामी पदों को हैशटेब या सॉर्ट की गई सूची में संग्रहीत करें। फिर, अंतिम स्थान के लिए सभी तरीकों की गणना करें$k/2$प्रारंभिक स्थिति पर आकृतियाँ, और हैशटेबल या सॉर्ट की गई सूची में परिणामी पदों में से प्रत्येक को देखें। यदि आपको कोई मेल मिलता है, तो वह समाधान निकालता है। इससे आपको ब्रूट बल को थोड़ा और आगे बढ़ाने में मदद मिलेगी - संभावित रूप से लगभग दो बार - यदि आपके पास असीमित मात्रा में मेमोरी है। इसे अधिकतम करने के लिए इसमें बहुत सारे विवरण शामिल हैं, लेकिन यह एक ऐसा विचार है जिस पर आप विचार कर सकते हैं कि यदि आप क्रूरता के बल पर आप को पास लाते हैं, लेकिन थोड़ा कम हो जाता है। यह अभी भी एक घातांक-समय एल्गोरिथ्म है इसलिए यह अभी भी एक सीमा को हिट करेगा।