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

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

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

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

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

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

जहाँ

$f(n)$ = मूल्यांकन फंक्शन.

$g(n)$ = प्रारंभ नोड से वर्तमान नोड तक की लागत

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

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

निरूपण

$n$ एक नोड है

$h$ एक अनुमानी है

$h(n)$ द्वारा दर्शाई गई लागत है $h$ से एक लक्ष्य तक पहुँचने के लिए $n$

$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* खोज एल्गोरिदम के साथ संभव है यदि विशेष देखभाल नहीं की जाती है), तो यह एल्गोरिदम केवल एक इष्टतम पथ पर ही समाप्त हो सकता है। इसका कारण जानने के लिए, विरोधाभास द्वारा निम्नलिखित प्रमाण पर विचार करें:

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

एस_true<टी_true: टी_eval≤ एस_evalयदि हमारा अनुमान स्वीकार्य है तो इसका तात्पर्य यह है कि इस अंतिम चरण में टी_eval= टी_trueक्योंकि टी पर अनुमानी द्वारा वास्तविक लागत पर कोई भी वृद्धि अस्वीकार्य होगी और अनुमान नकारात्मक नहीं हो सकता। दूसरी ओर, एक स्वीकार्य अनुमान के लिए आवश्यक होगा कि एस_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$. इसलिए भले ही लक्ष्य एक उम्मीदवार था, हम उसे नहीं चुन सके क्योंकि वहां अभी भी बेहतर रास्ते थे। इस तरह, एक स्वीकार्य अनुमान इष्टतमता सुनिश्चित कर सकता है।

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

यह भी देखें

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

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