जावा में एक स्टार (ए *) एल्गोरिदम का कार्यान्वयन

Question

अस्वीकरण: मेरे पास जावा में बहुत कम पृष्ठभूमि है, क्योंकि मैं मुख्य रूप से एक सी # डेवलपर हूं।

ए * एल्गोरिदम के जावा कार्यान्वयन करना चाहते हैं।
हां, मैंने एक ही ऑनलाइन के कई संस्करण देखे और मैं उनके बीच चयन करने में असमर्थ हूं।

मैं ए * एल्गोरिदम कार्यान्वयन की तलाश में हूं जो जावा की सभी नई सुविधाओं का उपयोग करता है जो एल्गोरिदम को तेज़ी से बनाता है (भले ही एक छोटा सा भी)। इसका कारण यह है कि हम MMO पर पथ-खोज के लिए कार्यान्वित कर रहे हैं और इसलिए, प्रदर्शन सर्वोच्च प्राथमिकता है।

कोई पॉइंटर्स (कम से कम कहां देखना है)?

Answer 1

कई कोशिश करें, मापें, सबसे तेज़ चुनें, अपनी आवश्यकताओं के अनुरूप। प्रदर्शन ज्यादातर ह्युरिस्टिक फ़ंक्शन की पसंद से निर्धारित होता है, जो ए * उचित से स्वतंत्र होता है।

यदि ह्युरिस्टिक तय किया गया है, तो प्राथमिकता कतार का कार्यान्वयन बाधा बनने की संभावना है, इसलिए pairing heaps आज़माएं। ये अभ्यास में सबसे तेज ढेर डेटा संरचनाओं में से कुछ हैं, और उन्हें बाइनरी ढेर पर लाभ होता है जो वे ओ (1) सम्मिलन समय + एमोरेटेड ओ (लॉग एन) पॉप-मिनट के लिए अनुमति देते हैं। यह कई ए * लूप के अपेक्षित मामले में महत्वपूर्ण है, जहां कतार भर जाती है, लेकिन पूरी तरह से खाली नहीं होती है, यानी, प्रविष्टियों की संख्या पॉप की संख्या से कहीं अधिक है।

यदि स्मृति कोई समस्या बन जाती है, तो पुनरावर्तक-गहराई ए * (आईडीए *) या रिकर्सिव सर्वश्रेष्ठ-प्रथम खोज (आरबीएफएस) पर स्विच करें।

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

एल्गोरिदम के लिए Russell and Norvig और मुद्दों की अच्छी चर्चा के लिए देखें।

Answer 2

यदि प्रदर्शन आपकी सर्वोच्च प्राथमिकता है, तो ए * शायद आपकी सबसे अच्छी पसंद नहीं है। ए * एक सटीक समाधान प्रदान करता है, और नतीजतन यह तब तक संसाधित रहेगा जब तक कि यह सही उत्तर न मिले। ऐसे अन्य हल्के समाधान हैं जो बहुत तेज़ समय में पर्याप्त समाधान प्रदान करते हैं: उदाहरण के लिए पहाड़ी चढ़ाई या सबसे पहले, पहले भी एक साधारण गहराई लागू होती है।