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

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

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

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

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

एस_true<टी_true: टी_eval≤ एस_evalयदि हमारा अनुमान स्वीकार्य है तो इसका तात्पर्य यह है कि इस अंतिम चरण में टी_eval= टी_trueक्योंकि T पर अनुमानी द्वारा वास्तविक लागत पर कोई भी वृद्धि अस्वीकार्य होगी और अनुमान नकारात्मक नहीं हो सकता। दूसरी ओर, एक स्वीकार्य अनुमान के लिए आवश्यक होगा कि एस_eval≤ एस_trueजो उपरोक्त असमानताओं के साथ मिलकर हमें T प्राप्त करता है_eval<टी_trueऔर विशेष रूप से टी_eval≠ टी_true. जैसा कि टी_evalऔर टी_trueसमान और असमान दोनों नहीं हो सकते, हमारी धारणा गलत रही होगी और इसलिए इसे इष्टतम पथ से अधिक महंगे रास्ते पर समाप्त करना असंभव होगा।

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

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

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

यह भी देखें

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

श्रेणी:ह्यूरिस्टिक्स श्रेणी:कृत्रिम बुद्धि