खोज एल्गोरिदम

From Vigyanwiki
Revision as of 10:57, 4 July 2023 by Indicwiki (talk | contribs) (9 revisions imported from alpha:खोज_एल्गोरिदम)
हैश तालिका का दृश्य प्रतिनिधित्व, डेटा संरचना जो सूचना के तेजी से पुनर्प्राप्ति की अनुमति देती है

कंप्यूटर विज्ञान में, सर्च कलन विधि एक एल्गोरिथम है जिसे सर्च समस्या को हल करने के लिए डिज़ाइन किया गया है। सर्च एल्गोरिदम विशेष डेटा संरचना के अन्दर संग्रहीत जानकारी को पुनः प्राप्त करने के लिए काम करते हैं, या किसी समस्या डोमेन के व्यवहार्य क्षेत्र में निरंतर या असतत चर के साथ गणना की जाती है।

चूँकि सर्च इंजन (कंप्यूटिंग) एल्गोरिदम का उपयोग करते हैं, किन्तु वे सूचना पुनर्प्राप्ति के अध्ययन से संबंधित हैं, एल्गोरिथम के अध्ययन से संबंधित नहीं हैं।

उपयोग करने के लिए उपयुक्त सर्च एल्गोरिदम अधिकांशतः खोजी जा रही डेटा संरचना पर निर्भर करता है, और इसमें डेटा के बारे में पूर्व ज्ञान भी सम्मिलित हो सकता है। विशेष रूप से निर्मित डेटाबेस संरचनाओं का उपयोग किया जाता है, जैसे सर्च ट्री , हैश मैप और डेटाबेस सूचकांक द्वारा सर्च एल्गोरिदम को तेज या अधिक कुशल बनाया जा सकता है।[1][2]

सर्च एल्गोरिदम को तीन प्रकार के एल्गोरिदम में सर्च करने के उनके तंत्र के आधार पर वर्गीकृत किया जा सकता है: रैखिक, बाइनरी और हैशिंग रेखीय सर्च एल्गोरिदम रेखीय फैशन में लक्ष्य कुंजी से जुड़े प्रत्येक आवरण की जांच करता है।[3] बाइनरी सर्च एल्गोरिद्म बाइनरी, या आधा-अंतराल, सर्च बार-बार सर्च संरचना के केंद्र को लक्षित करती है और सर्च स्पेस को आधे में विभाजित करती है। सर्च एल्गोरिदम लक्ष्य आवरण मिलने तक कुंजियों की तुलना के आधार पर क्रमिक रूप से आवरण को समाप्त करके रैखिक सर्च में सुधार करते हैं, और परिभाषित क्रम के साथ डेटा संरचनाओं पर प्रयुक्त किया जा सकता है।[4] डिजिटल सर्च एल्गोरिथम संख्यात्मक कुंजियों का उपयोग करके डेटा संरचनाओं में अंकों के गुणों के आधार पर कार्य करता है।[5] अंत में, हैश तालिका सीधे कुंजी को हैश फंकशन के आधार पर आवरण करने के लिए मैप करती है।[6]

एल्गोरिदम का मूल्यांकन अधिकांशतः उनकी कम्प्यूटेशनल जटिलता, या अधिकतम सैद्धांतिक रन टाइम द्वारा किया जाता है। उदाहरण के लिए, बाइनरी सर्च फ़ंक्शंस की अधिकतम जटिलता है O(log n), या लघुगणकीय समय सरल शब्दों में, सर्च लक्ष्य को खोजने के लिए आवश्यक संचालन की अधिकतम संख्या सर्च स्पेस के आकार का लघुगणकीय कार्य है।

सर्च एल्गोरिदम के अनुप्रयोग

सर्च एल्गोरिदम के विशिष्ट अनुप्रयोगों में सम्मिलित हैं:

वर्ग

वर्चुअल सर्च स्पेस के लिए

वर्चुअल स्पेस की सर्च के लिए एल्गोरिदम का उपयोग कॉन्सट्रेंट सटिस्फैक्शन समस्या में किया जाता है, जहां लक्ष्य कुछ चर के लिए मान असाइनमेंट का सेट खोजता है जो विशिष्ट गणितीय समीकरण और असमानताओं/समानताओं को संतुष्ट करता है। उनका उपयोग तब भी किया जाता है जब लक्ष्य चर असाइनमेंट खोजना होता है जो उन चरों के निश्चित कार्य को असतत करता है। इन समस्याओं के लिए एल्गोरिदम में मूलभूत ब्रूट-बल सर्च और कई प्रकार के ह्यूरिस्टिक कार्य सम्मिलित हैं जो इस स्पेस की संरचना के बारे में आंशिक ज्ञान का लाभ उठाने का प्रयाश करते हैं, जैसे लीनियर रिलैक्सेशन कंस्ट्रेंट जनरेशन और कंस्ट्रेंट प्रोपेगेशन होता है। .

महत्वपूर्ण उपवर्ग लोकल सर्च (अनुकूलन) विधियाँ हैं, जो सर्च स्पेस के तत्वों को ग्राफ के शीर्ष (ग्राफ़ सिद्धांत) के रूप में देखती हैं, किनारों के साथ स्थिति पर प्रयुक्त अनुमानों के सेट द्वारा परिभाषित है और किनारों के साथ आइटम से आइटम पर जाकर स्पेस को स्कैन करते है, उदाहरण के लिए तीव्रतम अवरोहण या क्रूर-बल सर्च या बेस्ट-फर्स्ट मानदंड के अनुसार, या स्टोचैस्टिक अनुकूलन में इस श्रेणी में सामान्य मेटाह्यूरिस्टिक विधियों की विशाल विविधता सम्मिलित है, जैसे तैयार कि हुयी धातु पे पानी चढाने की कला , तब्बू सर्च, ए-टीम्स और जेनेटिक प्रोग्रामिंग है, जो विशिष्ट विधियों से मनमाने ह्यूरिस्टिक्स को जोड़ती हैं। लोकल सर्च के विपरीत वैश्विक सर्च विधियाँ होंटी है। यह विधि तब प्रयुक्त होती है जब सर्च स्पेस सीमित नहीं होता है और दिए गए नेटवर्क के सभी स्टोकेस्टिक खोज एल्गोरिथम चलाने वाली इकाई के लिए उपलब्ध होते हैं।[7]

इस वर्ग में विभिन्न ट्री ट्रैवर्सल भी सम्मिलित हैं, जो तत्वों को ट्री के शीर्ष के रूप में देखते हैं (ग्राफ सिद्धांत), और उस ट्री को कुछ विशेष क्रम में पार करते हैं। उत्तरार्द्ध के उदाहरणों में विस्तृत विधियाँ सम्मिलित हैं जैसे कि प्रूनिंग-ट्री सर्च और चौड़ाई-पहली सर्च, साथ ही विभिन्न ह्यूरिस्टिक-आधारित निर्णय वृक्ष विधियाँ है जैसे बैक ट्रैकिंग और शाखा और बाउंड या सामान्य मेटाह्यूरिस्टिक्स के विपरीत, जो केवल संभाव्य अर्थ में सबसे अच्छा काम करता है, इनमें से कई ट्री-सर्च विधियों को पर्याप्त समय दिए जाने पर स्पष्ट या ऑप्टीमल समाधान खोजने की गारंटी दी जाती है। इसे पूर्णता कहते हैं।

अन्य महत्वपूर्ण उप-वर्ग में शतरंज या चौसर जैसे बहु-खिलाड़ी गेम ट्री कों सर्च करने के लिए एल्गोरिदम सम्मिलित हैं, जिनके नोड्स में सभी संभावित गेम स्थितियां सम्मिलित हैं जो वर्तमान स्थिति से उत्पन्न हो सकती हैं। इन समस्याओं में लक्ष्य उस चाल का पता लगाना है जो प्रतिद्वंद्वीओं की सभी संभावित चालों को ध्यान में रखते हुए जीत का सबसे अच्छा अवसर प्रदान करती है। इसी तरह की समस्याएं तब होती हैं जब मनुष्यों या मशीनों को निरंतर निर्णय लेने पड़ते हैं जिनके परिणाम पूरी तरह से किसी के नियंत्रण में नहीं होते हैं, जैसे कि रोबोट मार्गदर्शन या विपणन, वित्त या सैन्य रणनीति योजना में इस तरह की समस्या संयुक्त सर्च का कृत्रिम इंटेलिजेंस के संदर्भ में बड़े मापदंड पर अध्ययन किया गया है। इस वर्ग के लिए एल्गोरिदम के उदाहरण मिनिमैक्स एल्गोरिथम अल्फा बीटा प्रूनिंग और a * एल्गोरिथम और इसके वेरिएंट हैं।

किसी दिए गए रुपरेखा के उप-संरचनाओं के लिए

संयोजी सर्च नाम सामान्यतः एल्गोरिदम के लिए उपयोग किया जाता है जो किसी दिए गए असतत गणित की विशिष्ट उप-संरचना की खोज करता है, जैसे कि ग्राफ, स्ट्रिंग (कंप्यूटर विज्ञान), परिमित समूह (गणित), और इसी तरह या कॉम्बिनेटरियल ऑप्टिमाइज़ेशन शब्द का उपयोग सामायतः तब किया जाता है जब लक्ष्य कुछ मापदंड के अधिकतम (या न्यूनतम) मान के साथ उप-संरचना को खोजना होता है। (चूंकि उप-संरचना को सामायतः कंप्यूटर में बाधाओं के साथ पूर्णांक चर के सेट द्वारा दर्शाया जाता है, इन समस्याओं को कॉन्सट्रेंट सटिस्फैक्शन या असतत अनुकूलन के विशेष स्थितियों के रूप में देखा जा सकता है; किन्तु वे सामायतः अधिक सार सेटिंग में तैयार और हल किए जाते हैं जहां आंतरिक प्रतिनिधित्व का स्पष्ट रूप से उल्लेख नहीं किया गया है।)

महत्वपूर्ण और बड़े मापदंड पर अध्ययन किए गए उपवर्ग एल्गोरिदम ग्राफ़ एल्गोरिदम की सूची हैं, विशेष रूप से ग्राफ ट्रैवर्सल एल्गोरिदम में, किसी दिए गए ग्राफ़ में विशिष्ट उप-संरचनाओं को खोजने के लिए पथ (ग्राफ सिद्धांत) की शब्दावली सबग्राफ, पथ (ग्राफ़ सिद्धांत), सर्किट, और इसी प्रकार उदाहरणों में दिज्क्स्ट्रा का एल्गोरिथ्म, क्रुस्कल का एल्गोरिथ्म, निकटतम समूह एल्गोरिथ्म और प्राइम का एल्गोरिथ्म सम्मिलित हैं।

इस श्रेणी का अन्य महत्वपूर्ण उपवर्ग स्ट्रिंग सर्च एल्गोरिथ्म है, जो स्ट्रिंग्स के अन्दर प्रतिरूप को सर्च करता है। दो प्रसिद्ध उदाहरण हैं बोयर-मूर स्ट्रिंग-सर्च एल्गोरिथम या बॉयर-मूर और नुथ-मॉरिस-प्रैट एल्गोरिदम, और प्रत्यय ट्री डेटा संरचना पर आधारित कई एल्गोरिदम है।

किसी फ़ंक्शन के अधिकतम के लिए खोजें

1953 में, अमेरिकी सांख्यिकीविद् जैक कीफ़र (सांख्यिकीविद्) ने फाइबोनैचि सर्च विधि तैयार की थी, जिसका उपयोग अनिमॉडल फ़ंक्शन का अधिकतम पता लगाने के लिए किया जा सकता है और कंप्यूटर विज्ञान में इसके कई अन्य अनुप्रयोग हैं।

क्वांटम कंप्यूटर के लिए

ग्रोवर के एल्गोरिथ्म की तरह क्वांटम कम्प्यूटिंग के लिए डिज़ाइन किए गए सर्च विधि भी हैं, जो डेटा संरचनाओं या ह्यूरिस्टिक्स की सहायता के बिना भी सैद्धांतिक रूप से रैखिक या पाशविक बल सर्च से तेज़ हैं। जबकि क्वांटम कंप्यूटर के पीछे के विचार और अनुप्रयोग अभी भी पूरी तरह से सैद्धांतिक हैं, ग्रोवर जैसे एल्गोरिदम के साथ अध्ययन किए गए हैं जो क्वांटम कंप्यूटिंग सिस्टम के काल्पनिक भौतिक संस्करणों को स्पष्ट रूप से दोहराते हैं।[8]

यह भी देखें

श्रेणियाँ:

  • :श्रेणी:खोज एल्गोरिदम

संदर्भ

उद्धरण

  1. Beame & Fich 2002, p. 39.
  2. Knuth 1998, §6.5 ("Retrieval on Secondary Keys").
  3. Knuth 1998, §6.1 ("Sequential Searching").
  4. Knuth 1998, §6.2 ("Searching by Comparison of Keys").
  5. Knuth 1998, §6.3 (Digital Searching).
  6. Knuth 1998, §6.4, (Hashing).
  7. Hunter, A.H.; Pippenger, Nicholas (4 July 2013). "चैनल ग्राफ़ में स्थानीय बनाम वैश्विक खोज". Networks: An International Journey. arXiv:1004.2526.
  8. López, G V; Gorin, T; Lara, L (26 February 2008). "पहले और दूसरे-निकटतम-पड़ोसी युग्मन के साथ एक आइसिंग-परमाणु-स्पिन-श्रृंखला क्वांटम कंप्यूटर में ग्रोवर की क्वांटम खोज एल्गोरिथ्म का अनुकरण". Journal of Physics B: Atomic, Molecular and Optical Physics. 41 (5): 055504. arXiv:0710.3196. Bibcode:2008JPhB...41e5504L. doi:10.1088/0953-4075/41/5/055504. S2CID 18796310.

ग्रन्थसूची

किताबें

लेख

बाहरी संबंध