मुझे पता है कि ए * डिजस्ट्रा के एल्गोरिदम से बेहतर है क्योंकि यह ह्युरिस्टिक मूल्यों को ध्यान में रखता है, लेकिन ए * और जंप प्वाइंट सर्च से जो सबसे कम पथ खोजने के लिए सबसे कुशल एल्गोरिदम है बाधाओं के साथ एक पर्यावरण में? और मतभेद क्या हैं?पथ खोज एल्गोरिदम: ए * बनाम जंप प्वाइंट सर्च
जंप प्वाइंट सर्च ग्राफ पर कुछ स्थितियों के आधार पर एक बेहतर ए * है। इस प्रकार, यदि आप इन शर्तों को पूरा करते हैं (वर्दी-लागत ग्रिड ज्यादातर), जेपीएस ए * से समान रूप से बेहतर है (समान इष्टतमता, सर्वोत्तम मामलों में परिमाण का क्रम बेहतर हो सकता है और बदतर मामला शायद एक ही जटिलता है लेकिन थोड़ा थोड़ा स्थिर है) , लेकिन यदि आप शर्तों को पूरा नहीं करते हैं, तो आप इसका उपयोग नहीं कर सकते हैं।
ए * पर जेपीएस के सुधार मूल रूप से, यदि आपके पास एक समान लागत फ़ंक्शन वाला ग्राफ है (यह उसी दिशा में ए से बी और बी से सी तक जाने के लिए समान होता है), तो आप छोड़ सकते हैं कुछ मामलों में कुछ कदम और बी
जेपीएस ए * पर एक छंटनी तकनीक है, आप उन मामलों को हटाते हैं जिनकी आपको मूल्यांकन करने की आवश्यकता नहीं है, क्योंकि आप जानते हैं कि वे उप-इष्टतम होंगे । वर्दी लागत ग्रिड की स्थिति के कारण आप इसे जानते हैं।
वैचारिक रूप से, यह एक गैर वर्दी ग्रिड, जहां पड़ोसी नोड्स प्रतिनिधित्व करते हैं कितनी दूर तुम कूद आप प्रदर्शन की लागत के साथ, एक बाधा का सामना किए बिना उस दिशा में जा सकते हैं पर एक * का उपयोग कर के बराबर है। तो अगर आप एक बाधा का सामना किए बिना सही पर 10 नोड्स जा सकते हैं, तो आप इस कम कर सकते हैं (या सीधे के लिए कूद) 10 की लागत * ग, जहां सी (स्थिर) लागत एक नोड से करने के लिए जाने के लिए है के साथ एक एकल नोड दाईं ओर एक और।
मूल पेपर here.
धन्यवाद! यह मेरे प्रश्न को कुछ बिंदु –
@ Thilan.L पर हल करता है आप वास्तव में क्या खो रहे हैं? शायद मैं आपको बेहतर जवाब देने के लिए अपना उत्तर अपडेट कर सकता हूं। – Leherenn
अग्रिम धन्यवाद यह हल हो गया था :) –