ए * ओपन सेट के लिए सबसे अच्छी डेटा संरचना क्या है?

Question

मैं पहली बार ए * विकसित कर रहा हूं, और मैं खुले सेट के लिए प्राथमिकता_क्यू का उपयोग कर रहा था, जब तक कि मुझे एहसास न हो कि आपको यह जांचने की आवश्यकता है कि नोड्स खुले सेट में भी हैं, न केवल नज़दीक।

बात यह है कि आप प्राथमिकता कतार में पुन: प्रयास नहीं कर सकते हैं .. तो क्यों हर कोई खुले सेट के लिए प्राथमिकता कतार की सिफारिश करता है? क्या यह अभी तक का सबसे अच्छा विकल्प है? मुझे लगता है कि इसे फिर से शुरू करने का एकमात्र तरीका एक प्रतिलिपि बना रहा है, इसलिए मैं इससे सबकुछ पॉप कर सकता हूं (भारी लागत)।

ए * पर उपयोग करने के लिए सबसे अच्छी डेटा संरचना क्या है?

Answer 1

प्राथमिकता कतार (पीक्यू) एक सार डेटा संरचना (एडीएस) है। उन्हें लागू करने के लिए कई संभावनाएं हैं। दुर्भाग्य से, C++ मानक लाइब्रेरी के साथ प्रदान की गई प्राथमिकता_क्यू सीमित है, और अन्य कार्यान्वयन ए * को लागू करने के लिए बहुत बेहतर हैं। स्पोइलर: आप std :: primary_queue के बजाय std :: set/multiset का उपयोग कर सकते हैं। लेकिन पर पढ़ें:

तो क्या आप को लागू करने की प्राथमिकता कतार से की क्या ज़रूरत है एक * है:

1. सबसे कम लागत
2. साथ नोड जाओ मनमाना तत्वों की लागत कम करें

कोई भी प्राथमिकता कतार 1. कर सकती है, लेकिन 2 के लिए, आपको "mutable" प्राथमिकता कतार की आवश्यकता है। मानक-लिब कोई ऐसा नहीं कर सकता है। इसके अलावा, आपको कुंजी को कम करने के लिए प्राथमिकता कतार में प्रविष्टियों को खोजने का एक आसान तरीका चाहिए (जब ए * पहले से खोले गए नोड के लिए बेहतर पथ पाता है)। इसके लिए दो बुनियादी तरीके हैं: आप अपने ग्राफ़ नोड के भीतर प्राथमिकता कतार तत्व को एक हैंडल संग्रहीत करते हैं (या प्रत्येक ग्राफ़ नोड के लिए उन हैंडल को स्टोर करने के लिए मानचित्र का उपयोग करें) - या आप ग्राफ़ नोड्स को स्वयं सम्मिलित करते हैं।

पहले मामले के लिए, जहां आप प्रत्येक नोड के लिए हैंडल स्टोर करते हैं, तो आप अपनी प्राथमिकता कतार के लिए std :: multiset का उपयोग कर सकते हैं। std :: multiset :: first() हमेशा आपकी "सबसे कम लागत" कुंजी होगी, और आप इसे सेट से हटाकर, मूल्य बदलने और पुनः डालने और हैंडल को अपडेट करके एक कुंजी घटा सकते हैं। वैकल्पिक रूप से, आप Boost.Heap से उत्परिवर्तनीय प्राथमिकता कतारों का उपयोग कर सकते हैं, जो सीधे "कमी-कुंजी" का समर्थन करते हैं।

दूसरे मामले के लिए, आपको किसी प्रकार का "घुसपैठ" बाइनरी पेड़ की आवश्यकता होगी - क्योंकि आपके पथदर्शी नोड्स को प्राथमिकता कतार में होना आवश्यक है। यदि आप अपना खुद का रोल नहीं करना चाहते हैं, तो Boost.Intrusive में आदेशित सहयोगी कंटेनर देखें।

Answer 2

विषय बहुत बड़ी है, मैं अगर आप अलग अलग संभावनाएं जानना चाहते हैं और एक अच्छी समझ जिनमें से डेटा संरचना अपनी स्थिति के लिए अनुकूलित किया गया है तो आप इस पेज पढ़ने का सुझाव है: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#set-representation

मेरे मामले में, द्विआधारी ढेर लागू करने और प्रदर्शन करने में कठिनाई के बीच एक अच्छा संतुलन था, जो कि मैं पूरी तरह से खोज रहा था। लेकिन शायद आप कुछ अलग खोज रहे हैं?

दस्तावेज़ का शेष एक बहुत अच्छा वे मतलब एक प्राथमिकता कतार जरूरी नहीं कि std :: priority_queue वर्ग उस भाषा के साथ आता है खेल विकास http://theory.stanford.edu/~amitp/GameProgramming/index.html

Answer 3

के लिए एक * के लिए संदर्भ है। यदि किसी में निर्मित कोई ऐसा नहीं करता है जिसे आपको स्वयं लिखने के लिए चाहिए, या कोई दूसरा ढूंढें।