खोज एल्गोरिदम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Any algorithm which solves the search problem}} | {{short description|Any algorithm which solves the search problem}} | ||
[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|upright=1.2|एक [[हैश तालिका]] का दृश्य प्रतिनिधित्व, एक [[डेटा संरचना]] जो सूचना के तेजी से पुनर्प्राप्ति की अनुमति देती है]][[कंप्यूटर विज्ञान]] में, एक सर्च [[ कलन विधि ]] एक एल्गोरिथम है जिसे एक [[खोज समस्या|सर्च समस्या]] को हल करने के लिए डिज़ाइन किया गया है। सर्च एल्गोरिदम विशेष डेटा संरचना के अन्दर संग्रहीत जानकारी को पुनः प्राप्त करने के लिए काम करते हैं, या किसी समस्या डोमेन के व्यवहार्य क्षेत्र में [[निरंतर या असतत चर]] के साथ गणना की जाती है। | [[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|upright=1.2|एक [[हैश तालिका]] का दृश्य प्रतिनिधित्व, एक [[डेटा संरचना]] जो सूचना के तेजी से पुनर्प्राप्ति की अनुमति देती है]][[कंप्यूटर विज्ञान]] में, एक सर्च [[ कलन विधि |कलन विधि]] एक एल्गोरिथम है जिसे एक [[खोज समस्या|सर्च समस्या]] को हल करने के लिए डिज़ाइन किया गया है। सर्च एल्गोरिदम विशेष डेटा संरचना के अन्दर संग्रहीत जानकारी को पुनः प्राप्त करने के लिए काम करते हैं, या किसी समस्या डोमेन के व्यवहार्य क्षेत्र में [[निरंतर या असतत चर]] के साथ गणना की जाती है। | ||
चूँकि [[खोज इंजन (कंप्यूटिंग)|सर्च इंजन (कंप्यूटिंग)]] एल्गोरिदम का उपयोग करते हैं, किन्तु वे सूचना पुनर्प्राप्ति के अध्ययन से संबंधित हैं, एल्गोरिथम के अध्ययन से संबंधित नहीं हैं। | चूँकि [[खोज इंजन (कंप्यूटिंग)|सर्च इंजन (कंप्यूटिंग)]] एल्गोरिदम का उपयोग करते हैं, किन्तु वे सूचना पुनर्प्राप्ति के अध्ययन से संबंधित हैं, एल्गोरिथम के अध्ययन से संबंधित नहीं हैं। | ||
उपयोग करने के लिए उपयुक्त सर्च एल्गोरिदम अधिकांशतः खोजी जा रही डेटा संरचना पर निर्भर करता है, और इसमें डेटा के बारे में पूर्व ज्ञान भी सम्मिलित हो सकता है। विशेष रूप से निर्मित डेटाबेस संरचनाओं, जैसे [[ खोज पेड़ | सर्च ट्री]] , [[हैश मैप]] और [[ डेटाबेस सूचकांक | डेटाबेस सूचकांक]] द्वारा सर्च एल्गोरिदम को तेज या अधिक कुशल बनाया जा सकता है।{{Sfn|Beame|Fich|2002|p=39}}{{Sfn|Knuth|1998|loc=§6.5 ("Retrieval on Secondary Keys")}} | उपयोग करने के लिए उपयुक्त सर्च एल्गोरिदम अधिकांशतः खोजी जा रही डेटा संरचना पर निर्भर करता है, और इसमें डेटा के बारे में पूर्व ज्ञान भी सम्मिलित हो सकता है। विशेष रूप से निर्मित डेटाबेस संरचनाओं, जैसे [[ खोज पेड़ |सर्च ट्री]] , [[हैश मैप]] और [[ डेटाबेस सूचकांक |डेटाबेस सूचकांक]] द्वारा सर्च एल्गोरिदम को तेज या अधिक कुशल बनाया जा सकता है।{{Sfn|Beame|Fich|2002|p=39}}{{Sfn|Knuth|1998|loc=§6.5 ("Retrieval on Secondary Keys")}} | ||
सर्च एल्गोरिदम को तीन प्रकार के एल्गोरिदम में सर्च करने के उनके तंत्र के आधार पर वर्गीकृत किया जा सकता है: रैखिक, बाइनरी और हैशिंग रेखीय सर्च एल्गोरिदम एक रेखीय फैशन में लक्ष्य कुंजी से जुड़े प्रत्येक आवरण की जांच करता है।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential Searching")}} बाइनरी सर्च एल्गोरिद्म बाइनरी, या आधा-अंतराल, सर्च बार-बार सर्च संरचना के केंद्र को लक्षित करती है और सर्च स्पेस को आधे में विभाजित करती है। सर्च एल्गोरिदम लक्ष्य आवरण मिलने तक कुंजियों की तुलना के आधार पर क्रमिक रूप से आवरण को समाप्त करके रैखिक सर्च में सुधार करते हैं, और एक परिभाषित क्रम के साथ डेटा संरचनाओं पर प्रयुक्त किया जा सकता है।{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison of Keys")}} डिजिटल सर्च एल्गोरिथम संख्यात्मक कुंजियों का उपयोग करके डेटा संरचनाओं में अंकों के गुणों के आधार पर कार्य करता है।{{Sfn|Knuth|1998|loc=§6.3 (Digital Searching)}} अंत में, हैश तालिका सीधे कुंजी को [[हैश फंकशन]] के आधार पर आवरण करने के लिए मैप करती है।{{Sfn|Knuth|1998|loc=§6.4, (Hashing)}} | सर्च एल्गोरिदम को तीन प्रकार के एल्गोरिदम में सर्च करने के उनके तंत्र के आधार पर वर्गीकृत किया जा सकता है: रैखिक, बाइनरी और हैशिंग रेखीय सर्च एल्गोरिदम एक रेखीय फैशन में लक्ष्य कुंजी से जुड़े प्रत्येक आवरण की जांच करता है।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential Searching")}} बाइनरी सर्च एल्गोरिद्म बाइनरी, या आधा-अंतराल, सर्च बार-बार सर्च संरचना के केंद्र को लक्षित करती है और सर्च स्पेस को आधे में विभाजित करती है। सर्च एल्गोरिदम लक्ष्य आवरण मिलने तक कुंजियों की तुलना के आधार पर क्रमिक रूप से आवरण को समाप्त करके रैखिक सर्च में सुधार करते हैं, और एक परिभाषित क्रम के साथ डेटा संरचनाओं पर प्रयुक्त किया जा सकता है।{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison of Keys")}} डिजिटल सर्च एल्गोरिथम संख्यात्मक कुंजियों का उपयोग करके डेटा संरचनाओं में अंकों के गुणों के आधार पर कार्य करता है।{{Sfn|Knuth|1998|loc=§6.3 (Digital Searching)}} अंत में, हैश तालिका सीधे कुंजी को [[हैश फंकशन]] के आधार पर आवरण करने के लिए मैप करती है।{{Sfn|Knuth|1998|loc=§6.4, (Hashing)}} | ||
| Line 21: | Line 23: | ||
** मानचित्र में रंग भरने की समस्या | ** मानचित्र में रंग भरने की समस्या | ||
** [[सुडोकू]] या वर्ग पहेली भरना | ** [[सुडोकू]] या वर्ग पहेली भरना | ||
* [[ खेल सिद्धांत | खेल सिद्धांत]] | * [[ खेल सिद्धांत | खेल सिद्धांत]] और विशेष रूप से [[कॉम्बिनेटरियल गेम थ्योरी|कॉम्बिनेटरियल गेम सिद्धांत]] में, अगला बनाने के लिए सबसे अच्छा कदम चुनना (जैसे कि [[ न्यूनतम अधिकतम |न्यूनतम अधिकतम]] एल्गोरिथम के साथ) | ||
* संभावनाओं के पूरे सेट से एक संयोजन या पासवर्ड खोजना | * संभावनाओं के पूरे सेट से एक संयोजन या पासवर्ड खोजना | ||
* [[गुणन]]खंड एक पूर्णांक ([[क्रिप्टोग्राफी]] में एक महत्वपूर्ण समस्या) | * [[गुणन]]खंड एक पूर्णांक ([[क्रिप्टोग्राफी]] में एक महत्वपूर्ण समस्या) | ||
| Line 36: | Line 38: | ||
वर्चुअल स्पेस की सर्च के लिए एल्गोरिदम का उपयोग [[बाधा संतुष्टि समस्या|कॉन्सट्रेंट सटिस्फैक्शन समस्या]] में किया जाता है, जहां लक्ष्य कुछ चर के लिए मान असाइनमेंट का एक सेट खोजना है जो विशिष्ट गणितीय [[समीकरण]] और [[असमानता]]ओं/समानताओं को संतुष्ट करता है। उनका उपयोग तब भी किया जाता है जब लक्ष्य एक चर असाइनमेंट खोजना होता है जो उन चरों के एक निश्चित कार्य को असतत करता है। इन समस्याओं के लिए एल्गोरिदम में मूलभूत ब्रूट-बल सर्च (जिसे भोली या बेख़बर सर्च भी कहा जाता है), और कई प्रकार के ह्यूरिस्टिक कार्य सम्मिलित हैं जो इस स्पेस की संरचना के बारे में आंशिक ज्ञान का लाभ उठाने का प्रयाश करते हैं, जैसे लीनियर रिलैक्सेशन कंस्ट्रेंट जनरेशन और कंस्ट्रेंट प्रोपेगेशन होता है। . | वर्चुअल स्पेस की सर्च के लिए एल्गोरिदम का उपयोग [[बाधा संतुष्टि समस्या|कॉन्सट्रेंट सटिस्फैक्शन समस्या]] में किया जाता है, जहां लक्ष्य कुछ चर के लिए मान असाइनमेंट का एक सेट खोजना है जो विशिष्ट गणितीय [[समीकरण]] और [[असमानता]]ओं/समानताओं को संतुष्ट करता है। उनका उपयोग तब भी किया जाता है जब लक्ष्य एक चर असाइनमेंट खोजना होता है जो उन चरों के एक निश्चित कार्य को असतत करता है। इन समस्याओं के लिए एल्गोरिदम में मूलभूत ब्रूट-बल सर्च (जिसे भोली या बेख़बर सर्च भी कहा जाता है), और कई प्रकार के ह्यूरिस्टिक कार्य सम्मिलित हैं जो इस स्पेस की संरचना के बारे में आंशिक ज्ञान का लाभ उठाने का प्रयाश करते हैं, जैसे लीनियर रिलैक्सेशन कंस्ट्रेंट जनरेशन और कंस्ट्रेंट प्रोपेगेशन होता है। . | ||
एक महत्वपूर्ण उपवर्ग [[स्थानीय खोज (अनुकूलन)|लोकल सर्च (अनुकूलन)]] विधियाँ हैं, जो सर्च स्पेस के तत्वों को ग्राफ के शीर्ष (ग्राफ़ सिद्धांत) के रूप में देखती हैं, किनारों के साथ स्थिति पर प्रयुक्त अनुमानों के एक सेट द्वारा परिभाषित है और किनारों के साथ आइटम से आइटम पर जाकर स्पेस को स्कैन करते है, उदाहरण के लिए [[ ढतला हुआ वंश | तीव्रतम अवरोहण]] या [[क्रूर-बल खोज|क्रूर-बल सर्च]] या बेस्ट-फर्स्ट मानदंड के अनुसार, या [[स्टोचैस्टिक अनुकूलन]] में इस श्रेणी में सामान्य [[मेटाह्यूरिस्टिक]] विधियों की एक विशाल विविधता सम्मिलित है, जैसे [[ तैयार किए हुयी धातु पे पानी चढाने की कला | तैयार कि हुयी धातु पे पानी चढाने की कला]] , [[तब्बू खोज|तब्बू सर्च]], ए-टीम्स और [[ आनुवंशिक प्रोग्रामिंग | जेनेटिक प्रोग्रामिंग]] है, जो विशिष्ट विधियों से मनमाने ह्यूरिस्टिक्स को जोड़ती हैं। लोकल सर्च के विपरीत वैश्विक सर्च विधियाँ होंटी है। यह विधि तब प्रयुक्त होती है जब सर्च स्पेस सीमित नहीं होता है और दिए गए नेटवर्क के सभी [[सर्वोत्तम-पहली खोज|स्टोकेस्टिक खोज]] एल्गोरिथम चलाने वाली इकाई के लिए उपलब्ध होते हैं।<ref>{{Cite journal|last1=Hunter|first1=A.H.|last2=Pippenger|first2=Nicholas|date=4 July 2013|title=चैनल ग्राफ़ में स्थानीय बनाम वैश्विक खोज|journal=Networks: An International Journey|arxiv=1004.2526}}</ref> | एक महत्वपूर्ण उपवर्ग [[स्थानीय खोज (अनुकूलन)|लोकल सर्च (अनुकूलन)]] विधियाँ हैं, जो सर्च स्पेस के तत्वों को ग्राफ के शीर्ष (ग्राफ़ सिद्धांत) के रूप में देखती हैं, किनारों के साथ स्थिति पर प्रयुक्त अनुमानों के एक सेट द्वारा परिभाषित है और किनारों के साथ आइटम से आइटम पर जाकर स्पेस को स्कैन करते है, उदाहरण के लिए [[ ढतला हुआ वंश |तीव्रतम अवरोहण]] या [[क्रूर-बल खोज|क्रूर-बल सर्च]] या बेस्ट-फर्स्ट मानदंड के अनुसार, या [[स्टोचैस्टिक अनुकूलन]] में इस श्रेणी में सामान्य [[मेटाह्यूरिस्टिक]] विधियों की एक विशाल विविधता सम्मिलित है, जैसे [[ तैयार किए हुयी धातु पे पानी चढाने की कला |तैयार कि हुयी धातु पे पानी चढाने की कला]] , [[तब्बू खोज|तब्बू सर्च]], ए-टीम्स और [[ आनुवंशिक प्रोग्रामिंग |जेनेटिक प्रोग्रामिंग]] है, जो विशिष्ट विधियों से मनमाने ह्यूरिस्टिक्स को जोड़ती हैं। लोकल सर्च के विपरीत वैश्विक सर्च विधियाँ होंटी है। यह विधि तब प्रयुक्त होती है जब सर्च स्पेस सीमित नहीं होता है और दिए गए नेटवर्क के सभी [[सर्वोत्तम-पहली खोज|स्टोकेस्टिक खोज]] एल्गोरिथम चलाने वाली इकाई के लिए उपलब्ध होते हैं।<ref>{{Cite journal|last1=Hunter|first1=A.H.|last2=Pippenger|first2=Nicholas|date=4 July 2013|title=चैनल ग्राफ़ में स्थानीय बनाम वैश्विक खोज|journal=Networks: An International Journey|arxiv=1004.2526}}</ref> | ||
इस वर्ग में विभिन्न [[ट्री ट्रैवर्सल]] भी सम्मिलित हैं, जो तत्वों को ट्री के शीर्ष के रूप में देखते हैं (ग्राफ सिद्धांत), और उस ट्री को कुछ विशेष क्रम में पार करते हैं। उत्तरार्द्ध के उदाहरणों में विस्तृत विधियाँ सम्मिलित हैं जैसे कि [[गहराई-पहली खोज|प्रूनिंग-ट्री सर्च]] और चौड़ाई-पहली सर्च, साथ ही विभिन्न ह्यूरिस्टिक-आधारित निर्णय वृक्ष विधियाँ है जैसे [[ बैक ट्रैकिंग | बैक ट्रैकिंग]] और शाखा और बाउंड या सामान्य मेटाह्यूरिस्टिक्स के विपरीत, जो केवल एक संभाव्य अर्थ में सबसे अच्छा काम करता है, इनमें से कई ट्री-सर्च विधियों को पर्याप्त समय दिए जाने पर स्पष्ट या ऑप्टीमल समाधान खोजने की गारंटी दी जाती है। इसे [[पूर्णता (तर्क)|पूर्णता]] कहते हैं। | इस वर्ग में विभिन्न [[ट्री ट्रैवर्सल]] भी सम्मिलित हैं, जो तत्वों को ट्री के शीर्ष के रूप में देखते हैं (ग्राफ सिद्धांत), और उस ट्री को कुछ विशेष क्रम में पार करते हैं। उत्तरार्द्ध के उदाहरणों में विस्तृत विधियाँ सम्मिलित हैं जैसे कि [[गहराई-पहली खोज|प्रूनिंग-ट्री सर्च]] और चौड़ाई-पहली सर्च, साथ ही विभिन्न ह्यूरिस्टिक-आधारित निर्णय वृक्ष विधियाँ है जैसे [[ बैक ट्रैकिंग |बैक ट्रैकिंग]] और शाखा और बाउंड या सामान्य मेटाह्यूरिस्टिक्स के विपरीत, जो केवल एक संभाव्य अर्थ में सबसे अच्छा काम करता है, इनमें से कई ट्री-सर्च विधियों को पर्याप्त समय दिए जाने पर स्पष्ट या ऑप्टीमल समाधान खोजने की गारंटी दी जाती है। इसे [[पूर्णता (तर्क)|पूर्णता]] कहते हैं। | ||
एक अन्य महत्वपूर्ण उप-वर्ग में [[शतरंज]] या [[चौसर]] जैसे बहु-खिलाड़ी[[ खेल का पेड़ | खेल का ट्री]] की सर्च के लिए एल्गोरिदम सम्मिलित हैं, जिनके नोड्स में सभी संभावित गेम स्थितियां सम्मिलित हैं जो वर्तमान स्थिति से उत्पन्न हो सकती हैं। इन समस्याओं में लक्ष्य उस चाल का पता लगाना है जो प्रतिद्वंद्वीओं की सभी संभावित चालों को ध्यान में रखते हुए जीत का सबसे अच्छा मौका प्रदान करती है। इसी तरह की समस्याएं तब होती हैं जब मनुष्यों या मशीनों को निरंतर निर्णय लेने पड़ते हैं जिनके परिणाम पूरी तरह से किसी के नियंत्रण में नहीं होते हैं, जैसे कि [[रोबोट]] मार्गदर्शन या [[विपणन]], [[वित्त]] या [[सैन्य]] रणनीति योजना में इस तरह की समस्या [[संयुक्त खोज|संयुक्त सर्च]] का [[ कृत्रिम होशियारी | कृत्रिम इंटेलिजेंस]] के संदर्भ में बड़े मापदंड पर अध्ययन किया गया है। इस वर्ग के लिए एल्गोरिदम के उदाहरण मिनिमैक्स एल्गोरिथम अल्फा बीटा प्रूनिंग और ए * एल्गोरिथम और इसके वेरिएंट हैं। | एक अन्य महत्वपूर्ण उप-वर्ग में [[शतरंज]] या [[चौसर]] जैसे बहु-खिलाड़ी[[ खेल का पेड़ | खेल का ट्री]] की सर्च के लिए एल्गोरिदम सम्मिलित हैं, जिनके नोड्स में सभी संभावित गेम स्थितियां सम्मिलित हैं जो वर्तमान स्थिति से उत्पन्न हो सकती हैं। इन समस्याओं में लक्ष्य उस चाल का पता लगाना है जो प्रतिद्वंद्वीओं की सभी संभावित चालों को ध्यान में रखते हुए जीत का सबसे अच्छा मौका प्रदान करती है। इसी तरह की समस्याएं तब होती हैं जब मनुष्यों या मशीनों को निरंतर निर्णय लेने पड़ते हैं जिनके परिणाम पूरी तरह से किसी के नियंत्रण में नहीं होते हैं, जैसे कि [[रोबोट]] मार्गदर्शन या [[विपणन]], [[वित्त]] या [[सैन्य]] रणनीति योजना में इस तरह की समस्या [[संयुक्त खोज|संयुक्त सर्च]] का [[ कृत्रिम होशियारी |कृत्रिम इंटेलिजेंस]] के संदर्भ में बड़े मापदंड पर अध्ययन किया गया है। इस वर्ग के लिए एल्गोरिदम के उदाहरण मिनिमैक्स एल्गोरिथम अल्फा बीटा प्रूनिंग और ए * एल्गोरिथम और इसके वेरिएंट हैं। | ||
=== किसी दिए गए रुपरेखा के उप-संरचनाओं के लिए === | === किसी दिए गए रुपरेखा के उप-संरचनाओं के लिए === | ||
| Line 53: | Line 55: | ||
=== क्वांटम कंप्यूटर के लिए === | === क्वांटम कंप्यूटर के लिए === | ||
ग्रोवर के एल्गोरिथ्म की तरह [[ क्वांटम कम्प्यूटिंग ]] के लिए डिज़ाइन किए गए सर्च विधि भी हैं, जो डेटा संरचनाओं या ह्यूरिस्टिक्स की सहायता के बिना भी सैद्धांतिक रूप से रैखिक या क्रूर-बल सर्च से तेज़ हैं। जबकि क्वांटम कंप्यूटर के पीछे के विचार और अनुप्रयोग अभी भी पूरी तरह से सैद्धांतिक हैं, ग्रोवर जैसे एल्गोरिदम के साथ अध्ययन किए गए हैं जो क्वांटम कंप्यूटिंग सिस्टम के काल्पनिक भौतिक संस्करणों को स्पष्ट रूप से दोहराते हैं।<ref>{{Cite journal|last1=López|first1=G V|last2=Gorin|first2=T|last3=Lara|first3=L|date=26 February 2008|title=पहले और दूसरे-निकटतम-पड़ोसी युग्मन के साथ एक आइसिंग-परमाणु-स्पिन-श्रृंखला क्वांटम कंप्यूटर में ग्रोवर की क्वांटम खोज एल्गोरिथ्म का अनुकरण|journal=Journal of Physics B: Atomic, Molecular and Optical Physics|volume=41|issue=5|page=055504|doi=10.1088/0953-4075/41/5/055504|arxiv=0710.3196|bibcode=2008JPhB...41e5504L|s2cid=18796310}}</ref> | ग्रोवर के एल्गोरिथ्म की तरह [[ क्वांटम कम्प्यूटिंग |क्वांटम कम्प्यूटिंग]] के लिए डिज़ाइन किए गए सर्च विधि भी हैं, जो डेटा संरचनाओं या ह्यूरिस्टिक्स की सहायता के बिना भी सैद्धांतिक रूप से रैखिक या क्रूर-बल सर्च से तेज़ हैं। जबकि क्वांटम कंप्यूटर के पीछे के विचार और अनुप्रयोग अभी भी पूरी तरह से सैद्धांतिक हैं, ग्रोवर जैसे एल्गोरिदम के साथ अध्ययन किए गए हैं जो क्वांटम कंप्यूटिंग सिस्टम के काल्पनिक भौतिक संस्करणों को स्पष्ट रूप से दोहराते हैं।<ref>{{Cite journal|last1=López|first1=G V|last2=Gorin|first2=T|last3=Lara|first3=L|date=26 February 2008|title=पहले और दूसरे-निकटतम-पड़ोसी युग्मन के साथ एक आइसिंग-परमाणु-स्पिन-श्रृंखला क्वांटम कंप्यूटर में ग्रोवर की क्वांटम खोज एल्गोरिथ्म का अनुकरण|journal=Journal of Physics B: Atomic, Molecular and Optical Physics|volume=41|issue=5|page=055504|doi=10.1088/0953-4075/41/5/055504|arxiv=0710.3196|bibcode=2008JPhB...41e5504L|s2cid=18796310}}</ref> | ||
== यह भी देखें == | == यह भी देखें == | ||
| Line 74: | Line 74: | ||
==संदर्भ== | ==संदर्भ== | ||
===उद्धरण=== | ===उद्धरण=== | ||
{{Reflist|30em}} | {{Reflist|30em}} | ||
===ग्रन्थसूची=== | ===ग्रन्थसूची=== | ||
====किताबें==== | ====किताबें==== | ||
*{{TAOCP|volume=3|edition=2}} | *{{TAOCP|volume=3|edition=2}} | ||
Revision as of 15:06, 18 June 2023
कंप्यूटर विज्ञान में, एक सर्च कलन विधि एक एल्गोरिथम है जिसे एक सर्च समस्या को हल करने के लिए डिज़ाइन किया गया है। सर्च एल्गोरिदम विशेष डेटा संरचना के अन्दर संग्रहीत जानकारी को पुनः प्राप्त करने के लिए काम करते हैं, या किसी समस्या डोमेन के व्यवहार्य क्षेत्र में निरंतर या असतत चर के साथ गणना की जाती है।
चूँकि सर्च इंजन (कंप्यूटिंग) एल्गोरिदम का उपयोग करते हैं, किन्तु वे सूचना पुनर्प्राप्ति के अध्ययन से संबंधित हैं, एल्गोरिथम के अध्ययन से संबंधित नहीं हैं।
उपयोग करने के लिए उपयुक्त सर्च एल्गोरिदम अधिकांशतः खोजी जा रही डेटा संरचना पर निर्भर करता है, और इसमें डेटा के बारे में पूर्व ज्ञान भी सम्मिलित हो सकता है। विशेष रूप से निर्मित डेटाबेस संरचनाओं, जैसे सर्च ट्री , हैश मैप और डेटाबेस सूचकांक द्वारा सर्च एल्गोरिदम को तेज या अधिक कुशल बनाया जा सकता है।[1][2]
सर्च एल्गोरिदम को तीन प्रकार के एल्गोरिदम में सर्च करने के उनके तंत्र के आधार पर वर्गीकृत किया जा सकता है: रैखिक, बाइनरी और हैशिंग रेखीय सर्च एल्गोरिदम एक रेखीय फैशन में लक्ष्य कुंजी से जुड़े प्रत्येक आवरण की जांच करता है।[3] बाइनरी सर्च एल्गोरिद्म बाइनरी, या आधा-अंतराल, सर्च बार-बार सर्च संरचना के केंद्र को लक्षित करती है और सर्च स्पेस को आधे में विभाजित करती है। सर्च एल्गोरिदम लक्ष्य आवरण मिलने तक कुंजियों की तुलना के आधार पर क्रमिक रूप से आवरण को समाप्त करके रैखिक सर्च में सुधार करते हैं, और एक परिभाषित क्रम के साथ डेटा संरचनाओं पर प्रयुक्त किया जा सकता है।[4] डिजिटल सर्च एल्गोरिथम संख्यात्मक कुंजियों का उपयोग करके डेटा संरचनाओं में अंकों के गुणों के आधार पर कार्य करता है।[5] अंत में, हैश तालिका सीधे कुंजी को हैश फंकशन के आधार पर आवरण करने के लिए मैप करती है।[6]
एल्गोरिदम का मूल्यांकन अधिकांशतः उनकी कम्प्यूटेशनल जटिलता, या अधिकतम सैद्धांतिक रन टाइम द्वारा किया जाता है। उदाहरण के लिए, बाइनरी सर्च फ़ंक्शंस की अधिकतम जटिलता है O(log n), या लघुगणकीय समय सरल शब्दों में, सर्च लक्ष्य को खोजने के लिए आवश्यक संचालन की अधिकतम संख्या सर्च स्पेस के आकार का लघुगणकीय कार्य है।
सर्च एल्गोरिदम के अनुप्रयोग
सर्च एल्गोरिदम के विशिष्ट अनुप्रयोगों में सम्मिलित हैं:
- कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में समस्याएँ, जैसे:
- वाहन रूटिंग समस्या, सबसे छोटी पथ समस्या का एक रूप है
- नैपसैक समस्या: वस्तुओं का एक सेट दिया गया है, प्रत्येक वजन और मूल्य के साथ, संग्रह में सम्मिलित करने के लिए प्रत्येक आइटम की संख्या निर्धारित करते है जिससे कुल वजन किसी सीमा से कम या उसके समान किया जा सके और जिससे कुल मूल्य में वृद्धि की जा सकती है।
- नर्स शेड्यूलिंग समस्या
- कॉन्सट्रेंट सटिस्फैक्शन में समस्याएँ, जैसे:
- मानचित्र में रंग भरने की समस्या
- सुडोकू या वर्ग पहेली भरना
- खेल सिद्धांत और विशेष रूप से कॉम्बिनेटरियल गेम सिद्धांत में, अगला बनाने के लिए सबसे अच्छा कदम चुनना (जैसे कि न्यूनतम अधिकतम एल्गोरिथम के साथ)
- संभावनाओं के पूरे सेट से एक संयोजन या पासवर्ड खोजना
- गुणनखंड एक पूर्णांक (क्रिप्टोग्राफी में एक महत्वपूर्ण समस्या)
- प्रक्रिया के मापदंडों (जैसे तापमान, दबाव और पीएच) को बदलकर एक औद्योगिक प्रक्रिया का अनुकूलन, जैसे रासायनिक प्रतिक्रिया
- एक डेटाबेस से एक आवरण पुनर्प्राप्त करना
- किसी सूची (सार डेटा प्रकार) या सरणी डेटा संरचना में अधिकतम या न्यूनतम मान खोजना
- यह देखने के लिए जाँच की जा रही है कि मानों के सेट में दिया गया मान उपस्थित है या नहीं उपस्थित है
वर्ग
वर्चुअल सर्च स्पेस के लिए
वर्चुअल स्पेस की सर्च के लिए एल्गोरिदम का उपयोग कॉन्सट्रेंट सटिस्फैक्शन समस्या में किया जाता है, जहां लक्ष्य कुछ चर के लिए मान असाइनमेंट का एक सेट खोजना है जो विशिष्ट गणितीय समीकरण और असमानताओं/समानताओं को संतुष्ट करता है। उनका उपयोग तब भी किया जाता है जब लक्ष्य एक चर असाइनमेंट खोजना होता है जो उन चरों के एक निश्चित कार्य को असतत करता है। इन समस्याओं के लिए एल्गोरिदम में मूलभूत ब्रूट-बल सर्च (जिसे भोली या बेख़बर सर्च भी कहा जाता है), और कई प्रकार के ह्यूरिस्टिक कार्य सम्मिलित हैं जो इस स्पेस की संरचना के बारे में आंशिक ज्ञान का लाभ उठाने का प्रयाश करते हैं, जैसे लीनियर रिलैक्सेशन कंस्ट्रेंट जनरेशन और कंस्ट्रेंट प्रोपेगेशन होता है। .
एक महत्वपूर्ण उपवर्ग लोकल सर्च (अनुकूलन) विधियाँ हैं, जो सर्च स्पेस के तत्वों को ग्राफ के शीर्ष (ग्राफ़ सिद्धांत) के रूप में देखती हैं, किनारों के साथ स्थिति पर प्रयुक्त अनुमानों के एक सेट द्वारा परिभाषित है और किनारों के साथ आइटम से आइटम पर जाकर स्पेस को स्कैन करते है, उदाहरण के लिए तीव्रतम अवरोहण या क्रूर-बल सर्च या बेस्ट-फर्स्ट मानदंड के अनुसार, या स्टोचैस्टिक अनुकूलन में इस श्रेणी में सामान्य मेटाह्यूरिस्टिक विधियों की एक विशाल विविधता सम्मिलित है, जैसे तैयार कि हुयी धातु पे पानी चढाने की कला , तब्बू सर्च, ए-टीम्स और जेनेटिक प्रोग्रामिंग है, जो विशिष्ट विधियों से मनमाने ह्यूरिस्टिक्स को जोड़ती हैं। लोकल सर्च के विपरीत वैश्विक सर्च विधियाँ होंटी है। यह विधि तब प्रयुक्त होती है जब सर्च स्पेस सीमित नहीं होता है और दिए गए नेटवर्क के सभी स्टोकेस्टिक खोज एल्गोरिथम चलाने वाली इकाई के लिए उपलब्ध होते हैं।[7]
इस वर्ग में विभिन्न ट्री ट्रैवर्सल भी सम्मिलित हैं, जो तत्वों को ट्री के शीर्ष के रूप में देखते हैं (ग्राफ सिद्धांत), और उस ट्री को कुछ विशेष क्रम में पार करते हैं। उत्तरार्द्ध के उदाहरणों में विस्तृत विधियाँ सम्मिलित हैं जैसे कि प्रूनिंग-ट्री सर्च और चौड़ाई-पहली सर्च, साथ ही विभिन्न ह्यूरिस्टिक-आधारित निर्णय वृक्ष विधियाँ है जैसे बैक ट्रैकिंग और शाखा और बाउंड या सामान्य मेटाह्यूरिस्टिक्स के विपरीत, जो केवल एक संभाव्य अर्थ में सबसे अच्छा काम करता है, इनमें से कई ट्री-सर्च विधियों को पर्याप्त समय दिए जाने पर स्पष्ट या ऑप्टीमल समाधान खोजने की गारंटी दी जाती है। इसे पूर्णता कहते हैं।
एक अन्य महत्वपूर्ण उप-वर्ग में शतरंज या चौसर जैसे बहु-खिलाड़ी खेल का ट्री की सर्च के लिए एल्गोरिदम सम्मिलित हैं, जिनके नोड्स में सभी संभावित गेम स्थितियां सम्मिलित हैं जो वर्तमान स्थिति से उत्पन्न हो सकती हैं। इन समस्याओं में लक्ष्य उस चाल का पता लगाना है जो प्रतिद्वंद्वीओं की सभी संभावित चालों को ध्यान में रखते हुए जीत का सबसे अच्छा मौका प्रदान करती है। इसी तरह की समस्याएं तब होती हैं जब मनुष्यों या मशीनों को निरंतर निर्णय लेने पड़ते हैं जिनके परिणाम पूरी तरह से किसी के नियंत्रण में नहीं होते हैं, जैसे कि रोबोट मार्गदर्शन या विपणन, वित्त या सैन्य रणनीति योजना में इस तरह की समस्या संयुक्त सर्च का कृत्रिम इंटेलिजेंस के संदर्भ में बड़े मापदंड पर अध्ययन किया गया है। इस वर्ग के लिए एल्गोरिदम के उदाहरण मिनिमैक्स एल्गोरिथम अल्फा बीटा प्रूनिंग और ए * एल्गोरिथम और इसके वेरिएंट हैं।
किसी दिए गए रुपरेखा के उप-संरचनाओं के लिए
संयोजी सर्च नाम सामान्यतः एल्गोरिदम के लिए उपयोग किया जाता है जो किसी दिए गए असतत गणित की एक विशिष्ट उप-संरचना की खोज करता है, जैसे कि एक ग्राफ, एक स्ट्रिंग (कंप्यूटर विज्ञान), एक परिमित समूह (गणित), और इसी तरह या कॉम्बिनेटरियल ऑप्टिमाइज़ेशन शब्द का उपयोग सामायतः तब किया जाता है जब लक्ष्य कुछ मापदंड के अधिकतम (या न्यूनतम) मान के साथ उप-संरचना को खोजना होता है। (चूंकि उप-संरचना को सामायतः कंप्यूटर में बाधाओं के साथ पूर्णांक चर के एक सेट द्वारा दर्शाया जाता है, इन समस्याओं को कॉन्सट्रेंट सटिस्फैक्शन या असतत अनुकूलन के विशेष स्थितियों के रूप में देखा जा सकता है; किन्तु वे सामायतः अधिक सार सेटिंग में तैयार और हल किए जाते हैं जहां आंतरिक प्रतिनिधित्व का स्पष्ट रूप से उल्लेख नहीं किया गया है।)
एक महत्वपूर्ण और बड़े मापदंड पर अध्ययन किए गए उपवर्ग एल्गोरिदम ग्राफ़ एल्गोरिदम की सूची हैं, विशेष रूप से ग्राफ ट्रैवर्सल एल्गोरिदम में, किसी दिए गए ग्राफ़ में विशिष्ट उप-संरचनाओं को खोजने के लिए पथ (ग्राफ सिद्धांत) की शब्दावली सबग्राफ, पथ (ग्राफ़ सिद्धांत), सर्किट, और इसी प्रकार उदाहरणों में दिज्क्स्ट्रा का एल्गोरिथ्म, क्रुस्कल का एल्गोरिथ्म, निकटतम समूह एल्गोरिथ्म और प्राइम का एल्गोरिथ्म सम्मिलित हैं।
इस श्रेणी का एक अन्य महत्वपूर्ण उपवर्ग स्ट्रिंग सर्च एल्गोरिथ्म है, जो स्ट्रिंग्स के अन्दर पैटर्न की सर्च करता है। दो प्रसिद्ध उदाहरण हैं बोयर-मूर स्ट्रिंग-सर्च एल्गोरिथम या बॉयर-मूर और नुथ-मॉरिस-प्रैट एल्गोरिदम, और प्रत्यय ट्री डेटा संरचना पर आधारित कई एल्गोरिदम है।
किसी फ़ंक्शन के अधिकतम के लिए खोजें
1953 में, अमेरिकी सांख्यिकीविद् जैक कीफ़र (सांख्यिकीविद्) ने फाइबोनैचि सर्च विधि तैयार की थी, जिसका उपयोग एक अनिमॉडल फ़ंक्शन का अधिकतम पता लगाने के लिए किया जा सकता है और कंप्यूटर विज्ञान में इसके कई अन्य अनुप्रयोग हैं।
क्वांटम कंप्यूटर के लिए
ग्रोवर के एल्गोरिथ्म की तरह क्वांटम कम्प्यूटिंग के लिए डिज़ाइन किए गए सर्च विधि भी हैं, जो डेटा संरचनाओं या ह्यूरिस्टिक्स की सहायता के बिना भी सैद्धांतिक रूप से रैखिक या क्रूर-बल सर्च से तेज़ हैं। जबकि क्वांटम कंप्यूटर के पीछे के विचार और अनुप्रयोग अभी भी पूरी तरह से सैद्धांतिक हैं, ग्रोवर जैसे एल्गोरिदम के साथ अध्ययन किए गए हैं जो क्वांटम कंप्यूटिंग सिस्टम के काल्पनिक भौतिक संस्करणों को स्पष्ट रूप से दोहराते हैं।[8]
यह भी देखें
- बैकवर्ड इंडक्शन
- कंटेंट-एड्रेसेबल मेमोरी हार्डवेयर
- डवल फेज एवोल्यूशन
- लीनियर सर्च प्रोबलम
- खोज और ऑप्टिमाइज़ेशन में कोई निःशुल्क लंच नहीं
- रेकोमेंडर सिस्टम, बहुत बड़े डेटा सेट में परिणामों को रैंक करने के लिए सांख्यिकीय विधियों का भी उपयोग करें
- सर्च इंजन (कम्प्यूटिंग)
- सर्च गेम
- सिलेक्शन एल्गोरिथ्म
- सॉल्वर
- सोर्टिंग एल्गोरिथ्म, कुछ सर्च एल्गोरिदम को क्रियान्वित करने के लिए आवश्यक है
- वेब सर्च इंजन
श्रेणियाँ:
- :श्रेणी:खोज एल्गोरिदम
संदर्भ
उद्धरण
- ↑ Beame & Fich 2002, p. 39.
- ↑ Knuth 1998, §6.5 ("Retrieval on Secondary Keys").
- ↑ Knuth 1998, §6.1 ("Sequential Searching").
- ↑ Knuth 1998, §6.2 ("Searching by Comparison of Keys").
- ↑ Knuth 1998, §6.3 (Digital Searching).
- ↑ Knuth 1998, §6.4, (Hashing).
- ↑ Hunter, A.H.; Pippenger, Nicholas (4 July 2013). "चैनल ग्राफ़ में स्थानीय बनाम वैश्विक खोज". Networks: An International Journey. arXiv:1004.2526.
- ↑ 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.
ग्रन्थसूची
किताबें
- Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
लेख
- Schmittou, Thomas; Schmittou, Faith E. (2002-08-01). "पूर्ववर्ती समस्या और संबंधित समस्याओं के लिए इष्टतम सीमा". Journal of Computer and System Sciences. 65 (1): 38–72. doi:10.1006/jcss.2002.1822.
बाहरी संबंध
- Uninformed Search Project at the Wikiversity.
