algorithm => एक * पाथफाइंडिंग

A * का परिचय

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

ए * एक की सर्वश्रेष्ठ पहली खोजें एक विशेषज्ञता, जिसमें मूल्यांकन च का कार्य एक खास तरह से परिभाषित है।

च (n) = g (n) + h (n) प्रारंभिक नोड के बाद से न्यूनतम लागत है जिसे सोचा नोड n पर जाने के लिए वातानुकूलित किया गया है।

g (n) प्रारंभिक नोड से n तक की न्यूनतम लागत है।

h (n) n से निकटतम उद्देश्य के लिए n से न्यूनतम लागत है

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

ए * एल्गोरिथ्म का उपयोग करके 8-पहेली समस्या का समाधान

समस्या की परिभाषा :

एक 8 पहेली एक सरल गेम है जिसमें 3 x 3 ग्रिड (9 वर्ग शामिल हैं)। चौकों में से एक खाली है। ऑब्जेक्ट को अलग-अलग स्थितियों में चौकों पर ले जाना है और "लक्ष्य स्थिति" में प्रदर्शित संख्याएं हैं।

8-पज़ल गेम की प्रारंभिक स्थिति और अंतिम स्थिति तक पहुंचने के लिए, प्रारंभिक अवस्था के साथ अंतिम स्थिति तक पहुंचने के लिए सबसे अधिक लागत प्रभावी रास्ता खोजें।

प्रारंभिक स्थिति :

_ 1 3
4 2 5
7 8 6

अंतिम स्थिति :

1 2 3
4 5 6
7 8 _

अनुमान लगाया जाना है :

आइए वर्तमान और अंतिम अवस्था के बीच मैनहट्टन की दूरी को इस समस्या के बयान के लिए अनुमानी मानते हैं।

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

कुल लागत समारोह :

तो कुल लागत फ़ंक्शन f(n) द्वारा दिया जाता है,

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

उदाहरण के लिए समस्या का हल :

पहले हम प्रारंभिक अवस्था से अंतिम स्थिति तक पहुंचने के लिए आवश्यक मूल्य को पाते हैं। लागत फ़ंक्शन, जी (एन) = 0, जैसा कि हम प्रारंभिक अवस्था में हैं

h(n) = 8

इसके बाद के संस्करण मूल्य के रूप में, प्राप्त किया जाता है 1 वर्तमान स्थिति में 1 से क्षैतिज दूरी पर है 1 अंतिम अवस्था में। वही 2 , 5 , 6 लिए जाता है। _ 2 क्षैतिज दूरी है और 2 ऊर्ध्वाधर दूरी है। तो h(n) लिए कुल मूल्य 1 + 1 + 1 + 1 + 2 + 2 = 8. कुल लागत फ़ंक्शन f(n) 8 + 0 = 8 के बराबर है।

अब, संभव कहा गया है कि प्रारंभिक अवस्था से पहुँचा जा सकता है पाए जाते हैं और ऐसा होता है कि हम या तो स्थानांतरित कर सकते हैं _ सही है या नीचे की ओर करने के लिए।

तो उन चालों को स्थानांतरित करने के बाद प्राप्त राज्य हैं:

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

फिर से कुल लागत फ़ंक्शन की गणना ऊपर वर्णित विधि का उपयोग करके इन राज्यों के लिए की जाती है और यह क्रमशः 6 और 7 हो जाता है। हमने न्यूनतम लागत वाला राज्य चुना है जो राज्य (1) है। अगले संभावित कदम वाम, अधिकार या नीचे हो सकते हैं। हम लेफ्ट को आगे नहीं बढ़ाएंगे क्योंकि हम पहले उस राज्य में थे। इसलिए, हम राइट या डाउन ले जा सकते हैं।

फिर से हम (1) से प्राप्त राज्यों को पाते हैं।

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

(3) लागत समारोह 6 के बराबर होता है और (4) 4 की ओर जाता है। इसके अलावा, हम विचार करेंगे (2) से पहले प्राप्त किया गया है, जिसमें लागत फ़ंक्शन समान है 7. उनमें से न्यूनतम चुनना (4) की ओर जाता है। अगली संभावित चालें वाम या अधिकार या नीचे हो सकती हैं। हम राज्यों:

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

हमें क्रमशः (5), (6) और (7) के लिए 5, 2 और 4 के बराबर लागत मिलती है। इसके अलावा, हमारे पास क्रमशः 6 और 7 के साथ पिछले राज्य (3) और (2) हैं। हमने न्यूनतम लागत वाला राज्य चुना है जो (6) है। अगले संभावित कदम ऊपर हैं, और नीचे और स्पष्ट रूप से नीचे हमें अंतिम राज्य में ले जाएगा जो कि 0 के बराबर हैरिटिस्टिक फ़ंक्शन मान के लिए अग्रणी है।

A * बिना किसी बाधा के भूलभुलैया से होकर गुजरना

मान लें कि हमारे पास 4 निम्नलिखित 4 ग्रिड हैं:

मान लेते हैं कि यह एक भूलभुलैया है । हालांकि कोई दीवारें / बाधाएं नहीं हैं। हमारे पास केवल एक प्रारंभिक बिंदु (हरा वर्ग), और एक समाप्ति बिंदु (लाल वर्ग) है। यह भी मान लें कि हरे से लाल होने के लिए, हम तिरछे नहीं चल सकते। तो, हरे वर्ग से शुरू करते हुए, आइए देखें कि हम किन वर्गों को स्थानांतरित कर सकते हैं और उन्हें नीले रंग में उजागर कर सकते हैं:

चुनने के लिए कि किस वर्ग को आगे बढ़ना है, हमें 2 उत्तराधिकारियों को ध्यान में रखना होगा:

"जी" मान - यह नोड ग्रीन स्क्वायर से कितनी दूर है।
"H" मान - यह नोड लाल वर्ग से कितनी दूर है।
"एफ" मूल्य - यह "जी" मूल्य और "एच" मूल्य का योग है। यह अंतिम संख्या है जो हमें बताती है कि किस नोड को स्थानांतरित करना है।

इन अनुमानों की गणना करने के लिए, यह वह सूत्र है जिसका हम उपयोग करेंगे: distance = abs(from.x - to.x) + abs(from.y - to.y)

यह "मैनहट्टन दूरी" सूत्र के रूप में जाना जाता है।

चलो हरे वर्ग के बाईं ओर नीले वर्ग के लिए "जी" मान की गणना करें: abs(3 - 2) + abs(2 - 2) = 1

महान! हमें मान मिला है: 1. अब, "h" मान की गणना करने का प्रयास करें: abs(2 - 0) + abs(2 - 0) = 4

उत्तम। अब, "f" मान प्राप्त करें: 1 + 4 = 5

तो, इस नोड का अंतिम मूल्य "5" है।

अन्य सभी नीले वर्गों के लिए भी ऐसा ही करते हैं। प्रत्येक वर्ग के केंद्र में बड़ी संख्या "f" मान है, जबकि शीर्ष बाईं ओर की संख्या "g" मान है, और शीर्ष दाईं ओर की संख्या "h" मान है:

हमने सभी नीले नोड्स के लिए g, h और f मानों की गणना की है। अब हम किसे चुनें?

जिसका भी सबसे कम f मान होता है।

हालांकि, इस मामले में, हमारे पास समान मान के साथ 2 नोड हैं, 5. हम उनके बीच कैसे उठाते हैं?

बस, या तो यादृच्छिक पर एक चुनें, या एक प्राथमिकता निर्धारित करें। मैं आमतौर पर प्राथमिकता पसंद करता हूं जैसे: "राइट> अप> डाउन> लेफ्ट"

5 के f मान वाले नोड्स में से एक हमें "डाउन" दिशा में ले जाता है, और दूसरा हमें "लेफ्ट" में ले जाता है। चूंकि लेफ्ट की तुलना में डाउन उच्च प्राथमिकता पर है, इसलिए हम उस वर्ग को चुनते हैं जो हमें "डाउन" लेता है।

अब मैं उन नोड्स को चिह्नित करता हूं, जिनके लिए हमने अनुमानों की गणना की है, लेकिन नारंगी के रूप में, और उस नोड को स्थानांतरित नहीं किया, जिसे हमने नयन के रूप में चुना था: