खोज समस्या

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

प्रत्येक खोज समस्या में एक संबंधित निर्णय समस्या भी होती है अर्थात्

$L(R)=\{x\mid \exists yR(x,y)\}.\,$

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

अधिक औपचारिक रूप से एक संबंध R को एक खोज समस्या के रूप में देखा जा सकता है और एक ट्यूरिंग मशीन जो R की गणना करती है उसे हल करने के लिए भी कहा जाता है। अधिक औपचारिक रूप से यदि R एक द्विआधारी संबंध है जैसे कि क्षेत्र (R) ⊆ Γ⁺ और T एक ट्यूरिंग मशीन है, तो T, R की गणना करता है यदि:

• यदि x ऐसा है कि कुछ y ऐसा है कि R(x, y) तो T आउटपुट z के साथ x को स्वीकार करता है जैसे कि R(x, z) (कई y हो सकते हैं और T को उनमें से केवल एक को खोजने की आवश्यकता है)
• यदि x ऐसा है कि कोई y ऐसा नहीं है कि R(x, y) तो T, x को अस्वीकार करता है

(ध्यान दें कि एक आंशिक फलन का गुट (ग्राफ सिद्धांत) संबंध है और यदि T एक आंशिक फलन की गणना करता है तो अधिकतम एक संभावित आउटपुट होता है।)

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

परिभाषा

एक खोज समस्या की विशेषता अधिकांशतः होती है:

अवस्था का एक सेट (कंप्यूटर विज्ञान)

• एक प्रारंभिक अवस्था
• एक लक्ष्य स्थिति या लक्ष्य परीक्षण: एक बूलियन फलन जो हमें बताता है कि दी गई स्थिति एक लक्ष्य स्थिति है या नहीं
• एक उत्तराधिकारी कार्य : एक अवस्था से नए अवस्था के एक सेट के लिए एक मानचित्रण

उद्देश्य

जब किसी समस्या को हल करने के लिए एल्गोरिथम नहीं दिया जाता है, किंतु समाधान कैसा दिखता है इसका केवल एक विवरण दिया जाता है,तो एक समाधान खोजें।

खोज विधि

• सामान्य खोज एल्गोरिदम: एक ग्राफ दिया गया है, नोड्स प्रारंभ करें, और लक्ष्य नोड्स, प्रारंभ नोड्स से बढ़ते पथों का पता लगाएं।
• खोजे गए प्रारंभ नोड से पथों की सीमा बनाए रखें।
• जैसे-जैसे खोज आगे बढ़ती है लक्ष्य नोड का सामना होने तक फ्रंटियर अस्पष्टीकृत नोड्स में फैलता है।
• जिस तरह से सीमा का विस्तार किया जाता है वह खोज रणनीति को परिभाषित करता है।

इनपुट: एक ग्राफ,

 Input: a graph,
       a set of start nodes,
       Boolean procedure goal(n) that tests if n is a goal node.
   frontier := {s : s is a start node};
   while frontier is not empty:
       select and remove path <n0, ..., nk> from frontier;
       if goal(nk)
           return <n0, ..., nk>;
       for every neighbor n of nk
           add <n0, ..., nk, n> to frontier;
   end while

       स्टार्ट नोड्स का एक सेट,
       बूलियन प्रक्रिया लक्ष्य (एन) जो परीक्षण करता है कि एन लक्ष्य नोड है या नहीं।
   फ्रंटियर := {s : s एक स्टार्ट नोड है};
   जबकि सीमांत खाली नहीं है:
       पथ का चयन करें और हटाएं <n0, ..., nk> सीमा से;
       अगर लक्ष्य (एनके)
           वापसी <n0, ..., एनके>;
       एनके के हर पड़ोसी एन के लिए
           फ्रंटियर में <n0, ..., nk, n> जोड़ें;
   जबकि समाप्त करें

यह भी देखें

• असीमित खोज ऑपरेटर
• निर्णय समस्या
• अनुकूलन समस्या
• गिनती की समस्या (जटिलता)
• कार्य की समस्या
• खोज खेल

संदर्भ

This article incorporates material from search problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.