भूलभुलैया हल करने इष्टतम कोई बाएं मोड़ एल्गोरिदम

Question

मैं एक ऐसे प्रोजेक्ट पर काम कर रहा हूं जहां मुझे न्यूनतम मोड़ों का उपयोग करके भूलभुलैया हल करने की आवश्यकता है और कोई बायां मुड़ता नहीं है।

यात्रा की दूरी तब तक अप्रासंगिक है जब तक कि सही मोड़ कम नहीं हो जाते हैं। हमें बैकट्रैकिंग एल्गोरिदम और इष्टतम (समय) दोनों का उपयोग करके हमारे कार्यक्रम को लागू करने के लिए कहा जाता है।

बैकट्रैकिंग एल्गोरिदम के लिए मैं एक ढेर का उपयोग कर रहा था। मेरा एल्गोरिदम कुछ ऐसा होगा:

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

मैं अगर कोई मुझे इस के लिए एक इष्टतम एल्गोरिथ्म की दिशा में बात कर सकता है सोच रहा था।

मुझे बैकट्रैकिंग से बेहतर कुछ भी सोचने में कठिन समय हो रहा है।

Answer 1

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

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

. . . . . . (0) . . . . . 0 1 1 1 1 (1) 0 1 1 1 1 1 
. ####### . . 0 ########## . 0 ########## . 0 ########## 2 
. # . # . . 0 # . # . . 0 # . # . . 0 # . # . (2) 
. # . . . . 0 # . . . . 0 # . . . . 0 # . . . (2) 
. #### . # . 0 #### . # . 0 #### . # . 0 #### . # 2 
(.) . . . . . (0) . . . . . 0 1 1 1 1 1 0 1 1 1 1 1 

0 1 1 1 1 1 0 1 1 1 1 1 
0 ########## 2 0 ########## 2 
0 # . # 3 2 0 # 4 # 3 2 
0 # (3) 3 3 2 0 # 3 3 3 2 
0 #### . # 2 0 #### 4 # 2 
0 1 1 (1) 1 1 0 1 1 1 1 1 

() निरूपित पहुँच उचित पड़ोसी दूर दराज के साथ अंक

Answer 2

भूलभुलैया में प्रत्येक स्थिति के लिए चार नोड्स का निर्माण करके एक ग्राफ बनाएं। प्रत्येक नोड एक विशेष दिशा के अनुरूप होगा: एन, एस, ई, डब्ल्यू

प्रत्येक नोड और उसके आस-पास के तीन पड़ोसियों के बीच किनारे होंगे: "फ्रंट", "बैक" और " सही "(यदि वे मौजूद हैं)। "फ्रंट" और "बैक" में नोड की ओर बढ़ने वाले किनारे में वजन 0 होगा (क्योंकि पथ की लंबाई कोई फर्क नहीं पड़ता), जबकि "दाएं" में नोड के किनारे के वजन 1 होगा (यह वही है जो दर्शाता है सही मोड़ बनाने की लागत)।

एक बार ग्राफ की स्थापना की है breadth-first search एल्गोरिथ्म के एक संशोधित संस्करण समस्या का समाधान होगा (और शायद सबसे अच्छा तरीका यह करने के लिए भूलभुलैया के मूल प्रतिनिधित्व का पुन: उपयोग करने के लिए है)।

0/1 एज वजन को संभालने की चाल मानक कतार कार्यान्वयन के बजाय deque का उपयोग करना है। विशेष रूप से, 0 वज़न किनारों के माध्यम से पहुंचे नोड्स डेक के सामने धकेल दिए जाएंगे और वजन 1 के किनारों तक पहुंचने वाले लोगों को पीछे की तरफ धकेल दिया जाएगा।