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

एक हैश तालिका का दृश्य प्रतिनिधित्व, एक डेटा संरचना जो सूचना के तेजी से पुनर्प्राप्ति की अनुमति देती है

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

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

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

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

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

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

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

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

कक्षाएं

आभासी खोज स्थानों के लिए

See also: Solver

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

• Backward induction
• Content-addressable memory हार्डवेयर
• Dual-phase evolution
• Linear search problem
• No free lunch in search and optimization
• Recommender system, बहुत बड़े डेटा सेट में परिणामों को रैंक करने के लिए सांख्यिकीय विधियों का भी उपयोग करें
• Search engine (computing)
• Search game
• Selection algorithm
• Solver
• Sorting algorithm, कुछ खोज एल्गोरिदम को क्रियान्वित करने के लिए आवश्यक है
• Web search engine

श्रेणियाँ:

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

संदर्भ

ग्रन्थसूची

किताबें

• 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.