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

A * Algorithm को समझना

A* एल्गोरिदम एक लागत समारोह, f(n) = g(n) + h(n) का उपयोग करता है, जहां:

  • g(n): शुरू नोड से लेकर नोड तक वास्तविक लागत।
  • h(n): नोड n से लक्ष्य तक लागत का हरिवेटिव अनुमान।

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

चरण-दर-चरण कार्यान्वयन

A * एल्गोरिदम को लागू करने के लिए इन चरणों का पालन करें:

1. ओपन और बंद सूचियों को शुरू करना

खुली सूची में नोड्स का मूल्यांकन किया जाना है, प्रारंभिक नोड से शुरू हुआ। बंद सूची में पहले से ही मूल्यांकन किए गए नोड्स शामिल हैं।

2. सबसे कम एफ (n) के साथ नोड का चयन करें

इस नोड को खुली सूची से निकालें और इसे बंद सूची में जोड़ें।

3. पड़ोसी नोड्स उत्पन्न करना

प्रत्येक पड़ोसी के लिए जी (n) और h(n) की गणना करें। यदि कोई पड़ोसी खुली सूची में नहीं है या उसके पास कम g(n) है तो अपने मूल्यों को अद्यतन करें और अपने माता-पिता को वर्तमान नोड में सेट करें।

4. जब तक लक्ष्य तक पहुंच जाता है तब तक दोहराएं

जब तक लक्ष्य नोड बंद सूची में जोड़ा जाता है तब तक प्रक्रिया जारी रखें, यह दर्शाता है कि सबसे छोटा पथ पाया गया है।

उदाहरण गणना

प्रारंभ नोड ए और लक्ष्य नोड जी के साथ एक सरल ग्रिड पर विचार करें। हेरिस्टिक h(n) सीधी रेखा दूरी है। प्रारंभिक गणना इस प्रकार है:

नोड ए, जी (ए) = 0, एच (ए) = 4 पर शुरू होता है। एफ (ए) = 4। पड़ोसी नोड्स बी और सी का मूल्यांकन किया जाता है:

नोड बी: जी (बी) = जी (ए) + लागत (ए, बी) = 0 + 1 = 1, एच (बी) = 3, एफ (बी) = 4

नोड C: g(C) = 1, h(C) = 2, f(C) = 3। Node C में सबसे कम f(n) है, इसलिए इसे अगले चुना जाता है।

यह प्रक्रिया जारी रहती है, जी, एच और एफ मूल्यों को अद्यतन करती है, जब तक कि लक्ष्य नोड जी की पहचान की गई सबसे कम पथ के साथ पहुंच नहीं मिलती है।