ऐडमिसिबल हेयुरिस्टिक: Difference between revisions

Latest revision as of 22:17, 10 October 2023

कंप्यूटर विज्ञान में, विशेष रूप से पाथफाइंडिंग से संबंधित एल्गोरिदम में, एक अनुमानी फ़ंक्शन को ऐडमिसिबल कहा जाता है यदि यह लक्ष्य तक पहुंचने की लागत को कभी भी कम नहीं करता है, यानी लक्ष्य तक पहुंचने के लिए यह जिस लागत का अनुमान लगाता है, वह पथ में वर्तमान बिंदु से न्यूनतम संभव लागत से अधिक नहीं है।^[1]

यह सतत अनुमानी की अवधारणा से संबंधित है। हालाँकि सभी सुसंगत अनुमान ऐडमिसिबल हैं, लेकिन सभी ऐडमिसिबल अनुमान सुसंगत नहीं हैं।

सर्च (सर्च) एल्गोरिदम

ऐडमिसिबल सर्च एल्गोरिदम में लक्ष्य स्थिति तक पहुंचने की लागत का अनुमान लगाने के लिए ऐडमिसिबल अनुमान का उपयोग किया जाता है। सर्च समस्या के लिए ऐडमिसिबल अनुमान के लिए, अनुमानित लागत हमेशा लक्ष्य स्थिति तक पहुंचने की वास्तविक लागत से कम या बराबर होनी चाहिए। सर्च एल्गोरिदम वर्तमान नोड से लक्ष्य स्थिति के लिए अनुमानित इष्टतम पथ खोजने के लिए ऐडमिसिबल अनुमानी का उपयोग करता है। उदाहरण के लिए, A* सर्च में मूल्यांकन फ़ंक्शन (जहां $n$ वर्तमान नोड है) है:

$f(n)=g(n)+h(n)$

जहाँ

f(n)

= मूल्यांकन फंक्शन.

g(n)

= प्रारंभ नोड से वर्तमान नोड तक की लागत

h(n)

= वर्तमान नोड से लक्ष्य तक अनुमानित लागत

$h(n)$ की गणना ह्यूरिस्टिक फ़ंक्शन का उपयोग करके की जाती है। गैर-ऐडमिसिबल अनुमान के साथ, A* एल्गोरिदम $f(n)$ में अधिक अनुमान के कारण सर्च समस्या के इष्टतम समाधान को अनदेखा कर सकता है।

फार्मूलेशन

n

एक नोड है

h

एक अनुमानी है

h(n)

n

से किसी लक्ष्य तक पहुंचने के लिए

h

द्वारा दर्शायी गई लागत है

h^{*}(n)

n

से किसी लक्ष्य तक पहुँचने के लिए इष्टतम लागत है

h(n)

ऐडमिसिबल है यदि,

\forall n

h(n)\leq h^{*}(n)

निर्माण

ऐडमिसिबल अनुमान समस्या के सुविधाजनक संस्करण से, या पैटर्न डेटाबेस से जानकारी द्वारा प्राप्त किया जा सकता है जो समस्या की उप-समस्याओं के सटीक समाधान संग्रहीत करता है, या आगमनात्मक शिक्षण विधियों का उपयोग करना है।

उदाहरण

फिफ्टीन पज़ल समस्या पर ऐडमिसिबल अनुमान के दो अलग-अलग उदाहरण प्रयुक्त होते हैं:

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

पजल की मैनहट्टन दूरी इस प्रकार परिभाषित की गई है:

h(n)=\sum _{\text{all tiles}}{\mathit {distance}}({\text{tile, correct position}})

नीचे दी गई पजल पर विचार करें जिसमें खिलाड़ी प्रत्येक टाइल को इस प्रकार हिलाना चाहता है कि संख्याएँ क्रमबद्ध हों। मैनहट्टन की दूरी इस स्थिति में ऐडमिसिबल अनुमान है क्योंकि प्रत्येक टाइल को अपने और उसकी सही स्थिति के बीच कम से कम स्थानों की संख्या को स्थानांतरित करना होगा।^[2]

4₃	6₁	3₀	8₁
7₂	12₃	9₃	14₄
15₃	13₂	1₄	5₄
2₄	10₁	11₁

सबस्क्रिप्ट प्रत्येक टाइल के लिए मैनहट्टन की दूरी दर्शाती है। प्रदर्शित पजल के लिए कुल मैनहट्टन दूरी है:

h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36

सर्वोत्तमता का प्रमाण

यदि किसी एल्गोरिदम में ऐडमिसिबल अनुमान का उपयोग किया जाता है, जो प्रति पुनरावृत्ति, केवल कई उम्मीदवार पथों के सबसे कम मूल्यांकन (वर्तमान लागत + अनुमानी) के पथ पर आगे बढ़ता है, तो उस क्षण समाप्त हो जाता है जब इसका अन्वेषण लक्ष्य तक पहुंचता है और, महत्वपूर्ण रूप से, समाप्त होने से पहले कभी भी सभी इष्टतम पथों को बंद नहीं किया जाता है (ऐसा कुछ जो A* सर्च एल्गोरिदम के साथ संभव है यदि विशेष देखभाल नहीं की जाती है ^[3]), तो यह एल्गोरिदम केवल एक इष्टतम पथ पर समाप्त हो सकता है। यह देखने के लिए कि, विरोधाभास द्वारा निम्नलिखित प्रमाण पर विचार करें:

मान लें कि इस तरह का एल्गोरिदम वास्तविक लागत के साथ पथ T पर समाप्त होने में कामयाब रहा, जो T_true के साथ इष्टतम पथ S से अधिक है। इसका मतलब यह है कि समाप्त होने से पहले, T की मूल्यांकन S_true की मूल्यांकन लागत से कम या उसके बराबर थी (अन्यथा S को चुना गया होता)। इन मूल्यांकन की गई लागतों को क्रमशः T_eval और S_eval निरूपित करें। उपर्युक्त को संक्षेप में इस प्रकार प्रस्तुत किया जा सकता है,

S_true < T_true

T_eval ≤ S_eval

यदि हमारा अनुमान ऐडमिसिबल है तो यह इस प्रकार है कि इस अंतिम चरण में T_eval = T_true है क्योंकि T पर अनुमान द्वारा वास्तविक लागत में कोई भी वृद्धि अस्वीकार्य होगी और अनुमान ऋणात्मक नहीं हो सकता है। दूसरी ओर, ऐडमिसिबल अनुमान के लिए S_eval ≤ S_true की आवश्यकता होगी जो उपरोक्त असमानताओं के साथ मिलकर हमें टेवल T_eval ≠ T_true और अधिक विशेष रूप से T_eval < T_true देता है। चूँकि T_eval और T_true समान और असमान दोनों नहीं हो सकते हैं, हमारी धारणा गलत रही होगी और इसलिए इष्टतम पथ से अधिक महंगे मार्ग पर समाप्त करना असंभव होगा।

उदाहरण के तौर पर, ^[4] मान लें कि हमारी लागत इस प्रकार है: (नोड के ऊपर/नीचे की लागत अनुमानी है, किनारे पर लागत वास्तविक लागत है)

  0     10   0   100   0
START ----  O  ----- GOAL
 |                   |
0|                   |100
 |                   | 
 O ------- O  ------ O
100   1    100   1   100

तो स्पष्ट रूप से हम शीर्ष मध्य नोड पर जाना शुरू करेंगे, क्योंकि अपेक्षित कुल लागत, अर्थात $f(n)$ , $10+0=10$ है तब लक्ष्य एक उम्मीदवार होगा, जिसमें $f(n)$ $10+100+0=110$ के बराबर होगा। फिर हम स्पष्ट रूप से एक के बाद एक नीचे के नोड्स को चुनेंगे, उसके बाद अद्यतन लक्ष्य, क्योंकि उन सभी का $f(n)$ वर्तमान लक्ष्य के $f(n)$ से कम है, अर्थात उनका $f(n)$ $100,101,102,102$ है। इसलिए भले ही लक्ष्य एक उम्मीदवार था, हम उसे नहीं चुन सके क्योंकि वहां अभी भी बेहतर रास्ते उपस्थित थे। इस तरह, ऐडमिसिबल अनुमान अनुकूलता सुनिश्चित कर सकता है।

हालाँकि, ध्यान दें कि यद्यपि ऐडमिसिबल अनुमान अंतिम इष्टतमता की गारंटी दे सकता है, लेकिन यह आवश्यक रूप से कुशल नहीं है।

संदर्भ

↑ Russell, S.J.; Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 0-13-790395-2.
↑ Korf, Richard E. (2000), "स्वीकार्य अनुमानी कार्यों के डिजाइन और विश्लेषण में हालिया प्रगति" (PDF), in Choueiry, Berthe Y.; Walsh, Toby (eds.), Abstraction, Reformulation, and Approximation: 4th International Symposium, SARA 2000 Horseshoe Bay, USA, July 26-29, 2000 Proceedings, vol. 1864, Springer, pp. 45–55, CiteSeerX 10.1.1.124.817, doi:10.1007/3-540-44914-0_3, ISBN 978-3-540-67839-7, retrieved 2010-04-26
↑ Holte, Robert (2005). "Common Misconceptions Concerning Heuristic Search". Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS).
↑ "Why do admissable [sic] heuristics guarantee optimality?". algorithm. Stack Overflow. Retrieved 2018-12-11.

यह भी देखें

सुसंगत अनुमानी
अनुमानी फंक्शन
सर्च एल्गोरिथ्म

[1] Russell, S.J.; Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 0-13-790395-2.

[Korf,2000-2] Korf, Richard E. (2000), "स्वीकार्य अनुमानी कार्यों के डिजाइन और विश्लेषण में हालिया प्रगति" (PDF), in Choueiry, Berthe Y.; Walsh, Toby (eds.), Abstraction, Reformulation, and Approximation: 4th International Symposium, SARA 2000 Horseshoe Bay, USA, July 26-29, 2000 Proceedings, vol. 1864, Springer, pp. 45–55, CiteSeerX 10.1.1.124.817, doi:10.1007/3-540-44914-0_3, ISBN 978-3-540-67839-7, retrieved 2010-04-26

[Misconceptions-3] Holte, Robert (2005). "Common Misconceptions Concerning Heuristic Search". Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS).

[4] "Why do admissable [sic] heuristics guarantee optimality?". algorithm. Stack Overflow. Retrieved 2018-12-11.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Computer science pathfinding concept}}
-[[कंप्यूटर विज्ञान]] में, विशेष रूप से [[ पथ खोज ]] से संबंधित [[कलन विधि]] में, एक अनुमानी फ़ंक्शन को स्वीकार्य कहा जाता है यदि यह लक्ष्य तक पहुंचने की लागत को कभी भी कम नहीं करता है, अर्थात लक्ष्य तक पहुंचने के लिए यह जिस लागत का अनुमान लगाता है वह वर्तमान से न्यूनतम संभव लागत से अधिक नहीं है पथ में इंगित करें.<ref>{{cite book
+कंप्यूटर विज्ञान में, विशेष रूप से पाथफाइंडिंग से संबंधित एल्गोरिदम में, एक अनुमानी फ़ंक्शन को '''ऐडमिसिबल''' कहा जाता है यदि यह लक्ष्य तक पहुंचने की लागत को कभी भी कम नहीं करता है, यानी लक्ष्य तक पहुंचने के लिए यह जिस लागत का अनुमान लगाता है, वह पथ में वर्तमान बिंदु से न्यूनतम संभव लागत से अधिक नहीं है।<ref>{{cite book
   | author = Russell, S.J.|author2= Norvig, P.
   | year = 2002
@@ Line 7: / Line 7: @@
   | isbn = 0-13-790395-2
   }}</ref>
-यह सुसंगत अनुमान की अवधारणा से संबंधित है। जबकि सभी सुसंगत अनुमान स्वीकार्य हैं, सभी स्वीकार्य अनुमान सुसंगत नहीं हैं।
-== खोज एल्गोरिदम ==
+यह सतत अनुमानी की अवधारणा से संबंधित है। हालाँकि सभी सुसंगत अनुमान ऐडमिसिबल हैं, लेकिन सभी ऐडमिसिबल अनुमान सुसंगत नहीं हैं।
-एक [[सूचित खोज एल्गोरिदम]] में लक्ष्य स्थिति तक पहुंचने की लागत का अनुमान लगाने के लिए एक स्वीकार्य अनुमान का उपयोग किया जाता है। एक अनुमान के लिए
-खोज समस्या के लिए स्वीकार्य होने के लिए, अनुमानित लागत हमेशा लक्ष्य स्थिति तक पहुंचने की वास्तविक लागत से कम या उसके बराबर होनी चाहिए।
+== सर्च (सर्च) एल्गोरिदम ==
-खोज एल्गोरिदम अनुमानित खोजने के लिए स्वीकार्य अनुमान का उपयोग करता है
+[[सूचित खोज एल्गोरिदम|ऐडमिसिबल सर्च एल्गोरिदम]] में लक्ष्य स्थिति तक पहुंचने की लागत का अनुमान लगाने के लिए ऐडमिसिबल अनुमान का उपयोग किया जाता है। सर्च समस्या के लिए ऐडमिसिबल अनुमान के लिए, अनुमानित लागत हमेशा लक्ष्य स्थिति तक पहुंचने की वास्तविक लागत से कम या बराबर होनी चाहिए। सर्च एल्गोरिदम वर्तमान नोड से लक्ष्य स्थिति के लिए अनुमानित इष्टतम पथ खोजने के लिए ऐडमिसिबल अनुमानी का उपयोग करता है। उदाहरण के लिए, A* सर्च में मूल्यांकन फ़ंक्शन (जहां <math>n</math> वर्तमान नोड है) है:
-वर्तमान नोड से लक्ष्य स्थिति के लिए इष्टतम पथ।
-उदाहरण के लिए, ए* में मूल्यांकन फ़ंक्शन खोजें (जहां
- <math>n</math> वर्तमान नोड है) है:
 <math>f(n) = g(n) + h(n)</math>
-कहाँ
-:<math>f(n)</math> = मूल्यांकन कार्य.
+जहाँ
+:<math>f(n)</math> = मूल्यांकन फंक्शन.
 :<math>g(n)</math> = प्रारंभ नोड से वर्तमान नोड तक की लागत
-:<math>h(n)</math> = वर्तमान नोड से लक्ष्य तक अनुमानित लागत।
+:<math>h(n)</math> = वर्तमान नोड से लक्ष्य तक अनुमानित लागत
-<math>h(n)</math> अनुमानी का उपयोग करके गणना की जाती है
+<math>h(n)</math> की गणना ह्यूरिस्टिक फ़ंक्शन का उपयोग करके की जाती है। गैर-ऐडमिसिबल अनुमान के साथ, A* एल्गोरिदम <math>f(n)</math> में अधिक अनुमान के कारण सर्च समस्या के इष्टतम समाधान को अनदेखा कर सकता है।
-समारोह। एक गैर-स्वीकार्य अनुमान के साथ, ए* एल्गोरिदम हो सकता है
-किसी खोज समस्या के इष्टतम समाधान को नज़रअंदाज कर दें
-में अधिक आकलन <math>f(n)</math>.
-==निरूपण==
+==फार्मूलेशन ==
 : <math>n</math> एक नोड है
 : <math>h</math> एक अनुमानी है
-: <math>h(n)</math> द्वारा दर्शाई गई लागत है <math>h</math> से एक लक्ष्य तक पहुँचने के लिए <math>n</math>
+:<math>h(n)</math> <math>n</math> से किसी लक्ष्य तक पहुंचने के लिए <math>h</math> द्वारा दर्शायी गई लागत है
-: <math>h^*(n)</math> किसी लक्ष्य तक पहुँचने के लिए इष्टतम लागत है <math>n</math>
+:<math>h^*(n)</math> <math>n</math> से किसी लक्ष्य तक पहुँचने के लिए इष्टतम लागत है
-: <math>h(n)</math> स्वीकार्य है यदि, <math>\forall n</math>
+: <math>h(n)</math> ऐडमिसिबल है यदि, <math>\forall n</math>
 :: <math>h(n) \leq h^*(n)</math>
 ==निर्माण==
-एक स्वीकार्य अनुमान एक [[विश्राम (अनुमान)]] से प्राप्त किया जा सकता है
+ऐडमिसिबल अनुमान समस्या के सुविधाजनक संस्करण से, या पैटर्न डेटाबेस से जानकारी द्वारा प्राप्त किया जा सकता है जो समस्या की उप-समस्याओं के सटीक समाधान संग्रहीत करता है, या आगमनात्मक शिक्षण विधियों का उपयोग करना है।
-समस्या का संस्करण, या पैटर्न डेटाबेस से जानकारी द्वारा जो समस्या की उप-समस्याओं के सटीक समाधान संग्रहीत करता है, या [[आगमनात्मक स्थानांतरण]] विधियों का उपयोग करके।
 ==उदाहरण==
-स्वीकार्य अनुमान के दो अलग-अलग उदाहरण [[पंद्रह पहेली]] समस्या पर लागू होते हैं:
+फिफ्टीन पज़ल समस्या पर ऐडमिसिबल अनुमान के दो अलग-अलग उदाहरण प्रयुक्त होते हैं:
 * [[हैमिंग दूरी]]
 *[[मैनहट्टन दूरी]]
-हैमिंग दूरी गलत रखी गई टाइलों की कुल संख्या है। यह स्पष्ट है कि यह अनुमान स्वीकार्य है क्योंकि टाइलों को सही ढंग से व्यवस्थित करने के लिए चालों की कुल संख्या कम से कम गलत रखी गई टाइलों की संख्या है (प्रत्येक टाइल जो जगह पर नहीं है उसे कम से कम एक बार स्थानांतरित किया जाना चाहिए)। लक्ष्य (एक आदेशित पहेली) की लागत (चालों की संख्या) पहेली की कम से कम हैमिंग दूरी है।
+हैमिंग दूरी गलत रखे गए टाइल्स की कुल संख्या है। यह स्पष्ट है कि यह अनुमान ऐडमिसिबल है क्योंकि टाइलों को सही ढंग से व्यवस्थित करने के लिए चालों की कुल संख्या कम से कम गलत जगह पर रखी गई टाइलों की संख्या है (प्रत्येक टाइल जो अपनी जगह पर नहीं है उसे कम से कम एक बार स्थानांतरित किया जाना चाहिए)। लक्ष्य ( क्रम में की गई पजल) की लागत (चालों की संख्या) कम से कम पजल की हैमिंग दूरी है।
-एक पहेली की मैनहट्टन दूरी को इस प्रकार परिभाषित किया गया है:
+पजल की मैनहट्टन दूरी इस प्रकार परिभाषित की गई है:
 :<math>h(n)=\sum_\text{all tiles} \mathit{distance}(\text{tile, correct position})</math>
-नीचे दी गई पहेली पर विचार करें जिसमें खिलाड़ी प्रत्येक टाइल को इस प्रकार स्थानांतरित करना चाहता है कि संख्याएँ क्रमबद्ध हों। मैनहट्टन की दूरी इस मामले में एक स्वीकार्य अनुमान है क्योंकि प्रत्येक टाइल को अपने और उसकी सही स्थिति के बीच कम से कम स्थानों की संख्या को स्थानांतरित करना होगा।<ref name="Korf,2000">{{cite conference |mode=cs2 |first=Richard E. |last=Korf |url=https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf |doi=10.1007/3-540-44914-0_3 |title=स्वीकार्य अनुमानी कार्यों के डिजाइन और विश्लेषण में हालिया प्रगति|editor-first=Berthe Y. |editor-last=Choueiry |editor2-first=Toby |editor2-last=Walsh |book-title=Abstraction, Reformulation, and Approximation: 4th International Symposium, SARA 2000 Horseshoe Bay, USA, July 26-29, 2000 Proceedings |pages=45–55 |publisher=Springer |year=2000 |isbn=978-3-540-67839-7 |access-date=2010-04-26 |volume=1864|citeseerx=10.1.1.124.817 }}</ref>
+नीचे दी गई पजल पर विचार करें जिसमें खिलाड़ी प्रत्येक टाइल को इस प्रकार हिलाना चाहता है कि संख्याएँ क्रमबद्ध हों। मैनहट्टन की दूरी इस स्थिति में ऐडमिसिबल अनुमान है क्योंकि प्रत्येक टाइल को अपने और उसकी सही स्थिति के बीच कम से कम स्थानों की संख्या को स्थानांतरित करना होगा।<ref name="Korf,2000">{{cite conference |mode=cs2 |first=Richard E. |last=Korf |url=https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf |doi=10.1007/3-540-44914-0_3 |title=स्वीकार्य अनुमानी कार्यों के डिजाइन और विश्लेषण में हालिया प्रगति|editor-first=Berthe Y. |editor-last=Choueiry |editor2-first=Toby |editor2-last=Walsh |book-title=Abstraction, Reformulation, and Approximation: 4th International Symposium, SARA 2000 Horseshoe Bay, USA, July 26-29, 2000 Proceedings |pages=45–55 |publisher=Springer |year=2000 |isbn=978-3-540-67839-7 |access-date=2010-04-26 |volume=1864|citeseerx=10.1.1.124.817 }}</ref>
 {| class="wikitable" style="text-align:right"
 |-
@@ Line 63: / Line 54: @@
 | 2<sub>4</sub>|| 10<sub>1</sub>|| 11<sub>1</sub>||
 |}
-सबस्क्रिप्ट प्रत्येक टाइल के लिए मैनहट्टन दूरी दिखाती है। दिखाई गई पहेली के लिए कुल मैनहट्टन दूरी है:
+सबस्क्रिप्ट प्रत्येक टाइल के लिए मैनहट्टन की दूरी दर्शाती है। प्रदर्शित पजल के लिए कुल मैनहट्टन दूरी है:
 :<math>h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36</math>
+==सर्वोत्तमता का प्रमाण==
+यदि किसी एल्गोरिदम में ऐडमिसिबल अनुमान का उपयोग किया जाता है, जो प्रति पुनरावृत्ति, केवल कई उम्मीदवार पथों के सबसे कम मूल्यांकन (वर्तमान लागत + अनुमानी) के पथ पर आगे बढ़ता है, तो उस क्षण समाप्त हो जाता है जब इसका अन्वेषण लक्ष्य तक पहुंचता है और, महत्वपूर्ण रूप से, समाप्त होने से पहले कभी भी सभी इष्टतम पथों को बंद नहीं किया जाता है (ऐसा कुछ जो A* सर्च एल्गोरिदम के साथ संभव है यदि विशेष देखभाल नहीं की जाती है <ref name="Misconceptions">{{cite journal|
-==इष्टतमता प्रमाण==
-यदि किसी एल्गोरिदम में एक स्वीकार्य अनुमान का उपयोग किया जाता है, जो प्रति पुनरावृत्ति, केवल कई उम्मीदवार पथों के न्यूनतम मूल्यांकन (वर्तमान लागत + अनुमानी) के पथ पर आगे बढ़ता है, तो उसी क्षण समाप्त हो जाता है जब उसका अन्वेषण लक्ष्य तक पहुंचता है और, महत्वपूर्ण रूप से, पहले कभी भी सभी इष्टतम पथ बंद नहीं करता है समाप्त करना (कुछ ऐसा जो A* खोज एल्गोरिदम के साथ संभव है यदि विशेष देखभाल नहीं की जाती है<ref name="Misconceptions">{{cite journal|
 last=Holte|
 first=Robert|
@@ Line 74: / Line 63: @@
 title=Common Misconceptions Concerning Heuristic Search|
 url=https://aaai.org/ocs/index.php/SOCS/SOCS10/paper/view/2073|
-journal=Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS)}}</ref>), तो यह एल्गोरिदम केवल एक इष्टतम पथ पर ही समाप्त हो सकता है। इसका कारण जानने के लिए, विरोधाभास द्वारा निम्नलिखित प्रमाण पर विचार करें:
+journal=Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS)}}</ref>), तो यह एल्गोरिदम केवल एक इष्टतम पथ पर समाप्त हो सकता है। यह देखने के लिए कि, विरोधाभास द्वारा निम्नलिखित प्रमाण पर विचार करें:
-मान लें कि ऐसा एल्गोरिदम वास्तविक लागत टी के साथ पथ टी पर समाप्त होने में कामयाब रहा<sub>true</sub>वास्तविक लागत S के साथ इष्टतम पथ S से अधिक<sub>true</sub>. इसका मतलब यह है कि समाप्त होने से पहले, T की मूल्यांकित लागत S की मूल्यांकित लागत से कम या उसके बराबर थी (अन्यथा S को चुना गया होता)। इन मूल्यांकित लागतों को निरूपित करें टी<sub>eval</sub>और एस<sub>eval</sub>क्रमश। उपरोक्त को इस प्रकार संक्षेप में प्रस्तुत किया जा सकता है,
+मान लें कि इस तरह का एल्गोरिदम वास्तविक लागत के साथ पथ T पर समाप्त होने में कामयाब रहा, जो '''T<sub>true</sub>''' के साथ इष्टतम पथ S से अधिक है। इसका मतलब यह है कि समाप्त होने से पहले, T की मूल्यांकन '''S<sub>true</sub>''' की मूल्यांकन लागत से कम या उसके बराबर थी (अन्यथा S को चुना गया होता)। इन मूल्यांकन की गई लागतों को क्रमशः '''T<sub>eval</sub>''' और '''S<sub>eval</sub>''' निरूपित करें। उपर्युक्त को संक्षेप में इस प्रकार प्रस्तुत किया जा सकता है,
-: एस<sub>true</sub><टी<sub>true</sub>: टी<sub>eval</sub>≤ एस<sub>eval</sub>यदि हमारा अनुमान स्वीकार्य है तो इसका तात्पर्य यह है कि इस अंतिम चरण में टी<sub>eval</sub>= टी<sub>true</sub>क्योंकि टी पर अनुमानी द्वारा वास्तविक लागत पर कोई भी वृद्धि अस्वीकार्य होगी और अनुमान नकारात्मक नहीं हो सकता। दूसरी ओर, एक स्वीकार्य अनुमान के लिए आवश्यक होगा कि एस<sub>eval</sub>≤ एस<sub>true</sub>जो उपरोक्त असमानताओं के साथ मिलकर हमें T प्राप्त करता है<sub>eval</sub><टी<sub>true</sub>और विशेष रूप से टी<sub>eval</sub>≠ टी<sub>true</sub>. जैसा कि टी<sub>eval</sub>और टी<sub>true</sub>समान और असमान दोनों नहीं हो सकते, हमारी धारणा गलत रही होगी और इसलिए इसे इष्टतम पथ से अधिक महंगे रास्ते पर समाप्त करना असंभव होगा।
-उदहारण के लिए,<ref>{{Cite web |url=https://stackoverflow.com/questions/23970588/why-do-admissable-heuristics-guarantee-optimality |title=Why do {{sic|admis|sable|nolink=y}} heuristics guarantee optimality? |website=Stack Overflow |access-date=2018-12-11 |department=algorithm}}</ref> आइए मान लें कि हमारी लागत इस प्रकार है: (नोड के ऊपर/नीचे की लागत अनुमानी है, किनारे पर लागत वास्तविक लागत है)
+: '''S<sub>true</sub>''' < '''T<sub>true</sub>'''
+: '''T<sub>eval</sub>''' ≤ '''S<sub>eval</sub>'''
+यदि हमारा अनुमान ऐडमिसिबल है तो यह इस प्रकार है कि इस अंतिम चरण में '''T<sub>eval</sub>''' = '''T<sub>true</sub>''' है क्योंकि T पर अनुमान द्वारा वास्तविक लागत में कोई भी वृद्धि अस्वीकार्य होगी और अनुमान ऋणात्मक नहीं हो सकता है। दूसरी ओर, ऐडमिसिबल अनुमान के लिए '''S<sub>eval</sub>''' ≤ '''S<sub>true</sub>''' की आवश्यकता होगी जो उपरोक्त असमानताओं के साथ मिलकर हमें टेवल '''T<sub>eval</sub>''' ≠ '''T<sub>true</sub>''' और अधिक विशेष रूप से '''T<sub>eval</sub>''' < '''T<sub>true</sub>''' देता है। चूँकि '''T<sub>eval</sub>''' और '''T<sub>true</sub>''' समान और असमान दोनों नहीं हो सकते हैं, हमारी धारणा गलत रही होगी और इसलिए इष्टतम पथ से अधिक महंगे मार्ग पर समाप्त करना असंभव होगा।
-10 0 100 0
+उदाहरण के तौर पर, <ref>{{Cite web |url=https://stackoverflow.com/questions/23970588/why-do-admissable-heuristics-guarantee-optimality |title=Why do {{sic|admis|sable|nolink=y}} heuristics guarantee optimality? |website=Stack Overflow |access-date=2018-12-11 |department=algorithm}}</ref> मान लें कि हमारी लागत इस प्रकार है: (नोड के ऊपर/नीचे की लागत अनुमानी है, किनारे पर लागत वास्तविक लागत है)
- प्रारंभ ---- हे ----- लक्ष्य
-  | |
-| |100
-  | |
-  ओ -------- ओ -------- ओ
-1 100 1 100
-तो स्पष्ट रूप से हम अपेक्षित कुल लागत के बाद से शीर्ष मध्य नोड पर जाना शुरू करेंगे, यानी। <math>f(n)</math>, है <math>10 + 0 = 10</math>. तब लक्ष्य एक उम्मीदवार होगा, साथ <math>f(n)</math> के बराबर <math>10+100+0=110</math>. फिर हम स्पष्ट रूप से एक के बाद एक नीचे के नोड्स को चुनेंगे, उसके बाद अद्यतन लक्ष्य को चुनेंगे, क्योंकि वे सभी ऐसा कर चुके हैं <math>f(n)</math> से कम <math>f(n)</math> वर्तमान लक्ष्य का, अर्थात् उनका <math>f(n)</math> है <math>100, 101, 102, 102</math>. इसलिए भले ही लक्ष्य एक उम्मीदवार था, हम उसे नहीं चुन सके क्योंकि वहां अभी भी बेहतर रास्ते थे। इस तरह, एक स्वीकार्य अनुमान इष्टतमता सुनिश्चित कर सकता है।
+     10   0   100   0
+ START ----  O  ----- GOAL
+  |                   |
+|                   |100
+  |                   |
+  O ------- O  ------ O
+   1    100   1   100
-हालाँकि, ध्यान दें कि यद्यपि एक स्वीकार्य अनुमान अंतिम इष्टतमता की गारंटी दे सकता है, लेकिन यह आवश्यक रूप से कुशल नहीं है।
+तो स्पष्ट रूप से हम शीर्ष मध्य नोड पर जाना शुरू करेंगे, क्योंकि अपेक्षित कुल लागत, अर्थात <math>f(n)</math>, <math>10 + 0 = 10</math> है तब लक्ष्य एक उम्मीदवार होगा, जिसमें <math>f(n)</math><math>10+100+0=110</math> के बराबर होगा। फिर हम स्पष्ट रूप से एक के बाद एक नीचे के नोड्स को चुनेंगे, उसके बाद अद्यतन लक्ष्य, क्योंकि उन सभी का <math>f(n)</math> वर्तमान लक्ष्य के <math>f(n)</math> से कम है, अर्थात उनका <math>f(n)</math> <math>100, 101, 102, 102</math> है। इसलिए भले ही लक्ष्य एक उम्मीदवार था, हम उसे नहीं चुन सके क्योंकि वहां अभी भी बेहतर रास्ते उपस्थित थे। इस तरह, ऐडमिसिबल अनुमान अनुकूलता सुनिश्चित कर सकता है।
+हालाँकि, ध्यान दें कि यद्यपि ऐडमिसिबल अनुमान अंतिम इष्टतमता की गारंटी दे सकता है, लेकिन यह आवश्यक रूप से कुशल नहीं है।
 ==संदर्भ==
 {{reflist}}
 ==यह भी देखें==
 *सुसंगत अनुमानी
-* अनुमानी कार्य
+* अनुमानी फंक्शन
-* [[खोज एल्गोरिथ्म]]
+* [[खोज एल्गोरिथ्म|सर्च एल्गोरिथ्म]]
-श्रेणी:ह्यूरिस्टिक्स
-श्रेणी:कृत्रिम बुद्धि
 [[Category: Machine Translated Page]]
 [[Category:Created On 27/07/2023]]
+[[Category:Vigyan Ready]]

Anonymous

Search

ऐडमिसिबल हेयुरिस्टिक: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 22:17, 10 October 2023

Contents

सर्च (सर्च) एल्गोरिदम

फार्मूलेशन

निर्माण

उदाहरण

सर्वोत्तमता का प्रमाण

संदर्भ

यह भी देखें

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ऐडमिसिबल हेयुरिस्टिक: Difference between revisions

Latest revision as of 22:17, 10 October 2023

सर्च (सर्च) एल्गोरिदम

फार्मूलेशन

निर्माण

उदाहरण

सर्वोत्तमता का प्रमाण

संदर्भ

यह भी देखें

Navigation

Wiki tools

Page tools

Other projects

Hidden categories