2010-03-02 7 views
6

मुझे पता है कि तत्वों के संयोजन उत्पन्न करने के लिए वहां कुछ प्रश्न हैं, लेकिन मुझे लगता है कि इस पर एक नया मोड़ होना एक नया मोड़ है:सबसे अधिक (गति) प्रभावी तरीके से अंक के सभी वैध संयोजन

मेरे पालतू जानवर प्रोजेक्ट के लिए मुझे बाद में एप्लिकेशन के रनटाइम व्यवहार को बेहतर बनाने के लिए बहुत सारी राज्यों की गणना करना है। जिन कदमों के साथ मैं संघर्ष करता हूं उनमें से एक यह है:

दो पूर्णांकों के एन टुपल्स को देखते हुए (उन्हें यहां से बिंदुओं को कॉल करने दें, हालांकि वे मेरे उपयोग के मामले में नहीं हैं। वे लगभग एक्स/वाई संबंधित हैं, हालांकि) किसी दिए गए नियम के लिए सभी वैध संयोजनों की गणना करने की आवश्यकता है।

  • की तरह कुछ

    नियम हो सकता है "हर बिंदु शामिल नहीं शामिल एक ही एक्स के साथ हर दूसरे बिंदु समन्वय"

  • "हर बिंदु शामिल शामिल नहीं एक अजीब एक्स के साथ हर दूसरे बिंदु समन्वय"

मुझे आशा है और उम्मीद है कि यह तथ्य चयन प्रक्रिया में सुधार की ओर अग्रसर है, लेकिन मेरे गणित कौशल को अभी भी पुनर्जीवित किया जा रहा है जैसा कि मैं टाइप करता हूं और मैं एक सुरुचिपूर्ण एल्गोरिदम के साथ आने में असमर्थ हूं।

  • अंक के सेट (एन) छोटे शुरू होता है, लेकिन जल्द ही 64 outgrows ("बिटमास्क रूप में लंबे समय का उपयोग करें" के लिए समाधान)
  • मैं सी # में यह कर रही है, लेकिन किसी भी भाषा में समाधान ठीक होना चाहिए अगर यह अंतर्निहित विचार

धन्यवाद बताता है।

Vlad के जवाब के जवाब में

अद्यतन:

शायद मेरे विचार प्रश्न सामान्यीकरण करने के लिए एक बुरा एक था। ऊपर मेरे नियमों का आविष्कार फ्लाई और बस प्लेसहोल्डर्स पर किया गया था। एक यथार्थवादी नियम इस प्रकार दिखाई देगा:

  • "हर बिंदु शामिल नहीं शामिल चुना बिंदु से ऊपर triagle में हर दूसरे बिंदु"

कि नियम से और चयन करके (2,1) मैं था को बाहर

  • (2,2) - सीधे
  • (1,3) (2,3) (3,3) ऊपर - अगली पंक्ति
  • और
  • इतने पर

तो नियम सामान्य हैं, सामान्य नहीं। वे दुर्भाग्य से एक्स/वाई नमूनों की तुलना में अधिक जटिल हैं जिन्हें मैंने शुरू में दिया था।

+0

यदि आप उन सभी वास्तविक नियमों को सूचीबद्ध कर सकते हैं जो आप उपयोग करने की योजना बना रहे हैं तो यह सहायक होगा। – Nixuz

उत्तर

0

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

आवंटित सामान्य नियमों के लिए मुझे शक है कि यह संभव है किसी भी एआई के बिना एक कुशल एल्गोरिदम का निर्माण।

+0

ठीक है, मेरे पास सामान्य नियम नहीं हैं (जैसा कि: प्रिय उपयोगकर्ता, कृपया फ्लाई पर अधिक आविष्कार करें)। अभी तक केवल कुछ निश्चित फिक्स्ड हैं। मैं पोस्ट को बेहतर और यथार्थवादी उदाहरण के साथ अपडेट करूंगा। –

+0

अद्यतन से नियम के लिए, निम्न एल्गोरिदम का उपयोग किया जा सकता है। आइए अस्थायी रूप से हमारे समन्वय प्रणाली को 45 डिग्री से घुमाएं। (अब हमारे त्रिकोणों में अक्षों के समानांतर पक्ष हैं।) जाहिर है कि कोई भी 2 बिंदु समान ऊर्ध्वाधर रेखा पर नहीं हो सकता है। इसके अलावा, यदि कोई बिंदु ए बिंदु बी के _left_ के लिए है, तो यह बी से _higher_ होना चाहिए। इसलिए हमारा नियम (1) मनमाने ढंग से लंबवत रेखाओं का चयन करना है (पुराने निर्देशांक में यह समानांतर विकर्ण रेखाओं के मनमाने ढंग से सेट होगा); (2) अवरोही क्रम में प्रत्येक पंक्ति पर एक बिंदु का चयन करें। (मान मनमाने ढंग से हो सकते हैं, केवल अवरोही क्रम महत्वपूर्ण है।) – Vlad

+0

जैसा कि आप देखते हैं, सरलीकृत नियम के लिए एल्गोरिदम पहले से ही जटिल है। अधिक जटिल नियमों के लिए यह और भी जटिल होगा, मुझे लगता है। – Vlad

0

समस्या की मेरी समझ यह है: bool property(Point x) const विधि को देखते हुए, सभी बिंदुओं को सेट करें, जिसके लिए संपत्ति() true है। क्या यह उचित है?

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

कुछ प्रकार की संपत्तियों के लिए, O(N) से सुधार करना संभव है बशर्ते उपयुक्त डेटा संरचना का उपयोग बिंदुओं को स्टोर करने के लिए किया जाता है और उपयुक्त पूर्व-गणना (जैसे सॉर्टिंग) किया जाता है। हालांकि, यह किसी भी मनमानी संपत्ति के लिए सच नहीं हो सकता है।

3

"प्रत्येक बिंदु के एक्स समन्वय को शामिल करने के बारे में अन्य शामिल बिंदुओं के वाई निर्देशांक के कुछ सबसेट का सटीक योग" है। यदि आप उस त्वरित बाधा समस्या के लिए एक तेज़ एल्गोरिदम के साथ आ सकते हैं तो आप वास्तव में बहुत प्रसिद्ध हो जाएंगे।

मेरा मुद्दा यह है कि कहा गया समस्या एनपी-पूर्ण या एनपी-हार्ड समस्याओं को स्वीकार करने के लिए इतनी अस्पष्ट है। बाधा अनुकूलन समस्याएं अविश्वसनीय रूप से कठिन हैं; यदि आप समस्या पर अत्यधिक तंग सीमा नहीं डाल सकते हैं तो यह बहुपद समय में मशीनों द्वारा विश्लेषण नहीं किया जा सकता है।

+0

उत्तर के लिए धन्यवाद। मैं फिर से अपने प्रश्न के बारे में पुनर्विचार करूँगा। मैंने विवरणों को पट्टी करने और समस्या के सामान्य समाधान के लिए पूछने की कोशिश की "वस्तुओं के एक सेट को देखते हुए, यदि मैं प्रत्येक पिक शेष सेट के हिस्से को समाप्त करता हूं तो मैं सभी संयोजनों को एक कुशल तरीके से कैसे गणना करूं"। शायद यह बहुत सामान्य है और मैं कुछ बेहतर, क्षमा करने की कोशिश करूंगा। –

संबंधित मुद्दे