एक मान्यता कार्य के रूप में समुद्री युद्ध

हेलो, हेब्र!
नौसैनिक युद्ध के सप्ताह को जारी रखते हुए, मैं इष्टतम शूटिंग रणनीति बनाने के लिए एक और तरीका पेश करना चाहता हूं। यह रणनीति के एक पेड़ के प्रतिनिधित्व का उपयोग करता है, जो कि खेल सिद्धांत में बहुत आम है। समाधान तालिका के रूप में समस्या की प्रस्तुति को परीक्षणों के सिद्धांत से उधार लिया गया है, जो पिछली शताब्दी के 70 के दशक में लोकप्रिय था और विशेष रूप से, इलेक्ट्रॉनिक सर्किट में दोषों की निगरानी और निदान के लिए इस्तेमाल किया गया था। यह विधि आपको इष्टतम रणनीति खोजने की अनुमति देती है, लेकिन इसकी बहुत बड़ी कम्प्यूटेशनल जटिलता है। काश, 10x10 मैदान पर खेल का विश्लेषण नहीं किया जा सकता था।

निर्णय का पेड़

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

(ई। ग्रिशकोवेट्स "ड्रेडनॉट" द्वारा नाटक से मुक्त उद्धरण)

आरंभ करने के लिए, चलो एक निर्णय पेड़ के रूप में रणनीति पेश करने का एक सुविधाजनक तरीका प्राप्त करें। उदाहरण के लिए, यहां एक 3x3 क्षेत्र पर क्रूजर और दो नावों को कैसे शूट किया जाए।


पेड़ की चोटी पर एक खेल का मैदान है जिसमें पहले से ही शॉट हैं। वर्तमान शॉट लाल रंग में चिह्नित है। शॉट के परिणाम को पसलियों के लिए जिम्मेदार ठहराया जाता है: मिस (।) या हिट (एक्स)। पत्तियां जहाजों का स्थान दिखाती हैं। रणनीति को इस तरह शब्दों में वर्णित किया जा सकता है। सबसे पहले, b1 पर शूट करें। यदि हम हिट करते हैं, तो यह स्पष्ट हो जाता है कि जहाज कैसे स्थित हैं, और यह उन्हें खत्म करने के लिए बनी हुई है। यदि नहीं, तो बी 2 पर शूट करें। अगर हम गिरते हैं, तो फिर से सब कुछ स्पष्ट है। यदि हम चूक जाते हैं, तो स्थान के लिए दो विकल्प हैं, और b3 में एक शॉट अंतिम स्पष्टता लाता है।

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

आप रणनीति का मूल्यांकन कर सकते हैं कि सबसे खराब स्थिति में कितनी मिसाइलें बनाई जाएंगी। फिर, दो रणनीतियों में, जड़ से पत्ती तक की अधिकतम संख्या के साथ एक न्यूनतम है। और हम मान सकते हैं कि दुश्मन समान संभावना के साथ संयोग से एक स्थान चुनता है, और अपेक्षित संख्या को कम करने का प्रयास करता है। फिर, दो रणनीतियों में, प्रत्येक पत्ती की जड़ से सभी रास्तों में सबसे छोटा कुल मिलाकर सबसे कम होगा। उदाहरण के लिए, हमारी रणनीति जहाजों को तीन से अधिक मिसाइलों को नष्ट करने की गारंटी देती है, और अपेक्षित संख्या में मिसाइलें (3 + 2 + 1 + 0) / 4 = 1.5 है।

वैसे, आप एक रणनीति खोजने की कोशिश कर सकते हैं जो दोनों इंद्रियों में सर्वश्रेष्ठ होगी। लुभावना लगता है? काश, दोनों समस्याएं एक सेट को कवर करने की एनपी-कठिन समस्या के समान हैं, जो हमें आसान समाधान एल्गोरिदम की अनुपस्थिति का वादा करती हैं। लेकिन, धैर्य और मशीन के समय के साथ, हम अभी भी कुछ करने की कोशिश कर रहे हैं।

निर्णय तालिका और रणनीति निर्माण एल्गोरिदम

आइए एक तथाकथित निर्णय तालिका के रूप में समस्या की कल्पना करें। हम एक आयताकार मेज का निर्माण करेंगे जिसमें स्तंभ खेल के मैदान की कोशिकाओं से मेल खाते हैं, और पंक्तियाँ जहाजों के स्थान के लिए सभी प्रकार के विकल्पों के अनुरूप हैं। पंक्ति और स्तंभ के चौराहे पर तालिका के सेल में साइन "X" होता है यदि खेल के मैदान के इस सेल में जहाजों के दिए गए स्थान में एक जहाज होता है, और "।" अन्यथा। उदाहरण के लिए, यहां एक तालिका है जो क्रूजर के स्थान के लिए चार संभावित विकल्पों और 3x3 क्षेत्र में दो नावों का वर्णन करती है (दाईं ओर प्रत्येक पंक्ति को एक सेल सौंपा गया है जिसमें क्रूजर का मध्य स्थित है - हमारे उदाहरण में, यह विशिष्ट रूप से जहाजों के स्थान को निर्धारित करता है)।


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

एक अनुमानित लालची एल्गोरिथ्म जड़ पर शुरू होने वाला एक पेड़ बनाता है। एल्गोरिथ्म तालिका के स्तंभ (शॉट के लिए सेल) का चयन करता है, ताकि इस सेल में एक जहाज के रूप में पंक्तियों का अनुपात 1/2 के करीब हो। चयनित सेल को पेड़ की जड़ के लिए जिम्मेदार ठहराया जाता है, मिस / हिट से संबंधित दो किनारों को जड़ से खींचा जाता है, किनारों के छोर पर दो नए कोने निलंबित होते हैं। प्रत्येक नए कोने में एक सबटेबल मिलता है, जिसमें पहली गोली के परिणामों के विपरीत लाइनों को पार किया जाता है। एक ही प्रक्रिया प्रत्येक पत्ते पर लागू होती है जब तक कि सभी परिणामी तालिकाओं में सिर्फ एक पंक्ति न हो। इसी कोने पत्ते बन जाते हैं, और एल्गोरिथ्म समाप्त हो जाता है।

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

प्रयोग

सिद्धांतकार तय करता है कि वह क्या कर सकता है, आवश्यकतानुसार, और व्यवसायी तय करता है कि उसे क्या चाहिए, वह कैसे कर सकता है।

सम्मानित Mrrl द्वारा आवाज उठाई गई कॉन्फ़िगरेशन (1.85 * 10 ¹⁵ ) की संख्या ने मुझे कोड लिखने की प्रक्रिया में पकड़ा और बहुत अधिक उत्साह बढ़ाया । यह सोचकर, मैंने मैदान के आकार को कम करते हुए मामले को अंत तक लाने का फैसला किया। सटीक एल्गोरिथ्म एक 5x5 क्षेत्र पर एक क्रूजर, दो विध्वंसक और तीन नौकाओं के एक स्क्वाड्रन पर गोलीबारी के कार्य को पूरा करने के लिए सहमत हुआ। संभावित विन्यासों की संख्या केवल 1428 है, लेकिन उपकथाओं के ग्राफ में एक प्रभावशाली 10 191 257 कोने और 214 464 800 किनारों हैं। इष्टतम एल्गोरिथ्म आपको स्क्वाड्रन को नष्ट करने की अनुमति देता है, जिससे सात से अधिक मिसाइलें नहीं बनती हैं, और औसतन 4.51 मिसेज़ की अनुमति देता है। नीचे दिए गए आंकड़े से पता चलता है कि आप पांच मिसाइलों में जहाजों की स्थिति कैसे निर्धारित कर सकते हैं (यानी, जब निर्णय पेड़ की सबसे दाहिनी शाखा को लागू करते हैं)।


समान कार्य के लिए लालची एल्गोरिथ्म ने एक रणनीति बनाई जिसमें सबसे खराब स्थिति में 11 मिसाइलों की अनुमति दी गई, जिनकी अनुमानित संख्या 5.46 थी। नीचे दिया गया आंकड़ा मिस शूटिंग रणनीति (निर्णय पेड़ की सबसे दाहिनी शाखा) को दर्शाता है।

सारांश

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

अद्यतन

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

2) एक लालची एल्गोरिथ्म जो प्रत्येक चरण पर एक कॉलम का चयन करता है जिसमें अधिकतम संख्या में संकेत X (यानी, जहाज को खोजने की उच्चतम संभावना वाले शॉट के लिए एक सेल चुनना), परिणाम को करीब से दिखाता है: सबसे खराब स्थिति में 8 मिस और औसतन 4.595। जवाब "मार" की शुरूआत प्रदर्शन में काफी सुधार करती है: सबसे खराब स्थिति में 4 मिस और औसतन 2.04 मिस।

अतिरिक्त के लिए धन्यवाद Mrrl ।