विस्तार-प्रधान खोज
विस्तार-प्रधान खोज (अंग्रेज़ी: Breadth-first Search या बीएफएस) ट्री या ग्राफ डेटा संरचनाओं की खोज या खोज के लिए एक कलन विधि है। यह ट्री के जड़(root) (या ग्राफ़ के कुछ मनमाने नोड,जिसे कभी-कभी 'खोज कुंजी'[1] के रूप में संदर्भित किया जाता है) पर शुरू होता है और अगली गहराई पर नोड्स में जाने से पहले वर्तमान गहराई पर सभी पड़ोसी नोड्स की पड़ताल करता है।
यह गहराई-प्रधान खोज,जो सबसे पहले गहराई पर मौजूद नोड्स की पड़ताल करता है, से उलट है[2]।
बीएफएस और रेखांकन के जुड़े घटकों को खोजने में इसके आवेदन का आविष्कार 1945 में कोनराड ज़्यूस द्वारा,उनके (अस्वीकृत) पीएच.डी. प्लैंकल्कल प्रोग्रामिंग भाषा पर थीसिस में किया गया था, लेकिन यह 1972 तक प्रकाशित नहीं हुई थी[3]। इसे 1959 में एडवर्ड एफमूर द्वारा पुन: स्थापित किया गया था, जिन्होंने इसका उपयोग एक भूलभुलैया से बाहर सबसे छोटा रास्ता खोजने के लिए किया था[4][5], और बाद में सी.वाई. ली द्वारा एक वायर रूटिंग एल्गोरिथ्म (1961 में प्रकाशित) में विकसित किया गया[6]।
छद्म कोड
संपादित करेंनिवेश(Input): एक ग्राफ G और एक प्रारंभिक नोड R जो G की जड़(root) नोड है।
उपज(Output):लक्ष्य अवस्था। जनक(parent) लिंक R तक जाने वाले सबसे छोटे मार्ग का पता लगाता है[7]।
1 procedure BFS(G, root) is
2 let Q be a queue
3 label root as discovered
4 Q.enqueue(root)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as discovered then
11 label w as discovered
12 w.parent := v
13 Q.enqueue(w)
अधिक जानकारी
संपादित करेंयह गैर-पुनरावर्ती(non-recursive) कार्यान्वयन गहराई-प्रधान खोज के गैर-पुनरावर्ती कार्यान्वयन के समान है, लेकिन दो तरीकों से इसमें भिन्नता है:
- यह एक स्टैक के बजाय एक कतार(queue) (फर्स्ट इन फर्स्ट आउट) का उपयोग करता है।
- यह जाँचता है कि क्या नोड कतारबद्ध करने से पहले खोजी जा चुकी है,बजाए की इस जांच को नोड को कतार से हटाते समय करने के।
यदि G एक ट्री है, विस्तार-प्रधान खोज की कलन विधि में कतार को स्टैक में बदलने से गहराई-प्रधान खोज कलन विधि प्राप्त होती है। सामान्य ग्राफ के लिए गहराई-प्रधान खोज की पुनरावृत्ति कार्यान्वयन में स्टैक को कतार से बदलने पर विस्तार-प्रधान खोज कलन विधि प्राप्त होती है,परन्तु सामान्य से भिन्न[8]।
कतार Q उन नोड्स को रखता है जिनमे अभी खोज हो रही है।
कार्यान्वयन के आधार पर,नोड्स को जांचा हुआ(discovered) चिन्हित करने के लिए उन्हें एक सेट में संगृहीत किया जा सकता है अथवा इस जानकारी को नोड में के ही एक गुण(attribute) के तौर पर रखा जा सकता है।
प्रत्ये नोड का 'मूल'(parent) गुण नोड्स तक जाने वाले सबसे छोटे मार्ग को जानने के लिए इस्तेमाल किया जाता है। विस्तार-प्रधान खोज को चलने से विस्तार-प्रधान ट्री(Breadth-first Tree) का निर्माण होता है,जिसे नीचे दिए उदहारण में देखा जा सकता है।
उदहारण
संपादित करेंनिम्नलिखित फ्रैंकफर्ट से शुरू होने वाले जर्मन शहरों पर बीएफएस चलाकर प्राप्त किए गए विस्तार-प्रधान ट्री का एक उदाहरण है:
जर्मनी का एक नक्शा (एक ग्राफ़ के रूप में दिया गया) जो कई ग्राफ़ खोज एल्गोरिदम के लिए उदाहरण के लिए आधार के रूप में काम कर सकता है[9]।
विश्लेषण
संपादित करेंसामयिक जटिलता एवं स्थान जटिलता (Time Complexity and Space Complexity)
संपादित करेंसामयिक जटिलता को O(|V|+|E|) के रूप में दर्शाया जा सकता है ,जहाँ V सिरों(Vertex/Nodes) की संख्या सामयिक जटिलता E किनारों(Edges) की संख्या है। ऐसा इसलिए क्यूंकि निकृष्टतम समय में खोज हर सिरे एवं किनारे की जांच करेगी।
जब ग्राफ में सिरों की संख्या समय से पहले पता हो ,और अतिरिक्त डेटा संरचनाओं का उपयोग यह निर्धारित करने के लिए किया गया हो कि कतार में कौन से सिरे पहले से ही जोड़े गए हैं, तब स्थान जटिलता O(|V|) के रूप में व्यक्त की जा सकती है। यह ग्राफ़ के लिए आवश्यक स्थान के अतिरिक्त है, जो कि कलन विधि के कार्यान्वयन द्वारा उपयोग किए गए ग्राफ़ प्रतिनिधित्व के आधार पर भिन्न हो सकता है।
संपूर्णता
संपादित करेंकलन विधियों के विश्लेषण में, विस्तार-प्रधान खोज के इनपुट को एक परिमित(finite) ग्राफ माना जाता है, जिसे स्पष्ट रूप से एक आसन्न सूची(Adjacency list), आसन्न मैट्रिक्स(Adjacency Matrix), या इसी तरह के प्रतिनिधित्व के रूप में दर्शाया गया हो। हालांकि, आर्टिफिशियल इंटेलिजेंस में ग्राफ ट्रावर्सल विधियों के अनुप्रयोग में इनपुट एक अनंत ग्राफ का निहित प्रतिनिधित्व हो सकता है। इस संदर्भ में, एक खोज विधि को पूर्ण होने के रूप में वर्णित किया जाता है यदि वह लक्ष्य अवस्था के मौजूद होने पर उसको ढूंढ़ने की गारंटी देती है। विस्तार-प्रधान खोज पूर्ण है, लेकिन गहराई-प्रधान खोज नहीं। जब स्पष्ट रूप से प्रतिनिधित्व किए गए अनंत ग्राफ पर लागू किया जाता है, तो विस्तार-प्रधान खोज में अंततः लक्ष्य स्थिति मिल जाएगी, लेकिन गहराई-प्रधान खोज ग्राफ़ के उन हिस्सों में खो सकती है, जिनके पास कोई लक्ष्य स्थिति नहीं है[10]।
उपयोग
संपादित करेंउदाहरण के लिए, ग्राफ थ्योरी में कई समस्याओं को हल करने के लिए विस्तार-प्रधान खोज का उपयोग किया जा सकता है:
- दो नोड्स u और v के बीच सबसे छोटा रास्ता खोजना, किनारों की संख्या द्वारा मापी गई लंबाई के साथ (गहराई-प्रधान खोज से बेहतर)
- (रिवर्स) कटहिल-मैकी मैश नंबरिंग
- एक फ्लो नेटवर्क में अधिकतम फ्लो की गणना के लिए फोर्ड-फुलकर्सन विधि
- ग्राफ में बाईपारटाइट गुण की जांच करना
सन्दर्भ
संपादित करें- ↑ "Graph 500 Benchmark 1 ("Search") | Graph 500". web.archive.org. 2015-03-26. मूल से पुरालेखित 26 मार्च 2015. अभिगमन तिथि 2020-08-23.सीएस1 रखरखाव: BOT: original-url status unknown (link)
- ↑ El-Sharoud, Walid (2019-09). "Book Review: Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliford Stein, Introduction to algorithms". Science Progress. 102 (3): 278–279. आइ॰एस॰एस॰एन॰ 0036-8504. डीओआइ:10.1177/0036850419873799b.
|date=में तिथि प्राचल का मान जाँचें (मदद) - ↑ "Konrad Zuse in Hopferau — Z4 und Plankalkül", Historische Notizen zur Informatik, Springer Berlin Heidelberg, पपृ॰ 198–203, आई॰ऍस॰बी॰ऍन॰ 978-3-540-85789-1, अभिगमन तिथि 2020-08-23
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald; Stein, Clifford (2017-01-31). Algorithmen - Eine Einführung. Berlin, Boston: De Gruyter. आई॰ऍस॰बी॰ऍन॰ 978-3-11-052201-3.
- ↑ Skiena, Steven S. (2012), "Sorting and Searching", The Algorithm Design Manual (अंग्रेज़ी में), Springer London, पपृ॰ 103–144, आई॰ऍस॰बी॰ऍन॰ 978-1-84800-069-8, डीओआइ:10.1007/978-1-84800-070-4_4, अभिगमन तिथि 2020-08-23
- ↑ Lee, C. Y. (1961-09). "An Algorithm for Path Connections and Its Applications". IEEE Transactions on Electronic Computers. EC-10 (3): 346–365. आइ॰एस॰एस॰एन॰ 0367-7508. डीओआइ:10.1109/TEC.1961.5219222.
|date=में तिथि प्राचल का मान जाँचें (मदद) - ↑ Lee, C. Y. (1961-09). "An Algorithm for Path Connections and Its Applications". IEEE Transactions on Electronic Computers. EC-10 (3): 346–365. आइ॰एस॰एस॰एन॰ 0367-7508. डीओआइ:10.1109/TEC.1961.5219222.
|date=में तिथि प्राचल का मान जाँचें (मदद) - ↑ Gongye, Xiaoyan; Wang, Yutian; Wen, Yulian; Nie, Peiyao; Lin, Peiguang (2020-05-09). "A simple detection and generation algorithm for simple circuits in directed graph based on depth-first traversal". Evolutionary Intelligence. आइ॰एस॰एस॰एन॰ 1864-5909. डीओआइ:10.1007/s12065-020-00416-6.
- ↑ Konieczny, S; Lang, J; Marquis, P (2004-08). "DA2 merging operators". Artificial Intelligence. 157 (1–2): 49–79. आइ॰एस॰एस॰एन॰ 0004-3702. डीओआइ:10.1016/j.artint.2004.04.008.
|date=में तिथि प्राचल का मान जाँचें (मदद) - ↑ Konieczny, S; Lang, J; Marquis, P (2004-08). "DA2 merging operators". Artificial Intelligence. 157 (1–2): 49–79. आइ॰एस॰एस॰एन॰ 0004-3702. डीओआइ:10.1016/j.artint.2004.04.008.
|date=में तिथि प्राचल का मान जाँचें (मदद)