A* सर्च
दिशा की समझ वाला डाइक्स्ट्रा। हर जगह की लागत में बची हुई लागत का अनुमान जोड़ता है, इसलिए पहले वे जगहें आज़माता है जो लक्ष्य के सबसे पास लगती हैं।
- समय O((V + E) log V)
- मेमोरी O(V)
- प्राथमिकता कतार
प्राथमिकता कतार: ऐसी कतार जिसमें पहले आने वाला नहीं, सबसे सस्ता पहले जाता है।
इस पेज के अन्य शब्द
- लागत: एक चाल की कीमत। भूलभुलैया में ज़मीन 1, कीचड़ 3 और पानी 9; ग्राफ़ में किनारे पर लिखी संख्या।
- अनुमान (h): बची हुई लागत का अंदाज़ा। A* तभी सटीक रहता है जब यह कभी ज़्यादा न हो।
- किनारे को ढीला करना: जाँचना कि मौजूदा जगह से होकर जाने पर पड़ोसी की लागत कम होती है या नहीं, और हो तो उसे अपनाना।
इसे आज़माएं: खुला मैदान चुनें और डाइक्स्ट्रा व A* के बीच बदलें: दोनों एक ही लागत का रास्ता ढूँढते हैं, पर A* कतार से कहीं कम खाने निकालता है।
यह कैसे काम करता है
A* डाइक्स्ट्रा की तरह काम करता है, पर कतार को f = अब तक की लागत + h से क्रम में रखता है, जहाँ h बची हुई लागत का अनुमान है। भूलभुलैया में h दीवारों और कीचड़ को छोड़कर M तक की चालों की संख्या है; ग्राफ़ में सीधी दूरी को 10 से भाग देकर। जब तक h कभी ज़्यादा अनुमान नहीं लगाता, लक्ष्य लेते समय A* के पास जो रास्ता है वही सबसे सस्ता है, ठीक डाइक्स्ट्रा की तरह। अनुमान जितना अच्छा, उतनी कम जगहें देखनी पड़ती हैं।
यह कब सही विकल्प है
A* तब काम आता है जब आप एक लक्ष्य ढूँढ रहे हों और उसकी दूरी का अनुमान लगा सकें: गेम में रास्ता ढूँढना, रोबोट, नक्शे पर रूट प्लानर। h = 0 पर यह ठीक डाइक्स्ट्रा है। जो अनुमान ज़्यादा लगा सकता है, वह A* को तेज़ करता है पर सबसे सस्ता रास्ता छूट सकता है।