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

ग्राफ़ प्रतिनिधित्व

दोनों एल्गोरिदम ग्राफ पर काम करते हैं, जिसमें नोड्स (vertices) और किनारों शामिल होते हैं। किनारों में लागत, दूरी, या समय का प्रतिनिधित्व करने वाले वजन हो सकते हैं। ग्राफ को निर्देशित या निर्देशित किया जा सकता है, और वजन आमतौर पर गैर-नकारात्मक होते हैं।

लागत कार्य और हेरिस्टिक्स

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

गणितीय स्वरूप

Let G = (V, E) vertices V और किनारों E के साथ एक graph हो सकता है। प्रत्येक किनारे (u, v) एक वजन w (u, v) है। लक्ष्य शुरू नोड से लक्ष्य नोड टी के लिए सबसे कम पथ खोजने के लिए है।

Dijkstra के एल्गोरिथ्म प्रत्येक vertex v के लिए दूरी डी (v) अद्यतन करता है, जो d(s) = 0 और d(v) = ∞ for v }} s. It is iteratively is the vertex with small d(v), फिर अपने पड़ोसी किनारों को आराम देता है।

A* इसे एक heuristic h(v) को शामिल करके संशोधित करता है जो v से t तक की लागत को अनुमान लगाता है। प्राथमिकता का कार्य f(v) = d(v) + h(v) हो जाता है। एल्गोरिदम न्यूनतम f(v) के आधार पर नोड्स का विस्तार करता है।

अल्गोरिथम दक्षता

दक्षता का उपयोग डेटा संरचनाओं पर निर्भर करता है। Dijkstra के एल्गोरिदम में प्राथमिकता वाले कतार के साथ O (E) + |V + log |V ) की समय जटिलता है। A * तेजी से हो सकता है अगर हेरिस्टिस्टिक अच्छी तरह से डिज़ाइन किया गया है, तो नोड्स की संख्या को बढ़ाया गया।

  • गैर-नकारात्मक वजन के साथ ग्राफ
  • A* के लिए स्वीकार्य हेरिस्टिक
  • नोड चयन के लिए प्राथमिकता queue
  • लागत को अद्यतन करने के लिए किनारों की छूट