तय
क्यू में
जाँचे गए एज

  • मौजूदा
  • क्यू में
  • तय
  • रास्ता
  • सीधी रेखा का अनुमान
नोड पर क्लिक से सेट करें

A* सर्च के बारे में और

A* सर्च

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

यह कैसे काम करता है

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

A* सर्च कैसे काम करता है

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

अनुमान कभी बहुत लंबा क्यों न हो

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

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

A* सर्च क्या है?

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

एडमिसिबल ह्यूरिस्टिक क्या है?

लक्ष्य तक की दूरी का ऐसा अनुमान जो असली सबसे छोटी दूरी से कभी लंबा नहीं होता। एडमिसिबल अनुमान के साथ A* हमेशा सबसे छोटा रास्ता खोजता है। नक्शे पर सीधी रेखा की दूरी इसका सबसे जाना-माना उदाहरण है।

क्या A* डाइक्स्ट्रा एल्गोरिदम से तेज़ है?

आमतौर पर हाँ, जब आपको एक ही लक्ष्य तक का रास्ता चाहिए और अच्छा अनुमान हो: A* कम नोड तय करता है, क्योंकि लक्ष्य से दूर पड़ने वाले नोड को ऊँचा स्कोर मिलता है। अनुमान 0 होने पर यह ठीक वही करता है जो डाइक्स्ट्रा एल्गोरिदम करता है। जब आपको हर नोड तक की दूरी चाहिए, तब डाइक्स्ट्रा एल्गोरिदम बेहतर विकल्प है।

A* कहाँ इस्तेमाल होता है?

वीडियो गेम में किरदारों को रुकावटों के चारों ओर ले जाने में, रूट प्लानर में, रोबोट की गति की योजना में, और 15-पज़ल जैसी पहेलियाँ हल करने वाले प्रोग्राम में, जहाँ अनुमान गिनता है कि टाइलें अपनी जगह से कितनी दूर हैं।

क्या मेरा ग्राफ़ कहीं भेजा जाता है?

नहीं। ग्राफ़ आपके ब्राउज़र में ही बनता और खोजा जाता है, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

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

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

एडिटर पर जाएँ