सबसे छोटा रास्ता खोजने के लिए आप बिडरेक्शनल बीएफएस का उपयोग कैसे करते हैं?

Question

सबसे छोटा रास्ता खोजने के लिए आप बिडरेक्शनल बीएफएस का उपयोग कैसे करते हैं? मान लें कि 6x6 ग्रिड है। प्रारंभ बिंदु (0,5) में है और अंत बिंदु (4,1) में है। बिडरेक्शनल बीएफएस का उपयोग कर सबसे छोटा रास्ता क्या है? कोई रास्ता लागत नहीं है। और यह अप्रत्यक्ष है।

Answer 1

द्वि-दिशात्मक बीएफएस कैसे काम करता है?

साथ ही दो बीएफएस दोनों स्रोत और लक्ष्य चरम से चलाते हैं, एक बार दोनों रनों के लिए सामान्य कशेरुक की खोज हो जाती है। यह कशेरुक स्रोत और लक्ष्य के बीच आधा रास्ते होगा।

बीएफएस से बेहतर क्यों है?

द्वि-दिशात्मक BFS ज्यादातर मामलों में सरल BFS तुलना में काफी बेहतर परिणाम मिलेंगे। मान लें कि स्रोत और लक्ष्य के बीच की दूरी k है, और शाखाकरण कारक B है (प्रत्येक चरम पर औसत बी किनारों पर है)।

• बीएफएस 1 + B + B^2 + ... + B^k शिखरों को पार करेगा।
• द्वि-दिशात्मक बीएफएस 2 + 2B^2 + ... + 2B^(k/2) शिखर पर जायेगा।

बड़े B और k के लिए, दूसरी स्पष्ट रूप से बहुत तेजी से पहला है।

---

आपके मामले में:

सरलता के लिए मुझे लगता है के लिए मैट्रिक्स में कोई बाधाएं हैं कि जा रहा हूँ।

iteration 0 (init): 
front1 = { (0,5) } 
front2 = { (4,1) } 

iteration 1: 
front1 = { (0,4), (1,5) } 
front2 = { (4,0), (4,2), (3,1), (5,1) } 

iteration 2: 
front1 = { (0,3), (1,4), (2,5) } 
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) } 

iteration 3: 
front1 = { (0,2), (1,3), (2,4), (3,5) } 
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), } 

iteration 4: 
front1 = { (0,1), (1,2), .... } 
front2 = { (1,2) , .... } 

अब, हम पता चला है कि मोर्चों (1,2) पर एक दूसरे को काटना, एक साथ स्रोत और लक्ष्य कोने से वहां जाने के लिए ले जाया रास्तों के साथ: यह इस प्रकार होता है

path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) 
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2) 

(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)