यह आमतौर पर कहा जाता है कि ए * पथदर्शी समस्याओं को हल करने के लिए सबसे अच्छा एल्गोरिदम है।ए * सबसे अच्छा पथदर्शी एल्गोरिदम है?
वहाँ किसी भी स्थिति है जब एक * नहीं सबसे अच्छा एल्गोरिथ्म समाधान खोजने के लिए है?
बीएफएस, डीएफएस, यूसीएस आदि की तुलना में ए * कितना अच्छा है?
ए * विशेष है क्योंकि यह नोड्स और इसका उपयोग करने वाले हेरिस्टिक का मूल्यांकन करने के साथ अन्य पथ-खोज एल्गोरिदम में घुमाया जा सकता है। आप Djikstra, सर्वोत्तम-पहली खोज, सांस-प्रथम-खोज, और गहराई-प्रथम-खोज अनुकरण करने के लिए ऐसा कर सकते हैं।
इसके अलावा, इसे तेज करना अक्सर आसान होता है। उदाहरण के लिए यदि आप स्थिर, सी द्वारा एक स्वीकार्य हेरिस्टिक को गुणा करते हैं, तो आप गारंटी दे सकते हैं कि नोड्स के परिणामी अनुक्रम की लागत इष्टतम परिणाम से सी गुना से अधिक नहीं है।
उदाहरण के लिए, इयान डेविस (स्टार ट्रेक आर्मडा के लिए लिखे गए) द्वारा यह awesome paper लें। ए * को मार्ग बिंदुओं के पदानुक्रमित सेट के साथ प्रयोग किया जाता है, जिसके परिणामस्वरूप एक मोटा पथ होता है। फिर, पथ को सुचारु बनाने के लिए, वे ए * को एक नए, जेनरेट किए गए ग्राफ पर पथ पर नोड्स और आस-पास के लोगों को अधिक उचित पथ प्राप्त करने के लिए चलाते हैं। अंत में, वे अनावश्यक नोड्स को हटाने के लिए रबड़-बैंडिंग चलाते हैं।
तो, ए * सब कुछ का समाधान नहीं है, लेकिन यह एक बहुत बहुमुखी उपकरण है।
संक्षिप्त उत्तर हाँ है, ऐसी स्थितियां हैं जिनमें ए * समस्या को हल करने के लिए सबसे अच्छा एल्गोरिदम नहीं है। हालांकि, समाधान खोजने के लिए सर्वोत्तम एल्गोरिदम का आकलन करने के कई तरीके हैं।
आप कई स्थलों करने के लिए सबसे अच्छा एक अकेले स्रोत से कई खोजों के प्रदर्शन के मामले में विचार कर रहे हैं, तो आप एक अधिक उपयुक्त दृष्टिकोण (Dijkstra's algorithm) का उपयोग पर विचार करना चाहिए।
आप सबसे अच्छाप्रदर्शन के संदर्भ में विचार कर रहे हैं, तो कुछ विशेष मामलों डीएफएस में और BFS काफी ए * बेहतर प्रदर्शन करेगी। पिछले अनुभव से, यह बहुत छोटे, लगभग छोटे ग्राफ के लिए होता है, लेकिन एक मजबूत कथन बनाने के लिए सावधानीपूर्वक परीक्षण और प्रोफाइलिंग की आवश्यकता होगी।
आप सबसे अच्छापथ-लंबाई के संदर्भ में विचार कर रहे हैं, कि कब तक अंतिम पथ एल्गोरिथ्म द्वारा उत्पादित है, तो ए * किसी अन्य इष्टतम खोज एल्गोरिथ्म के बराबर है है।
आप, सबसे अच्छापूर्णता के संदर्भ में विचार कर रहे हैं कि है, अगर इस तरह के एक रास्ता मौजूद है एल्गोरिथ्म हमेशा लक्ष्य के लिए एक रास्ता मिल जाएगा। यदि ऐसा है, तो ए * किसी अन्य पूर्ण एल्गोरिदम के बराबर है (उदाहरण के लिए, चौड़ाई-प्रथम-खोज)।
आप सबसे अच्छा मामलों में जहां ग्राफ में वजन के कुछ नकारात्मक हैं में विचार कर रहे हैं, तो आप
आप (उदाहरण के लिए bellman-ford) उन समस्याओं को हल करने के लिए एक विशेष एल्गोरिथ्म का उपयोग करने की आवश्यकता होगी, तो सर्वोत्तम पर विचार कर रहे हैं जहां कोई ह्युरिस्टिक उपलब्ध नहीं है तो आपको h(x,y)=0 forall states x and y पर वापस आना चाहिए। इस मामले में ए * सर्वोत्तम पहली खोज के बराबर है।
आप सबसे अच्छानिरंतर विन्यास रिक्त स्थान में गति नियोजन से संबंधित मामलों में विचार कर रहे हैं, तो A * कम आयामों में पर्याप्त रूप से काम कर सकते हैं, लेकिन खोज ग्राफ के भंडारण के उच्च आयाम पर अव्यावहारिक बनने के लिए शुरू होता है, और संभवतया पूरा एल्गोरिदम बढ़ जाती है उपयोग करने की आवश्यकता है (उदाहरण के RRT के लिए, द्वि-आर आर टी, RDT)
आप सबसे अच्छा मामलों में जहां ग्राफ आंशिक रूप से नमूदार है में विचार कर रहे हैं, आप केवल हर संभव कोने के एक सबसेट पता है और ग्राफ में किनारों पर किनारों पर समय, और आपको ग्राफ के अधिक निरीक्षण के लिए राज्य को बदलने की जरूरत है, तो आपको इसके लिए डिज़ाइन किए गए वैकल्पिक एल्गोरिदम की आवश्यकता है (उदाहरण के लिए, केओनिग का लाइफेलॉन्ग प्लानिंग ए *, एलपीए *, वास्तव में यह करता है)।
आप सबसे अच्छा मामलों में जहां समय से अधिक ग्राफ परिवर्तन, जो रोबोटिक्स में अक्सर तब होता है जब आप बाधाओं ले जा, तो आप एक एल्गोरिथ्म जो (उदाहरण के Stentz के D* या कोएनिग के लिए इस बात के लिए डिज़ाइन किया गया है की जरूरत है विचार कर रहे हैं & लिखचेव डी * -लाइट)।
+1, हालांकि एलपीए * का आपका विवरण गलत है। एलपीए * ए * की तरह है, लेकिन ग्राफ़ * में छोटे बदलावों के बाद कई रनों पर (संशोधित किनारे-भार, जोड़ों को जोड़ना/निकालना) *, यह ए * को फिर से चलाने से बहुत तेज़ गति से शुरू करने के लिए सर्वोत्तम पथ को फिर से समझ सकता है। शुरुआत/खत्म हमेशा एक ही स्थान पर होते हैं; यह डी \ * - लाइट * (जो पूरी तरह से डी \ * पूरी तरह से अप्रचलित है) * के विपरीत है, जिसमें "प्रारंभ नोड" * (जो चलती रोबोट, या जो कुछ भी दर्शाता है) * लगातार पुनर्मूल्यांकन के बीच सबसे अच्छे रास्ते के साथ आगे बढ़ रहा है। [यह भी देखें] (http://cstheory.stackexchange.com/a/11866/8532)। –
एक बेहद सरल विकल्प (हेरिस्टिक के साथ कोई झगड़ा नहीं) Collaborative Diffusion है। यह शानदार काम करता है जब आप एक लक्ष्य या एक समूह के किसी भी सदस्य, अंधाधुंध लक्षित करना है, और इस मामले में तेजी से एक * से हो सकता है। यह गेम "आप वार्मर/कोल्डर प्राप्त कर रहे हैं" की नकल करता है।
सहयोगी प्रसार एक "समूह" प्रति एक हीटमैप बनाता है जिसे आप लक्षित करना चाहते हैं ... यदि आप एक विशिष्ट लक्ष्य को ट्रैक करना चाहते हैं, तो इसे केवल उस लक्ष्य के लिए हीटमैप बनाकर अपने स्वयं के समूह के रूप में देखें; सहयोगी डिफ्यूजन का डोमेन फुटबॉल की तरह खेल है (जहां एजेंटों की दोनों टीमें गेंद और गोलपोस्ट को विशेष रूप से ट्रैक करती हैं, जिससे केवल 3 प्रभाव वाले नक्शे होते हैं) या पॅकमैन (समान, एकाधिक एजेंट पीएसी ट्रैकिंग) या सेना के खेल जहां शरीर का प्रतिनिधित्व करने वाला एक संयुक्त तापमैप होता है (कुल मिलाकर) प्रत्येक सेना के उस सेना में प्रत्येक एजेंट से निर्धारित किया गया है, ताकि एक सेना "अन्य सेना के भीतर विशिष्ट इकाइयों" की बजाय "अन्य सेना" तक पहुंच सके। इस सामान्यता में प्रदर्शन में वृद्धि हो सकती है।
घूमने में हिल-क्लाइंबिंग (वर्तमान सेल से एक गर्म पड़ोसी सेल तक जा रहा है) जब तक हम गंतव्य (सबसे गर्म बिंदु) तक नहीं पहुंच जाते। दृष्टिकोण अंतर्निहित बाधाओं यानी अन्य एजेंटों से संबंधित है।
यह सबसे उपयुक्त है जहां मानचित्र कई, चलती इकाइयों के साथ काफी घनी आबादी वाले होते हैं, इस प्रकार व्यापक प्रसार को उचित ठहराते हैं जो प्रत्येक अद्यतन पर संपूर्ण खोज स्थान पर होना चाहिए।यह स्पष्ट है कि एक अच्छी तरह से ट्यून किए गए ए * दृष्टिकोण एक बड़े, स्पैस मानचित्र में परिमाण का सस्ता हो सकता है, जहां हमारे पास सिर्फ एक इकाई है जो केवल एक इकाई को लक्षित करती है, क्योंकि इस मामले में आप केवल एक अंश पर काम कर रहे हैं साधक और लक्ष्य के बीच नक्शा टाइल्स का; जबकि सहयोगी डिफ्यूजन के साथ, आप पूरे मानचित्र में बस एक ही काम करने के लिए फैल रहे हैं, जिससे इसे और अधिक महंगा बना दिया जाता है।
यह ध्यान देने योग्य है कि एक स्थिरता से गुस्से में गुणा करने की चाल ह्यूरिस्टिक को अस्वीकार्य बनाती है, और खोज में ऐसे परिणाम अब इष्टतम नहीं होते हैं। –
हां, लेकिन जैसा ऊपर बताया गया है, वहां साबित सीमाएं हैं जो इष्टतम परिणाम का अनुमान लगाएंगे। विशेष रूप से, निरंतर, सी के लिए, आपका परिणामी पथ इष्टतम पथ तक सी गुना से अधिक नहीं होगा। – sjdlgjsljg