BFS र DFS: भूलभुलैया खोज्ने
एक-एक कोठा गर्दै भूलभुलैयामा खोज पठाउनुहोस्। Breadth-first search ले queue सँग घेरा-घेरा फैलिँदै सबैभन्दा छोटो बाटो भेट्छ; depth-first search ले stack सँग एउटै गल्लीमा गहिरो पस्छ। तिनले भेटेका बाटो र हरेकले हेरेका कोठाको सङ्ख्या दाँज्नुहोस्।
मूल अवधारणा
Breadth-first search (BFS) ले queue प्रयोग गरेर दूरीको क्रममा कोठा हेर्छ, त्यसैले यसको बाटो सधैँ सबैभन्दा छोटो हुन्छ; depth-first search (DFS) ले stack प्रयोग गरेर एउटै बाटो जतिसक्दो टाढासम्म पछ्याउँछ, त्यसैले यसको बाटो लामो हुन सक्छ
पाठ: Algorithm
भूलभुलैया कोठाहरूको grid हो, जसमध्ये केही पर्खाल हुन्। S बाट झण्डासम्मको बाटो खोज्न प्रोग्रामले अझै हेर्न बाँकी कोठाको सूची राख्छ। यसले एउटा कोठा झिक्छ, त्यो झण्डा हो कि जाँच्छ, होइन भने त्यस कोठाका नहेरिएका खुला छिमेकी सूचीमा थप्छ। दुई खोजबीच फरक एउटै छ: अर्को कुन कोठा झिक्ने। Breadth-first search (BFS) ले सूचीलाई queue बनाउँछ र सबैभन्दा पुरानो कोठा झिक्छ, त्यसैले पोखरीको छालजस्तै हरेक पटक एक कदम टाढा बराबर फैलिन्छ। यसको बाटो सधैँ सबैभन्दा छोटो हुन्छ। Depth-first search (DFS) ले सूचीलाई stack बनाउँछ र सबैभन्दा नयाँ कोठा झिक्छ, त्यसैले अड्किएसम्म एउटै गल्लीमा कुद्छ, अनि मात्र फर्किन्छ। यसको बाटो धेरै लामो हुन सक्छ। दुवैले हरेक कोठा कहाँबाट पुगियो भनेर सम्झन्छन्, त्यसैले अन्त्यमा झण्डाबाट पछाडितिर बाटो कोरिन्छ।
के सिक्नुहुनेछ
- Queue सँग BFS र stack सँग DFS लाई कोठा-कोठा गरेर trace गर्नुहोस्।
- Grid मा BFS ले किन सधैँ सबैभन्दा छोटो बाटो भेट्छ, व्याख्या गर्नुहोस्।
- BFS र DFS ले भेटेका बाटो र हेरेका कोठा दाँज्नुहोस्।
- बाटो नै छैन भनेर खोजले कसरी थाहा पाउँछ, व्याख्या गर्नुहोस्।
सुरु गर्नुअघि
- Queue (पहिले आउने, पहिले जाने) र stack (पछि आउने, पहिले जाने) भनेको के हो थाहा हुनुपर्छ।
सामग्री
- आफ्नै भूलभुलैया कोर्न कोठे कागज
उपकरण
- केही पनि चाहिँदैन
विधि
- खुला भूलभुलैयामा breadth-first search चलाएर बाटोको लम्बाइ र हेरिएका कोठा टिप्नुहोस्।
- उही भूलभुलैयामा depth-first search चलाएर दाँज्नुहोस्।
- पर्खालले घेरिएको भूलभुलैया, अनि गल्लीवाला भूलभुलैया दुवै खोजले चलाउनुहोस्।
- अभ्यासका challenge हरूको उत्तर दिनुहोस्।