एक त्रिभुज वातावरण में पथ खोजने के लिए * खोज में सुधार

Question

मेरे पास एक ऐसा क्षेत्र है जो बाध्यकारी त्रैमासिक त्रिकोण द्वारा दर्शाया गया है। मैं दो बिंदुओं के बीच पथ खोजने की समस्या के साथ खेल रहा हूं। मैं इस समस्या से निपटने के लिए संदर्भ बिंदु के रूप में मार्सेलो कल्लमैन द्वारा प्रदान किए गए पेपर का उपयोग कर रहा हूं। हालांकि, Kallmann paper link द्वारा प्रस्तावित Chazelle फ़नल एल्गोरिदम का उपयोग करने के बजाय, मैं ए * खोज एल्गोरिदम का उपयोग करने की योजना बना रहा हूं जो ग्रिड पर्यावरण में पथ को कुशलता से योजनाबद्ध करता है।

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

यहां कालमैन का आंकड़ा लक्ष्य तकनीक के मध्य बिंदु के उपयोग को प्रदर्शित करने के लिए लक्ष्य नोड युक्त त्रिभुज के विभिन्न पथ उत्पन्न करने के लिए है।

अब इस तकनीक ठीक काम करता है जब त्रिकोण घनत्व एक क्षेत्र में इतना बड़ा नहीं है। लेकिन कहें कि अंक के एक सेट के लिए जेनरेट त्रिकोण,

मैं सोच रहा था कि आईडीए * या आईडी-डीएफएस जैसी किसी अन्य तकनीक का उपयोग करके एल्गोरिदम की दक्षता में सुधार करने का कोई तरीका है या नहीं? एक त्रिभुज कमी ए * (टीआरए *) प्रस्तावित किया गया है, लेकिन मैं इसे समझ नहीं पाया क्योंकि यह बहुत औपचारिक रूप से परिभाषित किया गया था। टीआरए * विधि का विवरण डेमैन द्वारा इस thesis की धारा 5 में पाया जा सकता है।

मैं इस पर कुछ विचारों की सराहना करता हूं। अगर कुछ कोड साझा करने की आवश्यकता है, तो मैं इस पोस्ट को संपादित कर दूंगा।

Answer 1

ध्यान दें कि आईडी एल्गोरिदम कार्य को दोहराने से ए * द्वारा किए गए बहीखाता की लागत से व्यापार करते हैं, इस प्रकार संभावित रूप से उन्हें धीमा कर देते हैं (लेकिन उम्मीद है कि बहुत धीमी नहीं है)। तो आप किस उपाय को सुधारने की क्षमता में सुधार करने की कोशिश कर रहे हैं, यह प्रभावित करेगा कि यह कितना उपयोगी होगा।