समय के पेड़ प्रोग्रामिंग

परिचय

टाइमकोड के लेखों "टाइम ट्रैवल एंड प्रोग्रामिंग" [ 1, 2 ] को पढ़ने के बाद, मैंने ब्रांचिंग दुनिया के कार्यान्वयन से संबंधित प्रोग्रामिंग में अपने मामूली व्यावहारिक शोध को याद किया। एक बार मेरे काम करने वाले ने मुझे एक दिलचस्प समस्या बताई, लेकिन मैं अभी भी इसे हल नहीं कर पाया हूं। कार्य यह है कि उत्पादन में मशीनों को कैसे लोड किया जाए। प्रोग्रामर को यह भी स्पष्ट नहीं था कि एक सरल गणना की आवश्यकता थी, लेकिन मैं कम्प्यूटेशनल एल्गोरिदम प्रदान करने के लिए एक उपयुक्त डेटा संरचना के साथ नहीं आ सका। कार्य वास्तविक दुनिया से है, इसलिए मैंने उस भाग में कार्यक्रम में वास्तविक दुनिया को लागू करने का प्रयास करने का निर्णय लिया, जो कार्य की गणना करने के लिए आवश्यक है। हर बार, आगे की गणना में, दो कार्यों के बीच एक विकल्प था - प्रत्येक में एक अलग समाधान के साथ "दो नई दुनिया का निर्माण" था। इसके अलावा, प्रत्येक दुनिया ने अपने तरीके से विकास किया।

कट के तहत, मैं आपको बताता हूं कि विचार कैसे विकसित हुआ, और इरांग ने मेरी कैसे मदद की। अभ्यास सत्य की कसौटी है!

सामग्री

शब्दावली - समय का वृक्ष
पहली समस्याएं
जो पहले हो चुका है, उसे याद करें
विश्व अभिसरण
कार्यप्रणाली
चरण 1. दुनिया के किसी भी राज्य का विवरण टुप में रखें
चरण 2. उस फ़ंक्शन का वर्णन करें जो निर्धारित करता है कि दुनिया अपने लक्ष्य तक पहुंच गई है या नहीं
चरण 3. उस फ़ंक्शन का वर्णन करें जो यह निर्धारित करता है कि दुनिया को आगे विकास की आवश्यकता है या नहीं।
चरण 4. दुनिया के शाखापूर्ण कार्य का वर्णन करें
चरण 5. दुनिया का एचएसएच गणना कार्य बताएं
अन्य कार्य
संस्करण 1 रूपरेखा
समस्याओं के समाधान के लिए फ्रेमवर्क №1 का अनुप्रयोग
कागज के विभिन्न टुकड़ों के साथ 120 रूबल जारी करने के लिए विकल्पों की गणना
भाग्यशाली टिकटों की गणना
भाग्यशाली टिकटों की गणना, प्रयास संख्या 2
टास्क "वुल्फ, बकरी और गोभी"
हास्य का क्षण
निष्कर्ष
उपयोग किए गए स्रोतों की सूची

शब्दावली - समय का वृक्ष

गोलोवचेव विश्व इतिहास के विकास के ऐसे प्रतिनिधित्व को कहते हैं - ट्री ऑफ टाइम्स या एक भग्न [3]। इसके अलावा, मैं इस दृष्टिकोण का उपयोग करके परिणाम खोज विधि को "ट्री ऑफ़ टाइम्स विधि" कहूंगा।

दुनिया दुनिया के गुणों और उनके अर्थों की एक सूची है जो इसके राज्य का निर्धारण करती है।

समस्या को हल करना - ट्री ऑफ टाइम्स विधि द्वारा समस्या को हल करना, हम परिणाम को अग्रिम रूप से जानते हैं, या दुनिया के कुछ गुणों के मूल्य जो हम प्राप्त करना चाहते हैं। यही है, हम परिणाम जानते हैं, लेकिन इसे प्राप्त करने का तरीका अज्ञात है। समस्या का समाधान रास्ता ढूंढ रहा है।

प्रारंभिक दुनिया एक संदर्भ बिंदु है, वह दुनिया जहां से हम समस्या को हल करने में अपनी यात्रा शुरू करते हैं।

लक्ष्य दुनिया वह दुनिया (या बल्कि, उसकी अवस्था) है जिससे हम समस्या को हल करने का प्रयास करते हैं।

दुनिया का विकास - प्रारंभिक दुनिया का विकास, हम लक्ष्य दुनिया को प्राप्त करने का प्रयास करते हैं।

एक मृत अंत दुनिया एक मृत अंत शाखा नहीं है, लेकिन एक मृत अंत दुनिया है। यह एक ऐसी दुनिया है जिसके आगे विकास से लक्ष्य दुनिया नहीं बनेगी।

पहली समस्याएं

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

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

इस प्रकार, ट्री ऑफ टाइम्स विधि का उपयोग करके गणना में, निम्नलिखित समस्याओं को हल करने की आवश्यकता है:

• वास्तविकताओं के माइंडलेस समानांतरकरण को सीमित करें क्योंकि संसाधन सीमित हैं
• परिणाम प्राप्त करने के लिए पथ का विश्लेषण करने के लिए, यदि हम दुनिया में "कठिन" तरीके से या ऐसे तरीके से पहुँचे हैं, जिसकी हमें ज़रूरत नहीं है, तो आगे मत जाओ
• डुप्लिकेट परिणामों के साथ कुछ करने की आवश्यकता है। वास्तव में, अलग-अलग दुनिया अलग-अलग तरीकों से एक ही राज्य में आ सकती है - इसके बारे में क्या करना है?

लंबे समय से "ट्री ऑफ़ टाइम्स पद्धति" का उपयोग करके परिणामों की गणना का लंबा इतिहास "मेरी मेज" में पड़ा हुआ था। क्योंकि सभी कंप्यूटिंग समस्याओं का समाधान नहीं किया गया है। हां, और यह स्पष्ट है कि समानांतर कंप्यूटिंग को लागू करने का समय, नई, उन प्रोग्रामिंग भाषाओं से अलग है जिनसे मैं परिचित हूं। लेकिन कोई सरल उपाय नहीं थे।

जैसे-जैसे समय बीत रहा है, प्रोग्रामिंग के क्षेत्र में प्रौद्योगिकी विकसित हो रही है। यह स्पष्ट हो गया कि मेगाहर्ट्ज़ को उठाना असीम रूप से असंभव है। गणनाओं को समानांतर करना आवश्यक है। और ऐसे अवसर दिखाई देने लगे, भाषाओं में समानता के लिए समर्थन सरल होने लगा।

लेकिन दुनिया के क्लोन के बारे में क्या? मृत केंद्र से मामला टाइमकोड लेख स्थानांतरित कर दिया। एक को न केवल दुनिया के विकास की शाखाओं को अलग करने में सक्षम होना चाहिए, बल्कि उन्हें एक साथ जोड़ना होगा।

नए नए विचारों और उपकरणों के साथ सशस्त्र, मैंने टाइम ऑफ़ ट्रीज़ की खोज करने के लिए लौटने का फैसला किया।

जो पहले हो चुका है, उसे याद करें

चुनौती भाग्यशाली टिकट है। एक टिकट को भाग्यशाली माना जाएगा यदि इसमें पहले तीन अंकों का योग बाकी के योग के बराबर हो।


परिणाम इस प्रकार था:

 000000 200002 100001 200002 200002 100001 200002 200002 200002 

एल्गोरिथ्म किसी भी अनुकूलन से नहीं गुजरा है। विशेष रूप से सोचा नहीं गया। और संबंधित परिणाम युगल है।

कार्य पैसे का आदान-प्रदान करना है। 1000, 500, 100, 50, 10 रूबल के बिल होने दें। जारी करने के लिए विकल्पों की गणना करना आवश्यक है।


जाहिर है, आपको किसी तरह डुप्लिकेट (समान दुनिया) को अनदेखा करने की आवश्यकता है। सही प्रोग्रामिंग के लिए प्रशिक्षित मस्तिष्क तुरंत सोचने लगता है कि एल्गोरिथ्म का अनुकूलन कैसे किया जाए ताकि ऐसा न हो, अनुकूलन, अनुकूलन ... वास्तव में, यह एक बहुत ही सरल उदाहरण है, लेकिन यहां तक ​​कि अनुकूलन के साथ आना मुश्किल हो जाता है। और अधिक जटिल दुनिया में क्या होगा? सामान्य तौर पर, यदि ऐसा कोई अवसर है, तो स्पष्ट रूप से शानदार दुनिया का उत्पादन करना आवश्यक नहीं है, अन्य सभी मामलों में दुनिया को परिवर्तित करने के लिए तरीकों का आविष्कार करना आवश्यक है।

विश्व अभिसरण

आइए यह जाँचने का प्रयास करें कि क्या ऐसा है। यदि है, तो और कुछ नहीं (बच्चे की दुनिया नहीं बनाते हैं)।

हम किस दुनिया में हैं, इसका विश्लेषण करने के लिए, हम निष्कर्ष पर चर्चा करेंगे कि क्या हमने पाया है और अगर नहीं। सभी स्थितियों में, गणना की मात्रा को सीमित करने के लिए <10 को <2 के साथ बदलें। चलाएँ। परिणाम:

कुल 64 लाइनें हैं, अर्थात् 2 ^ 6, यह सच है। पूर्ण में, एल्गोरिथ्म तेजी से काम करता है, लगभग 155ms। QtConcurect offhand का उपयोग करके समानांतर करना संभव नहीं था।

लेकिन एर्लांग के बारे में क्या?

कार्य समान है - टिकटों के माध्यम से छंटनी। लेकिन एर्लांग में कोई वैश्विक चर नहीं हैं।


एर्लैंग के रूप में नई तकनीकों से हमने क्या किया? अब तक कुछ भी नहीं:

• C ++ qt से अधिक लंबा माना जाता है
• कोई समानांतर और बहु-मशीन कंप्यूटिंग नहीं हैं
• एफपी में निहित कोई सुरुचिपूर्ण और कॉम्पैक्ट कोड नहीं है, इसके बजाय, एक ही प्रकार के कोड की शीट
• एक पूरे के रूप में, एक पुनरावर्ती फ़ंक्शन ने मूल्यों की एक सरल गणना को हल किया, जो प्रक्रियात्मक भाषाओं में चक्रों द्वारा आसान और अधिक स्पष्ट रूप से हल किया जाता है। हर कोई रिकर्सन को नहीं समझता और प्यार करता है

क्या करें? एक कार्यप्रणाली की आवश्यकता है! सरल, कदम से कदम, एक छात्र के लिए भी समझ में आता है।

कार्यप्रणाली

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

यह क्या देता है? प्रत्येक व्यवहार एक सरल और सीधा कार्य है। एक शुद्ध कार्य, जिसका परिणाम केवल इनपुट डेटा पर निर्भर करता है। यह दूसरों की स्वतंत्र रूप से जाँच की जा सकती है।

इस प्रकार, एक रूपरेखा संस्करण 1 दिखाई दिया। समस्या को हल करने के लिए, आपको चरणों के माध्यम से जाने की आवश्यकता है

चरण 1. दुनिया के किसी भी राज्य का विवरण टुप में रखें

ट्रीज़ ऑफ़ टाइम के लिए प्रोग्रामिंग गणनाओं में एक महत्वपूर्ण बिंदु यह है कि दुनिया के विवरण को कैसे संग्रहीत किया जाए। कल्पना में "दुनिया का मैट्रिक्स" क्या कहा जाता है। दुनिया के वर्णन में इस समय दुनिया की स्थिति के बारे में जानकारी शामिल है, लेकिन केवल उसी की आवश्यकता है।

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

विश्व विवरण समझौता: दुनिया का वर्णन एक टपल में किया जाना चाहिए।

टुपल सीमित लंबाई के मूल्यों का एक समूह है। टुपल घुंघराले ब्रेसिज़ तक सीमित है, और टपल के तत्व एक-दूसरे से अल्पविराम द्वारा अलग हो जाते हैं। टुपल्स को एक दूसरे में घोंसला बनाया जा सकता है।

उदाहरण 1. भाग्यशाली टिकटों के विकल्पों की गणना करते समय शुरुआती समय में दुनिया की स्थिति का वर्णन करने वाला एक टपल।

 {0,0,0,0,0,0} 

टिकट संख्या में प्रत्येक अंक एक अलग अंक है।

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

उदाहरण 2. दुनिया की स्थिति का वर्णन करने वाला एक टपल, जिसमें हमें 1x100r और 2x10r के रूप में 120 रूबल जारी करने का एक तरीका मिला। हमारे पास पांच प्रकार के बैंकनोट हैं: 1000, 500, 100, 50, 10. इसलिए, दुनिया के पांच पैरामीटर होंगे। यह तय किया गया था कि वे अधिक से कम का पालन करेंगे, अर्थात्, पहली संख्या 1000 रूबल की संख्या है, आदि।

 {0,0,1,0,2} 

चरण 2. उस फ़ंक्शन का वर्णन करें जो निर्धारित करता है कि दुनिया अपने लक्ष्य तक पहुंच गई है या नहीं

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

चरण 3. उस फ़ंक्शन का वर्णन करें जो यह निर्धारित करता है कि दुनिया को आगे विकास की आवश्यकता है या नहीं।

फ़ंक्शन को दुनिया के लिए एक पैरामीटर के रूप में पारित किया जाता है। उसका काम यह निर्धारित करना है कि इसे और विकसित करना है या नहीं। अगर दुनिया का आगे विकास एक लक्ष्य के लिए नहीं हो सकता है, तो इसे और विकसित करने का कोई मतलब नहीं है। डेड एंड ब्रांच। यदि विकास की आवश्यकता है, तो true लौटें। अन्यथा false । उसी समय, यदि दुनिया का आगे विकास एक मृत अंत है, इसका मतलब यह नहीं है कि दुनिया को लक्षित नहीं किया जा सकता है।

चरण 4. दुनिया के शाखापूर्ण कार्य का वर्णन करें

दुनिया का विकास विभिन्न दिशाओं में जा सकता है। फ़ंक्शन को दुनिया के लिए एक पैरामीटर के रूप में पारित किया जाता है। जवाब में, दुनिया की एक सूची जिसमें आप इस दुनिया से विकसित कर सकते हैं जारी की जाती है।

चरण 5. दुनिया का एचएसएच गणना कार्य बताएं

डिफ़ॉल्ट रूप से, विश्व एचएएसएच गणना समारोह निम्नानुसार है:

 %%  w2hash(Wrld) -> erlang:phash2(Wrld). 

मानक erlang:phash2 फ़ंक्शन erlang:phash2 एक हैश erlang:phash2 है - संचरित ट्यूपल से संख्या। लेकिन एक दुनिया से दूसरी दुनिया के सटीक पत्राचार की हमेशा आवश्यकता नहीं होती है। यह लेख [1, 2] में लिखा गया था, लब्बोलुआब यह है कि कोई फर्क नहीं पड़ता कि मध्यवर्ती निर्णय क्या थे, आप एक परिणाम पर आ सकते हैं और विकास की शाखाएं परिवर्तित हो जाएंगी। दुनिया "परमाणु तक नहीं" को परिवर्तित करती है, लेकिन समस्या को हल करने के संदर्भ में अभिसरण करती है। यदि कार से काम करना है, तो आप अलग-अलग सड़कों से आ सकते हैं, लेकिन 12 बजे हम बैठक में शामिल होंगे। बेशक, अंतर कार के माइलेज में होगा, लेकिन यह क्षण हमारे लिए कोई मायने नहीं रखता।

फ्रेमवर्क नंबर 1 में दुनिया के अभिसरण को पहले से निर्मित दुनिया के भंडार के माध्यम से लागू किया गया है। बल्कि, इन दुनिया के हैश नंबर। और अगर किसी शाखा के विकास के दौरान हमने जो दुनिया में प्रवेश किया है, वह पहले से ही भंडार में मौजूद है, तो दुनिया का और विकास नहीं होता है। वास्तव में, दुनियाएं अभिसरण हो जाती हैं, क्योंकि दुनिया के विकास के दो रास्ते एक ही परिणाम पर आए और आगे भी उसी तरह चले गए। इसलिए, यदि दुनिया का कोई भी पैरामीटर परिणाम को प्रभावित नहीं करता है, तो आपको दुनिया के हैश की गणना करने के कार्य को समायोजित करने की आवश्यकता है ताकि यह पैरामीटर tuple-> हैश संख्या के रूपांतरण में भाग न ले।

अन्य कार्य

गणन, संसार, संसार के अभिसरण जैसे कार्य किसी भी कार्य के लिए समान होंगे। उन्हें रूपरेखा में शामिल किया जाएगा और उपयोगकर्ता को उन्हें बदलने / समझने की आवश्यकता नहीं है। और यदि आप कड़ाई से कार्यप्रणाली का पालन करते हैं, तो दुनिया के नियमों को परिभाषित करने वाले कार्यों को बदलने के बिना समानांतर कंप्यूटिंग के संदर्भ में रूपरेखा में सुधार किया जा सकता है।

संस्करण 1 की रूपरेखा

समस्याओं के समाधान के लिए फ्रेमवर्क №1 का अनुप्रयोग

कागज के विभिन्न टुकड़ों के साथ 120 रूबल जारी करने के लिए विकल्पों की गणना

चरण 1 - एक टपल में दुनिया को रखना

दुनिया पांच अंकों में वर्णित है।

 {0,0,0,0,0} 

चरण 2. उस फ़ंक्शन का वर्णन करें जो निर्धारित करता है कि दुनिया अपने लक्ष्य तक पहुंच गई है या नहीं

 %%  ? is_target(Wrld) -> {X1000,X500,X100,X50,X10} = Wrld, if ((X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)==120) -> io:format("120 (~w) = 1000p*~w 500p*~w 100p*~w 50p*~w 10p*~w~n", [X1000+X500+X100+X50+X10,X1000,X500,X100,X50,X10]); true -> ok end, (X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)==120. 

Erlang सिंटैक्स पर एक छोटा नोट। बहुत पहले ऑपरेशन एक असाइनमेंट नहीं है, लेकिन एक मैच है। Wrld वेरिएबल Wrld पाँच तत्वों वाला Wrld टपल Wrld । जब ऑपरेशन किया जाता है, तो ट्यूपल में तत्वों के मूल्यों को चर X1000, X500, X100, X50, X10 को सौंपा जाता है। एर्लांग में मैच के बारे में अधिक जानकारी, कृपया अपने दम पर पढ़ें। या बस सिंटैक्स को स्वीकार करें जैसे कि टुप से मान खींचने के लिए।

चरण 3. उस फ़ंक्शन का वर्णन करें जो यह निर्धारित करता है कि दुनिया को आगे विकास की आवश्यकता है या नहीं।

 %% -   is_dead(Wrld) -> {X1000,X500,X100,X50,X10} = Wrld, (X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)>120. 

चरण 4. दुनिया के शाखापूर्ण कार्य का वर्णन करें

 %%  br(Wrld) -> {X1000,X500,X100,X50,X10} = Wrld, [ {X1000+1,X500,X100,X50,X10}, {X1000,X500+1,X100,X50,X10}, {X1000,X500,X100+1,X50,X10}, {X1000,X500,X100,X50+1,X10}, {X1000,X500,X100,X50,X10+1} ]. 

गणना प्रारंभ

 %%  start() -> register(lib_srv, spawn(?MODULE, lib, [])), io:format("start~n", []), %%  []     spawn(?MODULE, ent, [{0,0,0,0,0}]). 

परिणामस्वरूप, हमने प्राप्त किया:

 1> c(wf1). {ok,wf1} 2> wf1:start(). start <0.455.0> 120 (3) = 1000x0 500x0 100x1 50x0 10x2 120 (4) = 1000x0 500x0 100x0 50x2 10x2 120 (8) = 1000x0 500x0 100x0 50x1 10x7 120 (12) = 1000x0 500x0 100x0 50x0 10x12 

भाग्यशाली टिकटों की गणना

चरण 1 - एक टपल में दुनिया को रखना

दुनिया को छह अंकों में वर्णित किया गया है।

 {0,0,0,0,0,0} 

चरण 2. उस फ़ंक्शन का वर्णन करें जो निर्धारित करता है कि दुनिया अपने लक्ष्य तक पहुंच गई है या नहीं

 %%  ? is_target(Wrld) -> {X1,X2,X3,X4,X5,X6} = Wrld, if ((X1+X2+X3)==(X4+X5+X6)) -> cnt_srv ! inc, cnt_srv ! {cnt, self()}, receive X -> ok end, io:format("~w ~w ~w ~w ~w ~w (~w)~n", [X1,X2,X3,X4,X5,X6, X]); true -> ok end, ((X1+X2+X3)==(X4+X5+X6)). 

चरण 3. उस फ़ंक्शन का वर्णन करें जो यह निर्धारित करता है कि दुनिया को आगे विकास की आवश्यकता है या नहीं।

 %% -   is_dead(Wrld) -> {X1,X2,X3,X4,X5,X6} = Wrld, if (X1>9)-> true; (X2>9)-> true; (X3>9)-> true; (X4>9)-> true; (X5>9)-> true; (X6>9)-> true; true -> false end. 

चरण 4. दुनिया के शाखापूर्ण कार्य का वर्णन करें

 %%  br(Wrld) -> {X1,X2,X3,X4,X5,X6} = Wrld, [ {X1+1,X2,X3,X4,X5,X6}, {X1,X2+1,X3,X4,X5,X6}, {X1,X2,X3+1,X4,X5,X6}, {X1,X2,X3,X4+1,X5,X6}, {X1,X2,X3,X4,X5+1,X6}, {X1,X2,X3,X4,X5,X6+1} ]. 

खुश टिकटों की संख्या की गणना करने के लिए, हम एक और सर्वर बनाएंगे जो सकारात्मक परिणाम के साथ संसार की संख्या को संग्रहित, बढ़ाएगा और देगा:

 %%-  cnt() -> cnt(0). cnt(N) -> receive inc -> cnt(N+1); {cnt,Pid} -> Pid ! N, cnt(N) end. 

जब आप गणना शुरू करते हैं, तो हम इसे भी शुरू करते हैं:

 %%  start() -> register(lib_srv, spawn(?MODULE, lib, [])), register(cnt_srv, spawn(?MODULE, cnt, [])), io:format("start~n", []), %%  []     spawn(?MODULE, ent, [{0,0,0,0,0,0}]). 

लेकिन अगर आप इस तरह से नियम निर्धारित करते हैं, तो आपको परिणाम के लिए लंबा इंतजार करना होगा। इतनी सारी प्रक्रियाएँ बनाई जाती हैं कि एर्लांग नोड इतने से निपटना बंद कर देता है और नई प्रक्रियाएँ बनाना बंद कर देता है। और यह अच्छा है, क्योंकि मुझे इस समस्या का हल ढूंढना था (कोशिश के माध्यम से)।

जाहिर है, दुनिया की शाखाओं को सबसे अच्छे तरीके से सेट नहीं किया जाता है और यह पता चलता है कि एक ही दुनिया कई बार बनाई जाती है, चेक लगातार चल रहे हैं और यह पता चला है कि दुनिया पहले से मौजूद है। इससे पता चलता है कि ऐसे मांगलिक कार्यों में आपको अभी भी मस्तिष्क का उपयोग करना है।

भाग्यशाली टिकटों की गणना, प्रयास संख्या 2

खुश टिकटों की समस्या का समाधान बहुत उपयोगी निकला। हल करने की प्रक्रिया में, प्रत्येक चरण के लिए बहुत महत्वपूर्ण बारीकियों को पाया गया था, और दुनिया के प्रसंस्करण के मुख्य चक्र को समायोजन की आवश्यकता थी। और यहां तक ​​कि चरण संख्या 5 (जो मूल रूप से नहीं था) की आवश्यकता का पता चला था।

टिकटों के साथ समस्या को हल करने के पिछले प्रयास ने हमें दिखाया कि हम प्रभावी रूप से दुनिया की शाखा नहीं लगाते हैं, जिसके कारण बड़ी संख्या में ले जाता है। लेकिन प्रारंभिक अवस्था से तुरंत दुनिया के विकास के सभी विकल्पों की गणना करने में कोई समस्या नहीं है। लेकिन हमारे पास एर्लांग है, इसलिए हम इसे पुनरावर्ती रूप से करेंगे, खंड को आधा में विभाजित करके। खंड 0 से 999999 तक का होगा, हम इसे तब तक विभाजित करेंगे जब तक कि पर्वतमाला की सीमाएं मेल नहीं खातीं। इसलिए, दुनिया के गुण दो और हो जाएंगे: बाईं और दाईं सीमाएं जुड़ जाएंगी। इसी समय, इन सीमाओं की आवश्यकता केवल दुनिया की सूची की गणना के पुनरावर्ती कार्य के लिए होती है और परिणाम से प्रभावित नहीं होती है। इसके अलावा, आधे हिस्से में खंड का विभाजन पूर्णांक है और कहीं एल्गोरिथ्म में मैंने एक गलती की है जो हमें अलग-अलग खंडों पर समान दुनिया देती है। इसलिए, दुनिया के हैश की गणना के लिए एक समायोजन की आवश्यकता होगी।

चरण 1 - एक टपल में दुनिया को रखना

पहले दो पैरामीटर रेंज हैं। बाकी सब पहले जैसा ही है।

 {0,999999,0,0,0,0,0,0} 

चरण 2. उस फ़ंक्शन का वर्णन करें जो निर्धारित करता है कि दुनिया अपने लक्ष्य तक पहुंच गई है या नहीं

 %%  ? is_target(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, if ((X1+X2+X3)==(X4+X5+X6)) -> cnt_srv ! inc, cnt_srv ! {cnt, self()}, receive X -> ok end, io:format("~w ~w ~w ~w ~w ~w (~w)~n", [X1,X2,X3,X4,X5,X6, X]); true -> ok end, ((X1+X2+X3)==(X4+X5+X6)). 

चरण 3. उस फ़ंक्शन का वर्णन करें जो यह निर्धारित करता है कि दुनिया को आगे विकास की आवश्यकता है या नहीं।

गणना के इस संस्करण में दुनिया के विकास को माना नहीं जाता है, क्योंकि हम तुरंत सभी विकास विकल्पों को जानते हैं। यही है, विकास का केवल एक ही चरण है - पहला चरण, जब 0 - 999999 की सीमा का संकेत दिया जाता है। जब हमारी सूची में सीमा रखी जाती है, तो दुनिया का विकास नहीं होना चाहिए। दुनिया हमेशा एक मृत अंत है, पहले चरण को छोड़कर।

 %% -   is_dead(Wrld) -> {St_d,En_d,_X1,_X2,_X3,_X4,_X5,_X6} = Wrld, (St_d == En_d). 

चरण 4. दुनिया के शाखापूर्ण कार्य का वर्णन करें

 %%  br(Wrld) -> {St_d,En_d,X1,X2,X3,X4,X5,X6} = Wrld, THalf = round((St_d + En_d) / 2), if (St_d == En_d) -> []; ((En_d - St_d) == 1) -> XX6 = En_d rem 10, XX5 = trunc((En_d rem 100)/10), XX4 = trunc((En_d rem 1000)/100), XX3 = trunc((En_d rem 10000)/1000), XX2 = trunc((En_d rem 100000)/10000), XX1 = trunc((En_d rem 1000000)/100000), [{St_d,St_d,XX1,XX2,XX3,XX4,XX5,XX6}] ++ [{En_d,En_d,XX1,XX2,XX3,XX4,XX5,XX6}]; true -> br({St_d,THalf,X1,X2,X3,X4,X5,X6}) ++ br({THalf,En_d,X1,X2,X3,X4,X5,X6}) end. 

चरण 5. दुनिया के एचएएसएच के कार्य का वर्णन करें

 %%  w2hash(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, X1*100000 + X2*10000 + X3*1000 + X4*100 + X5*10 + X6. 

या आप एक टपल इकट्ठा कर सकते हैं, लेकिन एक सीमा के बिना

 %%  w2hash(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, erlang:phash2({X1,X2,X3,X4,X5,X6}). 

लांच

 %%  start() -> register(lib_srv, spawn(?MODULE, lib, [])), register(cnt_srv, spawn(?MODULE, cnt, [])), io:format("start~n", []), %%  []     spawn(?MODULE, ent, [{0,999999,0,0,0,0,0,0}]). 

परिणाम

निष्पादन की प्रक्रिया में, कार्यक्रम ने भाग्यशाली टिकटों की एक सूची जारी की, जो 55252 हो गए। यह निकला , चियर्स !!!



परिणाम की गणना करने का समय खुश नहीं है: 16:49 पर गणना शुरू की, और 17:23 पर समाप्त हुई। यह 30 मिनट से अधिक है। लेकिन टिकट की समस्या का क्या समाधान हुआ और इसे दूर करना पड़ा? सबसे पहले, यह भंडारण में एक मिलियन दुनिया है। प्रारंभ में, मैंने रिपॉजिटरी में विश्व हैश रिकॉर्ड नहीं किया था, लेकिन दुनिया के सीधे tuples। जब आप बहुत सारी प्रविष्टियों वाली सूची में खोज करते हैं, तो हम पहले से ही बड़ी देरी का सामना कर रहे हैं। हैश का उपयोग करने से गति बढ़ गई है। और चरण 5 में विचारों ने हैश के उपयोग की शुद्धता की भी पुष्टि की। यद्यपि, सिद्धांत रूप में, आप दुनिया के एक टपल को स्टोर कर सकते हैं, लेकिन ऐसी जानकारी को हटाकर जो इससे सार्थक नहीं है। इसके अलावा, वर्तमान वास्तुकला से पता चलता है कि उत्पादकता के मामले में गुणात्मक वृद्धि के लिए अभी भी भंडार हैं, क्योंकि जिन दुनिया की गणना करने की आवश्यकता है, उन्हें एक सरणी में दिया गया है और दुनिया के एक सरणी के तत्वों की गणना समानांतर में, कई एरलंग नोड्स पर की जा सकती है।सभी विश्व गणनाओं को हर बार एक नई प्रक्रिया में लॉन्च किया जाता है। और सैद्धांतिक रूप से, आप Erlang वर्चुअल मशीन में अधिकतम संख्या में प्रक्रियाएं प्राप्त कर सकते हैं, जिससे त्रुटि हो सकती है। प्रतिबंध की "रन" करने की अनुमति टिकटों की गणना, त्रुटि को संसाधित करें और सुनिश्चित करें कि परिणाम सही है।

टास्क "वुल्फ, बकरी और गोभी"

“किसान को नदी के पार भेड़िये, बकरी और गोभी के परिवहन की आवश्यकता होती है। लेकिन नाव ऐसी है कि केवल एक किसान इसमें फिट हो सकता है, और इसके साथ या तो एक भेड़िया, या एक बकरी, या एक गोभी है। लेकिन अगर आप भेड़िये को बकरी के साथ छोड़ देते हैं, तो भेड़िये बकरी को खा जाएंगे, और अगर आप बकरी को गोभी के साथ छोड़ देंगे, तो बकरी गोभी खाएगी। किसान ने अपने माल को कैसे पहुँचाया? ”

कार्य के बारे में और साथ ही इसे हल करने के बारे में दो विकल्प यहाँ पाए जा सकते हैं [7]।

चरण 1: दुनिया के किसी भी राज्य का विवरण मोटरसाइकिल में रखें

जहां ( r- दाएं, lबाएं) - किनारे पर जिस पर दादा, बकरी, भेड़िया, गोभी और पिछला रास्ता ([] एक सूची है)। के लिए सूची क्या है? आखिरकार, हमें यह जानने की जरूरत है कि हम किस तरह से परिणाम में आए।

 {{ded,r},{koza,r},{volk,r},{kapusta,r},[]} 

चरण 2. उस फ़ंक्शन का वर्णन करें जो निर्धारित करता है कि दुनिया अपने लक्ष्य तक पहुंच गई है या नहीं

 %%  ? is_target(Wrld) -> {{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld, if ((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)) -> cnt_srv ! inc, cnt_srv ! {cnt, self()}, receive X -> ok end, io:format("~w) movs=~w ~w ~n", [X, length(History),History]); true -> ok end, ((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)). 

यही है, अगर सब कुछ सही बैंक पर है - समस्या हल हो गई है।

चरण 3. उस फ़ंक्शन का वर्णन करें जो यह निर्धारित करता है कि क्या दुनिया को और विकास की आवश्यकता है।

 %% -   is_dead(Wrld) -> {{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld, if (length(History) > 8) -> true; ((KozaBereg==VolkBereg)and(DedBereg/=KozaBereg)) -> true; %%  ,      ((KozaBereg==KapustaBereg)and(DedBereg/=KozaBereg)) -> true; %%  ,      true -> false end. 

यदि दादाजी बहुत लंबे समय तक काम करते हैं, तो यह एक मृत अंत है।

यदि बकरी पर शोर मचता है और भेड़िया इत्तेफाक रखता है, और उनके पास कोई दादा नहीं है (दादा दूसरी तरफ), तो भेड़िया बकरी को खा जाता है।

यदि बकरी और गोभी के किनारे मेल खाते हैं, और उनके पास कोई दादा (दूसरी तरफ दादा) नहीं है, तो बकरी गोभी खाती है।

अन्य मामलों में, आप भविष्य के लिए जी सकते हैं और आशा कर सकते हैं।

चरण 4. दुनिया को शाखाओं में लेने के कार्य का वर्णन करें।

यहां, यह तुरंत काम नहीं किया, क्योंकि मैंने स्मार्ट और सरलीकृत होने का फैसला किया। और आपको कुछ भी सरल करने की आवश्यकता नहीं है। हमें इसे वैसे ही करना चाहिए जैसे कि - ऐसा है।

पहले मैं एक फ़ंक्शन लिखूंगा जो पारित बैंक से विपरीत बैंक लौटाता है (यह हमारे लिए उपयोगी होगा)

 na_drugoi_bereg(l) -> r; na_drugoi_bereg(r) -> l. 

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

 %%  br(Wrld) -> {{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld, NewHistory = History ++ [{{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg}}], %% ,        %%          ,        %%   ,    %%  -  ,     if (DedBereg==KozaBereg) -> Variant1 = {{ded,na_drugoi_bereg(DedBereg)},{koza,na_drugoi_bereg(KozaBereg)},{volk,VolkBereg},{kapusta,KapustaBereg},NewHistory}; true -> Variant1 = [] end, %%  -  ,     if (DedBereg==VolkBereg) -> Variant2 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,na_drugoi_bereg(VolkBereg)},{kapusta,KapustaBereg},NewHistory}; true -> Variant2 = [] end, %%  -  ,     if (DedBereg==KapustaBereg) -> Variant3 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,VolkBereg},{kapusta,na_drugoi_bereg(KapustaBereg)},NewHistory}; true -> Variant3 = [] end, %%   -   -    Variant4 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},NewHistory}, %%     [Variant1]++[Variant2]++[Variant3]++[Variant4]. 

चरण 5.

दुनिया के एचएएसएच की गणना के कार्य का वर्णन करें । दुनिया का मानक एचएएसएच हमारे लिए काफी उपयुक्त है।

 %%  w2hash(Wrld) -> erlang:phash2(Wrld). 

और अगर हम केवल परिणामी दुनिया के हैश की गणना करते हैं? हां, उसे, सामान्य रूप से, जरूरत नहीं है। परिणाम हम पहले से ही जानते हैं - सब कुछ सही बैंक पर है। पथ हमारे लिए महत्वपूर्ण है - इतिहास की सरणी का मूल्य। इसलिए, दुनिया के हैश की गणना करने से पहले, इससे कुछ निकालने का कोई मतलब नहीं है।

लांच

 %%  start() -> register(lib_srv, spawn(?MODULE, lib, [])), register(cnt_srv, spawn(?MODULE, cnt, [])), io:format("start~n", []), %%  []     spawn(?MODULE, ent, [{{ded,l},{koza,l},{volk,l},{kapusta,l},[]}]). 

परिणाम का विश्लेषण

नदी के पार दादाजी के आंदोलनों की संख्या में, समस्या को हल करने के लिए कई विकल्प हैं। उनमें से, सबसे छोटे निर्णय 7 आंदोलनों में हैं। दो ऐसे समाधान हैं, जैसा कि वे लेख [ 7 ] में लिखे गए हैं ।

 1) movs=7 [ {{ded,l},{koza,l},{volk,l},{kapusta,l}}, -     {{ded,r},{koza,r},{volk,l},{kapusta,l}}, -      {{ded,l},{koza,r},{volk,l},{kapusta,l}}, -     {{ded,r},{koza,r},{volk,r},{kapusta,l}}, -      {{ded,l},{koza,l},{volk,r},{kapusta,l}}, -        {{ded,r},{koza,l},{volk,r},{kapusta,r}}, -      {{ded,l},{koza,l},{volk,r},{kapusta,r}}] -      ,       

 5) movs=7 [ {{ded,l},{koza,l},{volk,l},{kapusta,l}}, -     {{ded,r},{koza,r},{volk,l},{kapusta,l}}, -      {{ded,l},{koza,r},{volk,l},{kapusta,l}}, -     {{ded,r},{koza,r},{volk,l},{kapusta,r}}, -      {{ded,l},{koza,l},{volk,l},{kapusta,r}}, -        {{ded,r},{koza,l},{volk,r},{kapusta,r}}, -      {{ded,l},{koza,l},{volk,r},{kapusta,r}}] -      ,       

अन्य विकल्पों में अधिक आंदोलनों की आवश्यकता होती है, लेकिन यह स्पष्ट है कि ये शरीर की गतिविधियाँ निरर्थक होंगी:

 2) movs=9 [ {{ded,l},{koza,l},{volk,l},{kapusta,l}}, -     {{ded,r},{koza,r},{volk,l},{kapusta,l}}, -      {{ded,l},{koza,r},{volk,l},{kapusta,l}}, -     {{ded,r},{koza,r},{volk,r},{kapusta,l}}, -      {{ded,l},{koza,l},{volk,r},{kapusta,l}}, -       {{ded,r},{koza,l},{volk,r},{kapusta,r}}, -      {{ded,l},{koza,l},{volk,r},{kapusta,l}}, -      {{ded,r},{koza,l},{volk,r},{kapusta,r}}, -        {{ded,l},{koza,l},{volk,r},{kapusta,r}}] -    

हास्य का क्षण

चित्र - ट्री ऑफ़ टाइम्स पद्धति का चित्रण।


भेड़िये, बकरी और गोभी के बारे में समस्या का अमेरिकी संस्करण।

निष्कर्ष

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

विधि की आलोचना।
गणितीय दृष्टिकोण से यह विधि अवैज्ञानिक है। समस्याओं को हल करने के लिए, उदाहरण के लिए, उत्पादन लोडिंग पर, मास सर्विस थ्योरी आदि को लागू किया जा सकता है। विधि का सार विकल्पों की गणना है ("जानवर बल" विधि), जो अर्थहीन रूप से विशाल कम्प्यूटेशनल संसाधनों को खर्च कर रहा है और यदि कम्प्यूटेशनल डोमेन सीमित रूप से सीमित है तो इसका समाधान नहीं मिल सकता है। हालांकि, विकिपीडिया ने क्रूरता को गणितीय समस्याओं को हल करने का एक तरीका माना है ।

आगे का विकास
क्लस्टर कंप्यूटिंग। एर्लैंग पूल के साथ प्रयोग।

समस्याओं के एक अन्य वर्ग को हल करने के लिए एक फ्रेम नंबर 2 का विकास, जब एक पेड़ पहली बार बनाया जाता है, और फिर इसके लिए समाधान पाए जाते हैं। उदाहरण के लिए, टिक टीएसी पैर की अंगुली के कार्यान्वयन के लिए एआई। उसके लिए, जीत की ओर खेल में किसी भी संभावित संयोजन से एक पेड़ बनाया जाता है। जब खेल की बारी सेट होती है, AI पेड़ में दुनिया को पाता है, तो विकास शाखाओं में से एक का चयन करता है, जो दुनिया को जीतने वाली लक्ष्य दुनिया तक ले जाएगा और उचित कदम उठाएगा।

उपयोग किए गए स्रोतों की सूची

1. यात्रा समय और प्रोग्रामिंग के माध्यम से - habrahabr.ru/post/150300
2. यात्रा समय और प्रोग्रामिंग 2: विरोधाभास - habrahabr.ru/post/178959
3. वसीली Golovachev - जल्लाद बार
4. qt-project.org
5. प्रारंभ Erlang के साथ काम करें - rsdn.ru/article/erlang/GettingStartedWithErlang.xml
6. www.erlang.org
7. कार्य "वुल्फ, बकरी और गोभी" - suhin.napp.ru/mat4.htm
8. बाधा प्रोग्रामिंग - en.wikipedia .org / wiki / Constraint_programming
9. बाधाओं में प्रोग्रामिंग - en.wikipedia.org/wiki/Programming in constraints
10. प्रोफेसर मैट कार्लसन - बाधाओं में प्रोग्रामिंग।खुला वीडियो व्याख्यान
11. शाखाओं और सीमाओं की विधि - en.wikipedia.org/wiki/Metod_Branches_and बॉर्डर

PS। मुझे दिलचस्प कार्यों की तलाश है!
- हनोई का टॉवर
- सुडोकू
- यूलर हॉर्स