ऐडमिसिबल हेयुरिस्टिक

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

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

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

ऐडमिसिबल सर्च एल्गोरिदम में लक्ष्य स्थिति तक पहुंचने की लागत का अनुमान लगाने के लिए ऐडमिसिबल अनुमान का उपयोग किया जाता है। सर्च समस्या के लिए ऐडमिसिबल अनुमान के लिए, अनुमानित लागत हमेशा लक्ष्य स्थिति तक पहुंचने की वास्तविक लागत से कम या बराबर होनी चाहिए। सर्च एल्गोरिदम वर्तमान नोड से लक्ष्य स्थिति के लिए अनुमानित इष्टतम पथ खोजने के लिए ऐडमिसिबल अनुमानी का उपयोग करता है। उदाहरण के लिए, 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}})$

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

43	61	30	81
72	123	93	144
153	132	14	54
24	101	111

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

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

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

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

मान लें कि इस तरह का एल्गोरिदम वास्तविक लागत के साथ पथ 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 समान और असमान दोनों नहीं हो सकते हैं, हमारी धारणा गलत रही होगी और इसलिए इष्टतम पथ से अधिक महंगे मार्ग पर समाप्त करना असंभव होगा।

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

  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$ है। इसलिए भले ही लक्ष्य एक उम्मीदवार था, हम उसे नहीं चुन सके क्योंकि वहां अभी भी बेहतर रास्ते उपस्थित थे। इस तरह, ऐडमिसिबल अनुमान अनुकूलता सुनिश्चित कर सकता है।

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

यह भी देखें

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