बिडरेक्शनल ए * (ए-स्टार) खोज

Question

मैं एक बिडरेक्शनल ए * खोज को कार्यान्वित कर रहा हूं (खोज में बिडरेक्शनल एक साथ मूल और गंतव्य दोनों से किया जाता है, और जब ये दो खोज मिलती हैं, तो मेरा सबसे छोटा होगा पथ - कम से कम अतिरिक्त तर्क के साथ फेंक दिया)।

क्या किसी को एक unidirectional ए * और bidirectionalising (!) लेने के साथ कोई अनुभव है - मैं किस तरह के प्रदर्शन लाभ की उम्मीद कर सकते हैं? मैं कम से कम खोज समय को कम से कम कम करके मानता हूं - लेकिन क्या मुझे यह बड़ा लाभ दिखाई दे सकता है? मैं सड़क नेटवर्क पर सबसे कम मार्ग निर्धारित करने के लिए एल्गोरिदम का उपयोग कर रहा हूं - यदि यह किसी भी तरह से प्रासंगिक है (मैंने एमएस के "पहुंच" एल्गोरिदम के बारे में पढ़ा है, लेकिन सीधे इसमें कूदने के बजाए इसके प्रति शिशु कदम उठाना चाहते हैं)।

Answer 1

सर्वोत्तम संभव मामले में यह हे में चला था (ख^(एन/2)) के बजाय हे (ख^n) में, लेकिन केवल तभी, आप भाग्यशाली हैं :) है

(जहां ख क्या आपका ब्रांचिंग कारक है और एन नोड्स की संख्या एक यूनिडायरेक्शनल ए * पर विचार करेगा)

यह सब इस बात पर निर्भर करता है कि दोनों खोज कितनी आसानी से मिलती हैं, अगर वे एक दूसरे को आपकी खोज में जल्दी आधे रास्ते पर पाते हैं बहुत सारे खोज समय से दूर हो गए, लेकिन यदि वे जंगली रूप से अलग-अलग दिशाओं में शाखा बनाते हैं तो आप सरल ए * (सभी अतिरिक्त बहीखाता के कारण) से धीमे हो सकते हैं

Answer 2

आप डब्ल्यू http://sourceforge.net/projects/tway/ वहाँ एक बेंच मार्किंग स्क्रिप्ट है कि मानक astar के साथ इस की तुलना करता है की कोशिश करने चींटी

Answer 3

को लागू किया है (NY शहर की सड़कों डेटा के लिए यह एक 30% समय लाभ देने के लिए लगता है) 3 अलग द्विदिश एक * खोज algos (cskit देखें) ।

• net.coderodde.cskit.graph.p2psp.general.FastSuboptimalFinder सबसे तेज़ है, लेकिन आमतौर पर इष्टतम नहीं है;
• net.coderodde.cskit.graph.p2psp.general.BHPAFinder इष्टतम और बहुत तेज़ है; अगर इष्टतमता एक आवश्यकता है, तो मैं इसका उपयोग करूंगा;
• net.coderodde.cskit.graph.p2psp.general.WhangboFinder विशेष रूप से अच्छा नहीं है।

एक्शन में एल्गोरिदम देखने के लिए, परियोजना रूट प्रकार mvn exec:java (मेवेन की आवश्यकता है) से। शुभकामनाएँ!

(संपादित:। This library प्रदान करता है 3 अलग द्विदिश ए * एल्गोरिदम तीनों इष्टतम हैं।)

Answer 4

आप के रूप में ज्यादा और अधिक कुशल बूस्टर क्लस्टरिंग विचार कर सकते हैं। this article