गहराई से पहली खोज में, आप ग्राफ में कुछ नोड से शुरू करते हैं और ग्राफ में गहरा और गहराई से खोज करते हैं, जबकि आप नए नोड्स को पा सकते हैं जिन्हें आपने अभी तक नहीं पहुंचाया है (या जब तक आपको समाधान नहीं मिल जाता)। जब भी डीएफएस चाल से बाहर चला जाता है, तो यह नवीनतम बिंदु पर बैकट्रैक करता है जहां यह एक अलग विकल्प बना सकता है, फिर वहां से पता लगाता है। यदि आपका ग्राफ बहुत बड़ा है और यह केवल एक समाधान है, तो यह एक गंभीर समस्या हो सकती है, क्योंकि आप प्रत्येक नोड को देखने के बाद समाधान खोजने के लिए केवल एक डीएफएस पथ के साथ पूरे ग्राफ की खोज कर सकते हैं। इससे भी बदतर, यदि ग्राफ अनंत है (शायद आपके ग्राफ में सभी संख्याएं हैं, उदाहरण के लिए), खोज समाप्त नहीं हो सकती है। इसके अलावा, एक बार जब आप जिस नोड को ढूंढ रहे हैं उसे ढूंढने के बाद, आपके पास इष्टतम पथ नहीं हो सकता है (आप समाधान के लिए देख रहे पूरे ग्राफ पर लुप्त हो सकते थे, भले ही यह प्रारंभ नोड के ठीक आगे था!)
इस समस्या का एक संभावित समाधान डीएफएस द्वारा उठाए गए किसी भी पथ की गहराई को सीमित करना होगा। उदाहरण के लिए, हम एक डीएफएस खोज कर सकते हैं, लेकिन अगर हम कभी भी 5 से अधिक लंबाई का मार्ग लेते हैं तो खोज को रोकें। यह सुनिश्चित करता है कि हम किसी नोड को कभी भी नोड से अन्वेषण न करें, जिसका मतलब है कि शुरूआत नोड से पांच से अधिक दूरी का अर्थ है, जिसका अर्थ है कि हम कभी नहीं खोजते असीम रूप से बाहर या (जब तक कि ग्राफ बेहद घना न हो) हम पूरे ग्राफ को नहीं खोजते हैं। हालांकि, इसका मतलब यह है कि हमें वह नोड नहीं मिल रहा है जिसे हम ढूंढ रहे हैं, क्योंकि हम जरूरी नहीं कि पूरे ग्राफ का पता लगाएं।
पुनरावृत्ति गहराई के पीछे विचार इस दूसरे दृष्टिकोण का उपयोग करना है, लेकिन प्रत्येक स्तर पर गहराई को बढ़ाने के लिए है। दूसरे शब्दों में, हम लम्बे समय के सभी पथों का उपयोग करके खोज सकते हैं, फिर लम्बाई के सभी पथ, फिर लंबाई तीन, आदि। जब तक हम प्रश्न में नोड ढूंढने को समाप्त नहीं करते हैं। इसका मतलब यह है कि हम कभी भी अनंत मृत-अंत पथों के साथ अन्वेषण नहीं करते हैं, क्योंकि प्रत्येक चरण की लंबाई प्रत्येक चरण में कुछ लंबाई से ढकी होती है। इसका मतलब यह भी है कि हमें गंतव्य नोड के लिए सबसे कम संभव पथ मिल गया है, क्योंकि अगर हमें गहराई से नोड नहीं मिला, लेकिन इसे गहराई से +1 + पर पाया गया, तो लंबाई डी का मार्ग नहीं हो सकता (या हम इसे ले लिया होगा), तो लंबाई डी + 1 का मार्ग वास्तव में इष्टतम है।
कारण यह है कि यह एक डीएफएस से अलग है, यह कभी भी उस मामले में नहीं चलता है जहां कभी भी बिना किसी समाप्ति के ग्राफ के चारों ओर एक बहुत लंबा और सर्किट पथ होता है। पथ की लंबाई हमेशा कैप्ड की जाती है, इसलिए हम अनावश्यक शाखाओं की खोज कभी खत्म नहीं करते हैं।
बीएफएस से अलग यह कारण यह है कि बीएफएस में, आपको एक ही समय में सभी फ्रिंज नोड्स को स्मृति में रखना होगा। यह स्मृति ओ (बी डी) लेता है, जहां बी शाखाकरण कारक है। इसकी तुलना ओ (डी) स्मृति उपयोग को पुनरावर्तक गहराई से करें (मौजूदा पथ में प्रत्येक डी नोड्स के लिए राज्य को पकड़ने के लिए)। बेशक, बीएफएस कभी भी एक ही पथ की खोज नहीं करता है, जबकि पुनरावृत्ति गहराई कई बार किसी भी पथ का पता लगा सकती है क्योंकि यह गहराई सीमा को बढ़ाती है।हालांकि, असम्बद्ध रूप से दोनों में एक ही रनटाइम होता है। बीएफएस ओ (बी डी) में सभी ओ (बी डी) दूरी डी पर विचार करने के बाद चरण समाप्त हो जाता है। Iterative गहराई ओ (बी डी) समय प्रति स्तर का उपयोग करता है, जो ओ (बी डी) कुल मिलाकर, लेकिन एक उच्च निरंतर कारक के साथ।
संक्षेप में:
- डीएफएस एक इष्टतम पथ को खोजने के लिए गारंटी नहीं है; पुनरावृत्ति गहराई है।
- डीएफएस लक्ष्य नोड खोजने से पहले पूरे ग्राफ का पता लगा सकता है; पुनरावृत्ति गहराई केवल तभी होती है जब प्रारंभ और अंत नोड के बीच की दूरी ग्राफ में अधिकतम हो।
- बीएफएस और पुनरावर्तक दोनों ओ (बी डी) में दोनों को गहरा कर देते हैं, लेकिन पुनरावृत्त गहराई में उच्च स्थिर कारक होता है।
- बीएफएस ओ (बी डी) स्मृति का उपयोग करता है, जबकि पुनरावृत्ति गहराई केवल ओ (डी) का उपयोग करता है।
आशा है कि इससे मदद मिलती है!
गहराई से पहली खोज में, आप उस प्रत्येक शाखा का पता लगाते हैं जिसे आप पूरी तरह से दर्ज करते हैं और इससे पहले कि आप आगे बढ़ते हैं। पुनरावर्तक गहराई में, आप वर्तमान गहराई से नीचे नहीं जाते हैं, और इसलिए बैकट्रैकिंग से पहले आप जिस शाखा को पूरी तरह से देखते हैं उसका पता लगाएं। – HelloGoodbye