खोज समस्या

कम्प्यूटेशनल जटिलता सिद्धांतसंगणनीयता सिद्धांत सिद्धांत और निर्णय समस्या के गणित में, एक खोज समस्या एक प्रकार की कम्प्यूटेशनल समस्या है जो द्विआधारी संबंध द्वारा प्रस्तुत की जाती है। सहजता से, समस्या वस्तु 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 एक आंशिक फ़ंक्शन की गणना करता है तो अधिकतम एक संभावित आउटपुट होता है।)

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

परिभाषा

एक खोज समस्या की विशेषता अक्सर होती है: * राज्य का एक सेट (कंप्यूटर विज्ञान)

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

उद्देश्य

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

खोज विधि

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

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

       स्टार्ट नोड्स का एक सेट,
       बूलियन प्रक्रिया लक्ष्य (एन) जो परीक्षण करता है कि एन लक्ष्य नोड है या नहीं।
   फ्रंटियर := {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.