हास्केल मिशनरी और नरभक्षी समस्या का समाधान

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

रुचि रखने वालों के लिए, कृपया कैट के लिए आगे बढ़ें।

कार्य विवरण

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

निर्णय

थिएटर एक पिछलग्गू के साथ शुरू होता है, और हास्केल कार्यक्रम काम के लिए आवश्यक मॉड्यूल के आयात के साथ शुरू होता है। चलो उनके साथ शुरू करते हैं।

import Data.List 

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

 data State = State { missioners :: Int, cannibals :: Int, bank :: Char} deriving (Eq, Show) 

एक चौकस पाठक पूछ सकता है, "लेकिन राज्य में केवल दो पूर्णांक फ़ील्ड क्यों हैं? मिशनरी बाएं किनारे पर और दाईं ओर दोनों हो सकते हैं; यही बात नरभक्षी पर लागू होती है। यह चार संख्या वाले क्षेत्रों को दर्शाता है। ”
एक सच्ची टिप्पणी, लेकिन कुछ कारणों से, बिना नाव के लोगों की संख्या के बारे में जानकारी बेमानी है (कुछ के लिए, इसे थोड़ी देर बाद कहा जाएगा)।

हमारी नाव को एक तट से दूसरे तट तक तैरने के लिए, सभी संभव आंदोलनों को सेट करना आवश्यक है। उनमें से केवल पाँच हैं:

 move01 (State msn cnb bk) = State (3 - msn + 2) (3 - cnb) (oppositeBank bk) move02 (State msn cnb bk) = State (3 - msn) (3 - cnb + 2) (oppositeBank bk) move03 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb + 1) (oppositeBank bk) move04 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb) (oppositeBank bk) move05 (State msn cnb bk) = State (3 - msn) (3 - cnb + 1) (oppositeBank bk) 

क्या आप नोटिस करते हैं? हमें इस बारे में जानकारी संग्रहीत करने की आवश्यकता नहीं है कि हमारे पास विपरीत बैंक में कितने मिशनरी हैं - हम हमेशा वर्तमान बैंक पर तीन से मिशनरियों की संख्या घटाकर उनकी संख्या प्राप्त कर सकते हैं। वही नरभक्षी के लिए चला जाता है।

विपरीतबैंक - सबसे सरल फ़ंक्शन जो तट लेबल को विपरीत में बदलता है।

 oppositeBank :: Char -> Char oppositeBank bank | bank == 'L' = 'R' | otherwise = 'L' 

एक नया राज्य बनाने के बाद, हमें यह जाँचना चाहिए कि क्या यह संभव है (सीधे शब्दों में कहें, तो हम ऐसी स्थिति में नहीं आए हैं, जहाँ नाव के साथ किनारे पर चार मिशनरियाँ थीं, या फिर और भी मज़ेदार, डेढ़ लीटर का भार घटाकर एक नरभक्षी)।

 isStatePossible :: State -> Bool isStatePossible (State msn cnb bk) = msn >= 0 && msn <= 3 && cnb >= 0 && cnb <= 3 

यह भी देखना होगा कि क्या हालत सुरक्षित है। तीन संभावित विकल्प हैं। पहला मिशनरियों की संख्या के बराबर नरभक्षी की संख्या है। दूसरा - वर्तमान किनारे पर तीन मिशनरी हैं (इस मामले में, विपरीत किनारे पर कोई मिशनरी नहीं हैं और स्थिति सुरक्षित है)। तीसरा दूसरे के विपरीत है - सभी मिशनरियों ने विपरीत बैंक पर इकट्ठा किया।
तो चलिए लिखते हैं।

 isStateSafe :: State -> Bool isStateSafe (State msn cnb bk) = (cnb == msn) || (msn == 3) || (msn == 0) 

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

 bfsSolution :: [[State]] -> [State] bfsSolution (path:tail') | State 3 3 'R' `elem` extensions = State 3 3 'R' : path | otherwise = bfsSolution $ tail' ++ [ext : path | ext <- extensions, (not . elem ext) path] where headState = head path extensions = filter (\x -> isStatePossible x && isStateSafe x) [move01 headState, move02 headState, move03 headState, move04 headState, move05 headState] 

bfsSolution एक पुनरावर्ती प्रक्रिया है। सबसे पहले, हम पहले से ही निर्मित पथों की सूची से सिर में स्थित पथ से लेते हैं। हम इसे जारी रखने की कोशिश कर रहे हैं, सभी संभव (और सुरक्षित) निरंतरताओं का निर्माण कर रहे हैं। यदि निर्मित निरंतरताओं में से एक अंतिम स्थिति है, तो प्रक्रिया अपना काम पूरा करती है और जारी पथ को वापस करती है। अन्यथा, हम सूची की पूंछ में सभी उत्पन्न पथ जोड़ते हैं और प्रक्रिया को फिर से कहते हैं।
हालत बहुत महत्वपूर्ण है।

 (not . elem ext) path 

यह आपको इस पथ के निर्माण की प्रक्रिया में एल्गोरिथम द्वारा पारित राज्यों में से एक में वापस जाने की अनुमति नहीं देता है। उदाहरण के लिए, अगर चरण n में हमने बाएं मिशन से दो मिशनरियों को दाईं ओर भेजा है, तो चरण (n + 1) में उन्हें बाएं बैंक में वापस लौटने का कोई मतलब नहीं है - हम समय बर्बाद करेंगे और हम एक भी कदम आगे नहीं बढ़ाएंगे (दिए गए कार्यक्रम का पता चलता है) मेरी नेटबुक पर, समाधान 0.85 सेकंड में है, उपरोक्त स्थिति को हटाते हुए, मुझे गणनाओं में बहुत बड़ी वृद्धि मिलती है - उत्तर खोजने में 45 सेकंड लगते हैं)।

अंतिम स्पर्श मुख्य कार्य है।

 main = do mapM_ (putStrLn . show) $ (reverse . bfsSolution) ([[State 3 3 'L']]) 

निष्कर्ष

यह लेख किसी भी तरह से इस समस्या की व्यापक समीक्षा और सभी संभावित समाधानों की विस्तृत व्याख्या का दावा नहीं करता है। इच्छुक पाठक रिटर्न के साथ एक गहरी खोज एल्गोरिदम को लागू कर सकते हैं; उपरोक्त समाधान "दिमाग में लाने" का एक और (अभी तक कार्यान्वित नहीं) विचार भी है - सूचियों की सूची में सभी उत्पन्न समाधानों को संग्रहीत करने से दूर जाने और एन-एरी ट्री को लागू करने का प्रयास करना।

आपका ध्यान देने के लिए धन्यवाद।