ग्राफ ट्रैवर्सल विधियों ने हमेशा मुझे बहुत मोहित किया है। प्रभावी सहकर्मी से सहकर्मी संचार करने के लिए जीपीएस का उपयोग करते हुए निकटतम रेस्तरां और कैफे खोजने के लिए, ट्रैवर्सल विधियों में वास्तविक दुनिया के परिदृश्य में अनुप्रयोगों का एक विविध सेट है। चौड़ाई-प्रथम खोज एल्गोरिथ्म पर इस ब्लॉग में, हम ग्राफ ट्रैवर्सल विधियों के पीछे के तर्क पर चर्चा करेंगे और चौड़ाई-प्रथम खोज एल्गोरिदम के काम को समझने के लिए उदाहरणों का उपयोग करेंगे।
आर्टिफिशियल इंटेलिजेंस और मशीन लर्निंग का गहराई से ज्ञान प्राप्त करने के लिए, आप लाइव के लिए नामांकन कर सकते हैं 24/7 समर्थन और आजीवन पहुंच के साथ Edureka द्वारा।
यहां उन विषयों की सूची दी गई है जो इस ब्लॉग में शामिल हैं:
- ग्राफ ट्रैवर्सल का परिचय
- चौड़ाई-प्रथम खोज क्या है?
- एक उदाहरण के साथ चौड़ाई-प्रथम खोज एल्गोरिथ्म को समझना
- चौड़ाई-पहली खोज एल्गोरिथ्म स्यूडोकोड
- चौड़ाई-पहली खोज के अनुप्रयोग
ग्राफ ट्रैवर्सल का परिचय
प्रसंस्करण के लिए एक ग्राफ पर जाने और तलाशने की प्रक्रिया को ग्राफ ट्रैवर्सल कहा जाता है। अधिक विशिष्ट होने के लिए यह एक ग्राफ में प्रत्येक शीर्ष और किनारे पर आने और जाने के बारे में है, जैसे कि सभी कोने बिल्कुल एक बार खोजे जाते हैं।
यह सरल लगता है! लेकिन वहाँ एक पकड़ है।
कई ग्राफ ट्रैवर्सल तकनीकें हैं जैसे कि ब्रेडथ-फर्स्ट सर्च, डेप्थ फर्स्ट सर्च वगैरह। एक ग्राफ का उपयोग करने के लिए चुनौती है ट्रैवर्सल तकनीक जो किसी विशेष समस्या को हल करने के लिए सबसे उपयुक्त है। यह हमें चौड़ाई-प्रथम खोज तकनीक में लाता है।
चौड़ाई-प्रथम खोज एल्गोरिथम क्या है?
चौड़ाई-प्रथम खोज एल्गोरिथ्म एक ग्राफ़ ट्रैवर्सिंग तकनीक है, जहां आप एक यादृच्छिक प्रारंभिक नोड (स्रोत या रूट नोड) का चयन करते हैं और ग्राफ़ लेयर-वार को इस तरह से ट्रैक करना शुरू करते हैं कि सभी नोड्स और उनके संबंधित बच्चों के नोड्स का दौरा किया और खोज की जाती है।
इससे पहले कि हम आगे बढ़ें और चौड़ाई-प्रथम खोज को एक उदाहरण से समझें, आइए ग्राफ ट्रैवर्सल से संबंधित दो महत्वपूर्ण शब्दों से परिचित हों:
- एक नोड पर जाना: जैसे नाम से पता चलता है, नोड पर जाने का मतलब है, नोड पर जाना या चयन करना।
- एक नोड की खोज: तलाश कर रहा है एक चयनित नोड के आसन्न नोड्स (बच्चे के नोड्स)।
इसे समझने के लिए उपरोक्त आंकड़ा देखें।
एक उदाहरण के साथ चौड़ाई-पहली खोज एल्गोरिदम को समझना
चौड़ाई-पहली खोज एल्गोरिथ्म एक समस्या को हल करने के लिए एक सरल, स्तर-आधारित दृष्टिकोण का अनुसरण करता है। नीचे दिए गए बाइनरी ट्री पर विचार करें (जो एक ग्राफ है)। हमारा उद्देश्य चौड़ाई-प्रथम खोज एल्गोरिदम का उपयोग करके ग्राफ को पार करना है।
एक सरणी जावा में एक वस्तु है
आरंभ करने से पहले, आपको चौड़ाई-प्रथम खोज एल्गोरिथ्म में शामिल मुख्य डेटा संरचना से परिचित होना चाहिए।
कतार एक सार डेटा संरचना है जो फर्स्ट-इन-फर्स्ट-आउट-आउट कार्यप्रणाली का अनुसरण करती है (पहले डाला गया डेटा पहले एक्सेस किया जाएगा)। यह दोनों सिरों पर खुला होता है, जहाँ एक सिरा हमेशा डेटा (enqueue) डालने के लिए और दूसरा डेटा (dequeue) निकालने के लिए उपयोग किया जाता है।
अब एक नज़र डालते हैं कि चौड़ाई-प्रथम खोज का उपयोग करके ग्राफ को पीछे हटाने में शामिल चरणों पर:
मैं एक जावा प्रोग्राम कैसे संकलित करता हूं
स्टेप 1: एक खाली कतार ले लो।
चरण 2: एक शुरुआती नोड का चयन करें (एक नोड पर जाकर) और इसे कतार में डालें।
चरण 3: बशर्ते कि कतार खाली नहीं है, कतार से नोड निकालें और कतार में अपने बच्चे के नोड्स (नोड की खोज) डालें।
चरण 4: निकाले गए नोड को प्रिंट करें।
यदि आप भ्रमित हैं तो चिंता न करें, हम इसे एक उदाहरण के साथ समझेंगे।
नीचे दिए गए ग्राफ़ पर एक नज़र डालें, हम ग्राफ़ के माध्यम से ट्रैवस करने के लिए चौड़ाई-प्रथम खोज एल्गोरिदम का उपयोग करेंगे।
हमारे मामले में, हम नोड 'ए' को रूट नोड के रूप में निर्दिष्ट करेंगे और नीचे की ओर ट्रेस करना शुरू करेंगे और ऊपर वर्णित चरणों का पालन करेंगे।
उपरोक्त छवि में चौड़ाई-प्रथम खोज एल्गोरिथम की एंड-टू-एंड प्रक्रिया को दर्शाया गया है। इसे और गहराई से समझाता हूं।
- रूट नोड के रूप में 'a' असाइन करें और इसे कतार में डालें।
- नोड node a ’को कतार से निकालें और‘ a ’, यानी,‘ b ’और’ c ’के चाइल्ड नोड्स डालें।
- नोड। A ’प्रिंट करें।
- कतार खाली नहीं है और इसमें नोड 'बी' और 'सी' है। चूँकि ue b ’कतार में पहला नोड है, इसलिए इसे निकालें और। B’, यानी, नोड ’d’ और ’e’ के चाइल्ड नोड्स डालें।
- जब तक कतार खाली न हो जाए, तब तक इन चरणों को दोहराएं। ध्यान दें कि पहले से ही आने वाले नोड्स को कतार में नहीं जोड़ा जाना चाहिए फिर।
अब हम चौड़ाई-प्रथम खोज एल्गोरिथ्म के छद्म पृष्ठ पर देखें।
चौड़ाई-पहली खोज एल्गोरिथ्म स्यूडोकोड
चौड़ाई-प्रथम खोज एल्गोरिथ्म को लागू करने के लिए यहाँ छद्मकोश है:
इनपुट: स्रोत नोड बीएफएस (जी, एस) के रूप में क्यू क्यू कतार है। Q.enqueue (s) मार्क एस के रूप में देखा गया है जबकि (क्यू खाली नहीं है) v = Q.dequeue () ग्राफ G में v के सभी पड़ोसियों के लिए यदि w का दौरा नहीं किया गया है
उपरोक्त कोड में, निम्न चरणों का पालन किया जाता है:
- (जी, एस) इनपुट है, यहां जी ग्राफ है और एस रूट नोड है
- स्रोत नोड que s 'के साथ एक कतार' Q 'बनाई और बनाई गई है
- सभी बच्चे के नोड्स चिह्नित हैं
- कतार से 's' निकालें और बच्चे के नोड्स पर जाएँ
- V के सभी बच्चे नोड्स की प्रक्रिया करें
- स्टोर w (चाइल्ड नोड्स) Q में आगे अपने चाइल्ड नोड्स पर जाएँ
- ‘Q’ तक जारी रखें खाली
इससे पहले कि हम ब्लॉग को लपेटें, आइए चौड़ाई-प्रथम खोज एल्गोरिदम के कुछ अनुप्रयोगों को देखें।
चौड़ाई-पहले खोज एल्गोरिथ्म के अनुप्रयोग
चौड़ाई-पहली खोज एक सरल ग्राफ ट्रैवर्सल विधि है जिसमें अनुप्रयोगों की एक आश्चर्यजनक सीमा होती है। यहाँ कुछ रोचक तरीके हैं जिनमें ब्रेड-फ़र्स्ट सर्च का उपयोग किया जा रहा है:
खोज इंजन में क्रॉलर: चौड़ाई-पहली खोज वेब पेजों को अनुक्रमित करने के लिए उपयोग किए जाने वाले मुख्य एल्गोरिदम में से एक है। एल्गोरिथ्म स्रोत पृष्ठ से ट्रैवर्स करना शुरू करता है और पेज से जुड़े सभी लिंक का अनुसरण करता है। यहां प्रत्येक वेब पेज को एक ग्राफ में एक नोड के रूप में माना जाएगा।
GPS नेविगेशन सिस्टम: चौड़ाई-पहली खोज जीपीएस सिस्टम का उपयोग करके पड़ोसी स्थानों को खोजने के लिए उपयोग किए जाने वाले सर्वोत्तम एल्गोरिदम में से एक है।
एक छोटे से ग्राफ के लिए सबसे छोटा रास्ता और न्यूनतम स्पैनिंग ट्री ढूंढें: जब यह एक अनवेटेड ग्राफ की बात आती है, तो सबसे कम पथ की गणना करना काफी सरल है क्योंकि सबसे छोटे पथ के पीछे का विचार कम से कम किनारों के साथ एक पथ चुनना है। चौड़ाई-पहली खोज स्रोत नोड से शुरू होने वाली न्यूनतम संख्या को ट्रेस करके इसकी अनुमति दे सकती है। इसी तरह, एक फैले हुए पेड़ के लिए, हम फैले हुए पेड़ को खोजने के लिए दोनों में से किसी एक, चौड़ाई-प्रथम खोज या गहराई-पहले ट्रैवर्सल विधियों का उपयोग कर सकते हैं।
हैशटेबल और हैशमैप में क्या अंतर है
प्रसारण: नेटवर्किंग हम संचार के लिए पैकेट के रूप में क्या कहते हैं का उपयोग करता है। ये पैकेट विभिन्न नेटवर्किंग नोड्स तक पहुंचने के लिए एक ट्रैवर्सल विधि का पालन करते हैं। सबसे अधिक इस्तेमाल की जाने वाली ट्रैवर्सल विधियों में से एक चौड़ाई-पहली खोज है। इसका उपयोग एक एल्गोरिथ्म के रूप में किया जा रहा है, जिसका उपयोग किसी नेटवर्क में सभी नोड्स में प्रसारित पैकेट को संप्रेषित करने के लिए किया जाता है।
पीयर टू पीयर नेटवर्किंग: चौड़ाई-प्रथम खोज को सहकर्मी से सहकर्मी नेटवर्क में सभी पड़ोसी नोड्स को खोजने के लिए एक ट्रावेलर विधि के रूप में उपयोग किया जा सकता है। उदाहरण के लिए, बिटटोरेंट सहकर्मी से सहकर्मी संचार के लिए चौड़ाई-प्रथम खोज का उपयोग करता है।
तो यह सब चौड़ाई-पहले खोज एल्गोरिदम के काम के बारे में था। अब जब आप जानते हैं कि रेखांकन कैसे करना है, तो मुझे यकीन है कि आप और जानने के लिए उत्सुक हैं। आपकी रुचि बनाए रखने के लिए यहां कुछ प्रासंगिक ब्लॉग दिए गए हैं:
इसके साथ, हम इस ब्लॉग के अंत में आते हैं। यदि आपके पास इस विषय के बारे में कोई प्रश्न हैं, तो कृपया नीचे एक टिप्पणी छोड़ दें और हम आपके पास वापस आ जाएंगे।
यदि आप आर्टिफिशियल इंटेलिजेंस और मशीन लर्निंग पर एक पूर्ण पाठ्यक्रम के लिए नामांकन करना चाहते हैं, तो एडुर्का ने विशेष रूप से क्यूरेट किया है जो आपको सुपरवाइज्ड लर्निंग, अनसुप्रवाइज्ड लर्निंग, और नेचुरल लैंग्वेज प्रोसेसिंग जैसी तकनीकों में पारंगत बना देगा। इसमें आर्टिफिशियल इंटेलिजेंस एंड मशीन लर्निंग में नवीनतम प्रगति और तकनीकी दृष्टिकोण पर प्रशिक्षण शामिल है जैसे कि डीप लर्निंग, ग्राफिकल मॉडल और सुदृढीकरण सीखना।