खोज समस्या: Difference between revisions
From Vigyanwiki
(Created page with "{{multiple issues| {{Refimprove|date=December 2013}} {{Confusing|date=December 2011}} {{one source|date=June 2016}} }} कम्प्यूटेशनल जटिलत...") |
No edit summary |
||
| Line 1: | Line 1: | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]][[संगणनीयता सिद्धांत]] सिद्धांत और [[निर्णय समस्या]] के गणित में एक खोज समस्या एक प्रकार की [[कम्प्यूटेशनल समस्या]] है जो [[ द्विआधारी संबंध | द्विआधारी संबंध]] द्वारा प्रस्तुत की जाती है। सहजता से समस्या वस्तु x में संरचना y खोजने में होती है। एक एल्गोरिदम को समस्या को हल करने के लिए कहा जाता है यदि कम से कम एक संबंधित संरचना उपस्थित है और फिर इस संरचना की एक घटना को आउटपुट बनाया जाता है अन्यथा, [[कलन विधि]] एक उपयुक्त आउटपुट (नहीं मिला या इस तरह का कोई संदेश) के साथ बंद हो जाता है। | |||
[[कम्प्यूटेशनल जटिलता सिद्धांत]][[संगणनीयता सिद्धांत]] सिद्धांत और [[निर्णय समस्या]] के गणित में | |||
प्रत्येक खोज समस्या में एक संबंधित निर्णय समस्या भी होती है | प्रत्येक खोज समस्या में एक संबंधित निर्णय समस्या भी होती है अर्थात् | ||
:<math>L(R)=\{x\mid \exists y R(x,y)\}. \, </math> | :<math>L(R)=\{x\mid \exists y R(x,y)\}. \, </math> | ||
इस परिभाषा को किसी भी उपयुक्त एन्कोडिंग का उपयोग करके एन-आरी संबंधों के लिए सामान्यीकृत किया जा सकता है जो कई स्ट्रिंग्स को एक स्ट्रिंग में संपीड़ित करने की अनुमति देता है (उदाहरण के लिए उन्हें एक सीमांकक के साथ | इस परिभाषा को किसी भी उपयुक्त एन्कोडिंग का उपयोग करके एन-आरी संबंधों के लिए सामान्यीकृत किया जा सकता है जो कई स्ट्रिंग्स को एक स्ट्रिंग में संपीड़ित करने की अनुमति देता है (उदाहरण के लिए उन्हें एक सीमांकक के साथ निरंतर सूचीबद्ध करके)। | ||
अधिक औपचारिक रूप से | अधिक औपचारिक रूप से एक संबंध R को एक खोज समस्या के रूप में देखा जा सकता है और एक ट्यूरिंग मशीन जो R की गणना करती है उसे हल करने के लिए भी कहा जाता है। अधिक औपचारिक रूप से यदि R एक द्विआधारी संबंध है जैसे कि क्षेत्र (R) ⊆ Γ<sup>+</sup> और T एक [[ट्यूरिंग मशीन]] है, तो T, R की गणना करता है यदि: | ||
* यदि x ऐसा है कि कुछ y ऐसा है कि R(x, y) तो T आउटपुट z के साथ x को स्वीकार करता है जैसे कि R(x, z) (कई y हो सकते हैं | * यदि x ऐसा है कि कुछ y ऐसा है कि R(x, y) तो T आउटपुट z के साथ x को स्वीकार करता है जैसे कि R(x, z) (कई y हो सकते हैं और T को उनमें से केवल एक को खोजने की आवश्यकता है) | ||
* यदि x ऐसा है कि कोई y ऐसा नहीं है कि R(x, y) तो T, x को अस्वीकार करता है | * यदि x ऐसा है कि कोई y ऐसा नहीं है कि R(x, y) तो T, x को अस्वीकार करता है | ||
(ध्यान दें कि एक आंशिक | (ध्यान दें कि एक आंशिक फलन का [[गुट (ग्राफ सिद्धांत)]] संबंध है और यदि T एक आंशिक फलन की गणना करता है तो अधिकतम एक संभावित आउटपुट होता है।) | ||
इस तरह की समस्याएं [[ ग्राफ सिद्धांत ]] और [[संयोजन अनुकूलन]] में बहुत बार होती हैं | इस तरह की समस्याएं [[ ग्राफ सिद्धांत ]]और [[संयोजन अनुकूलन]] में बहुत बार होती हैं उदाहरण के लिए जहाँ विशेष मिलान (ग्राफ़ सिद्धांत) वैकल्पिक क्लिक (ग्राफ़ सिद्धांत ), विशेष स्वतंत्र सेट (ग्राफ़ सिद्धांत)आदि जैसी संरचनाओं की खोज रुचि के विषय हैं। | ||
== परिभाषा == | == परिभाषा == | ||
एक खोज समस्या की विशेषता | एक खोज समस्या की विशेषता अधिकांशतः होती है:<ref name=Brown>{{cite web|last=Leyton-Brown|first=Kevin|title=रेखाचित्र खोज|url=http://www.cs.ubc.ca/~kevinlb/teaching/cs322%20-%202009-10/Lectures/Search2.pdf|publisher=ubc|accessdate=7 February 2013}}</ref> | ||
अवस्था का एक सेट (कंप्यूटर विज्ञान) | |||
* एक प्रारंभिक अवस्था | * एक प्रारंभिक अवस्था | ||
* एक लक्ष्य स्थिति या लक्ष्य परीक्षण: एक बूलियन | * एक लक्ष्य स्थिति या लक्ष्य परीक्षण: एक बूलियन फलन जो हमें बताता है कि दी गई स्थिति एक लक्ष्य स्थिति है या नहीं | ||
* एक [[उत्तराधिकारी समारोह]]: एक | * एक [[उत्तराधिकारी समारोह|उत्तराधिकारी कार्य]] : एक अवस्था से नए अवस्था के एक सेट के लिए एक मानचित्रण | ||
== उद्देश्य == | == उद्देश्य == | ||
जब किसी समस्या को हल करने के लिए एल्गोरिथम नहीं दिया जाता है, किंतु समाधान कैसा दिखता है इसका केवल एक विवरण दिया जाता है,तो एक समाधान खोजें।<ref name=Brown /> | |||
== खोज विधि == | == खोज विधि == | ||
* सामान्य खोज एल्गोरिदम: एक ग्राफ दिया गया है, नोड्स प्रारंभ करें, और लक्ष्य नोड्स, प्रारंभ नोड्स से बढ़ते पथों का पता लगाएं। | * सामान्य खोज एल्गोरिदम: एक ग्राफ दिया गया है, नोड्स प्रारंभ करें, और लक्ष्य नोड्स, प्रारंभ नोड्स से बढ़ते पथों का पता लगाएं। | ||
* खोजे गए प्रारंभ नोड से पथों की सीमा बनाए रखें। | * खोजे गए प्रारंभ नोड से पथों की सीमा बनाए रखें। | ||
* जैसे-जैसे खोज आगे बढ़ती है | *जैसे-जैसे खोज आगे बढ़ती है लक्ष्य नोड का सामना होने तक फ्रंटियर अस्पष्टीकृत नोड्स में फैलता है। | ||
* जिस तरह से सीमा का विस्तार किया जाता है वह खोज रणनीति को परिभाषित करता है।<ref name=Brown /> | * जिस तरह से सीमा का विस्तार किया जाता है वह खोज रणनीति को परिभाषित करता है।<ref name=Brown /> | ||
इनपुट: एक ग्राफ, | '''इनपुट: एक ग्राफ,'''<syntaxhighlight> | ||
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 | |||
</syntaxhighlight> | |||
स्टार्ट नोड्स का एक सेट, | स्टार्ट नोड्स का एक सेट, | ||
बूलियन प्रक्रिया लक्ष्य (एन) जो परीक्षण करता है कि एन लक्ष्य नोड है या नहीं। | बूलियन प्रक्रिया लक्ष्य (एन) जो परीक्षण करता है कि एन लक्ष्य नोड है या नहीं। | ||
| Line 52: | Line 60: | ||
* [[अनुकूलन समस्या]] | * [[अनुकूलन समस्या]] | ||
* [[गिनती की समस्या (जटिलता)]] | * [[गिनती की समस्या (जटिलता)]] | ||
*[[ समारोह की समस्या ]] | *[[ समारोह की समस्या | कार्य की समस्या]] | ||
* [[खोज खेल]] | * [[खोज खेल]] | ||
Revision as of 15:58, 25 May 2023
कम्प्यूटेशनल जटिलता सिद्धांतसंगणनीयता सिद्धांत सिद्धांत और निर्णय समस्या के गणित में एक खोज समस्या एक प्रकार की कम्प्यूटेशनल समस्या है जो द्विआधारी संबंध द्वारा प्रस्तुत की जाती है। सहजता से समस्या वस्तु 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 एक आंशिक फलन की गणना करता है तो अधिकतम एक संभावित आउटपुट होता है।)
इस तरह की समस्याएं ग्राफ सिद्धांत और संयोजन अनुकूलन में बहुत बार होती हैं उदाहरण के लिए जहाँ विशेष मिलान (ग्राफ़ सिद्धांत) वैकल्पिक क्लिक (ग्राफ़ सिद्धांत ), विशेष स्वतंत्र सेट (ग्राफ़ सिद्धांत)आदि जैसी संरचनाओं की खोज रुचि के विषय हैं।
परिभाषा
एक खोज समस्या की विशेषता अधिकांशतः होती है:[1]
अवस्था का एक सेट (कंप्यूटर विज्ञान)
- एक प्रारंभिक अवस्था
- एक लक्ष्य स्थिति या लक्ष्य परीक्षण: एक बूलियन फलन जो हमें बताता है कि दी गई स्थिति एक लक्ष्य स्थिति है या नहीं
- एक उत्तराधिकारी कार्य : एक अवस्था से नए अवस्था के एक सेट के लिए एक मानचित्रण
उद्देश्य
जब किसी समस्या को हल करने के लिए एल्गोरिथम नहीं दिया जाता है, किंतु समाधान कैसा दिखता है इसका केवल एक विवरण दिया जाता है,तो एक समाधान खोजें।[1]
खोज विधि
- सामान्य खोज एल्गोरिदम: एक ग्राफ दिया गया है, नोड्स प्रारंभ करें, और लक्ष्य नोड्स, प्रारंभ नोड्स से बढ़ते पथों का पता लगाएं।
- खोजे गए प्रारंभ नोड से पथों की सीमा बनाए रखें।
- जैसे-जैसे खोज आगे बढ़ती है लक्ष्य नोड का सामना होने तक फ्रंटियर अस्पष्टीकृत नोड्स में फैलता है।
- जिस तरह से सीमा का विस्तार किया जाता है वह खोज रणनीति को परिभाषित करता है।[1]
इनपुट: एक ग्राफ,
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> जोड़ें;
जबकि समाप्त करें
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 1.2 Leyton-Brown, Kevin. "रेखाचित्र खोज" (PDF). ubc. Retrieved 7 February 2013.
This article incorporates material from search problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
