A* सर्च

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

एक ग्राफ़ जिसमें पूरे हो चुके नोड शुरुआत से लक्ष्य की ओर एक पतली पट्टी बनाते हैं, लक्ष्य की ओर इशारा करती एक डैश वाली सीधी रेखा है, और नीचे एक क्यू बनी है
एक ग्राफ़ जिसमें पूरे हो चुके नोड शुरुआत से लक्ष्य की ओर एक पतली पट्टी बनाते हैं, लक्ष्य की ओर इशारा करती एक डैश वाली सीधी रेखा है, और नीचे एक क्यू बनी है

मूल विचार

जब आप नक्शे पर रास्ता खोजते हैं, तो अपनी मंज़िल से दूर ले जाने वाली सड़कों को उतने ध्यान से नहीं देखते जितना उसकी ओर ले जाने वाली सड़कों को। A* सर्च भी यही करता है। हर नोड को एक स्कोर मिलता है: शुरुआत से अब तक की दूरी, g, और बची हुई दूरी के अनुमान, h, का जोड़। सर्च हमेशा सबसे कम स्कोर वाले नोड से आगे बढ़ता है, इसलिए लक्ष्य की ओर पड़ने वाले नोड पहले आते हैं।

चरण दर चरण

शुरुआत को दूरी 0 दें और उसे स्कोर h(start) के साथ क्यू में रखें। दोहराएँ: सबसे कम स्कोर वाला नोड लें, और उसकी दूरी तय मानें। अगर वह लक्ष्य है, तो रुकें: याद रखे गए नोड के सहारे पीछे चलने पर रास्ता मिलता है। नहीं तो, हर उस पड़ोसी के लिए जो तय नहीं है, इस नोड से होकर उसकी दूरी निकालें। अगर यह उसकी अब तक की दूरी से छोटी है, तो उसे घटाएँ, इस नोड को वहाँ पहुँचने का रास्ता मानकर याद रखें, और पड़ोसी को उसकी नई दूरी और उसके अनुमान के जोड़ जितना स्कोर दें। जब दो स्कोर बराबर हों, तो छोटे अनुमान वाला नोड पहले लेने से आमतौर पर लक्ष्य जल्दी मिलता है।

एक उदाहरण

मान लें शुरुआत A है और लक्ष्य D। A–B की लंबाई 2 है और B–D की 2, जबकि A–C की 1 और C–D की 5। D तक की सीधी रेखा के अनुमान A से 3, B से 2 और C से 3 हैं। A का शुरुआती स्कोर 0 + 3 = 3 है। A लेने पर B को स्कोर 2 + 2 = 4 और C को स्कोर 1 + 3 = 4 मिलता है। बराबरी होने पर A* छोटे अनुमान वाला नोड B लेता है, और B से D को स्कोर 4 + 0 = 4 मिलता है। अब D का स्कोर सबसे कम है और अनुमान सबसे छोटा, इसलिए उसे लिया जाता है: सबसे छोटा रास्ता A → B → D है, लंबाई 4, और गलत दिशा में ले जाने वाला C कभी तय नहीं होता। डाइक्स्ट्रा एल्गोरिदम C को पहले तय करता, क्योंकि वह A के सबसे पास का नोड है।

अच्छा अनुमान

अनुमान लक्ष्य तक की असली दूरी से कभी लंबा नहीं होना चाहिए; ऐसा अनुमान एडमिसिबल कहलाता है, और इसके साथ A* हमेशा सबसे छोटा रास्ता खोजता है। सीधी रेखा एडमिसिबल है, क्योंकि कोई भी रास्ता सीधी रेखा से छोटा नहीं होता। अगर एक नोड से अगले नोड पर जाते हुए अनुमान कभी एज की लंबाई से ज़्यादा नहीं घटता, तो वह कंसिस्टेंट है, और किसी तय नोड को दोबारा देखने की ज़रूरत नहीं पड़ती। अनुमान सच के जितना पास हो, A* को उतने कम नोड चाहिए। 0 का अनुमान एडमिसिबल है पर बेकार: तब A* डाइक्स्ट्रा एल्गोरिदम बन जाता है। बहुत बड़ा अनुमान A* को तेज़ बनाता है, पर सबसे छोटा रास्ता चूक सकता है।

इतिहास और उपयोग

स्टैनफ़र्ड रिसर्च इंस्टीट्यूट के पीटर हार्ट, निल्स निल्सन और बर्ट्रम राफ़ेल ने 1968 में A* प्रकाशित किया, जब वे शेकी पर काम कर रहे थे, जो पहले चलने-फिरने वाले रोबोटों में से एक था। उनके पहले के संस्करण A1 और A2 कहलाते थे; स्टार उस संस्करण का निशान था जिसे उन्होंने ऑप्टिमल साबित किया। आज A* वीडियो गेम में किरदारों को रुकावटों के चारों ओर ले जाता है, रास्तों और रोबोट की गतिविधियों की योजना बनाता है, और 15-पज़ल जैसी पहेलियाँ हल करता है, जहाँ अनुमान जोड़ता है कि हर टाइल अपनी जगह से कितनी दूर है।

शेकी, स्टैनफ़ोर्ड रिसर्च इंस्टिट्यूट का गतिशील रोबोट, कंप्यूटर इतिहास संग्रहालय में लिया गया चित्र। पीटर हार्ट, निल्स निल्सन और बर्ट्राम राफ़ाएल ने इस पर काम करते हुए 1968 में A* प्रकाशित किया।
शेकी, स्टैनफ़ोर्ड रिसर्च इंस्टिट्यूट का गतिशील रोबोट, कंप्यूटर इतिहास संग्रहालय में लिया गया चित्र। पीटर हार्ट, निल्स निल्सन और बर्ट्राम राफ़ाएल ने इस पर काम करते हुए 1968 में A* प्रकाशित किया।

ख़ुद आज़माएँ

ऐप खोलें और “आगे” दबाएँ। एज पर लिखी संख्याएँ उनकी लंबाई हैं, जो यहाँ उनकी बनी हुई लंबाई से मेल खाती हैं, और डैश वाली रेखा लक्ष्य तक की सीधी रेखा का अनुमान दिखाती है। ग्राफ़ के नीचे की क्यू नोड को स्कोर के क्रम में दिखाती है, सबसे कम पहले। लक्ष्य तय होने पर, स्टेटस लाइन तुलना करती है कि A* ने कितने नोड तय किए और डाइक्स्ट्रा एल्गोरिदम को कितने चाहिए होते। सबसे बड़ा फ़र्क देखने के लिए किसी बड़े ग्राफ़ के दूर के कोने में लक्ष्य रखकर देखें।

अक्सर पूछे जाने वाले प्रश्न

A* में स्टार का क्या मतलब है?

हार्ट, निल्सन और राफ़ेल ने पहले A1 और A2 नाम के एल्गोरिदम बताए थे। A* (“A स्टार”) वह संस्करण था जिसके बारे में उन्होंने साबित किया कि अनुमान कंसिस्टेंट होने पर, वही अनुमान इस्तेमाल करने वाले तुलनीय एल्गोरिदम में यह सबसे कम नोड एक्सपैंड करके सबसे छोटा रास्ता खोजता है।

A* की टाइम कॉम्प्लेक्सिटी क्या है?

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

A* के लिए अच्छा ह्यूरिस्टिक कैसा होता है?

वह जल्दी निकल जाए, असली दूरी को कभी ज़्यादा न आँके, और उसके जितना हो सके उतना पास हो। ऐसे ग्रिड पर जहाँ सिर्फ़ ऊपर, नीचे, बाएँ और दाएँ चल सकते हैं, मैनहट्टन दूरी आम विकल्प है; नक्शे पर, सीधी रेखा की दूरी।

अगर ह्यूरिस्टिक ज़्यादा आँके तो क्या होता है?

तब A* ऐसा रास्ता लौटा सकता है जो सबसे छोटा न हो, क्योंकि वह बेहतर रास्ता देखने से पहले ही रुक सकता है। कुछ प्रोग्राम जानबूझकर ऐसा करते हैं (वेटेड A*), ताकि रास्ते की थोड़ी गुणवत्ता छोड़कर काफ़ी रफ़्तार पाई जा सके।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

A* सर्च आज़माएँ