एओ * एल्गोरिदम को कैसे कार्यान्वित करें?

Question

मैंने देखा है कि जब हम खोज एल्गोरिदम लागू करते हैं तो कुछ डेटा संरचनाओं का उपयोग किया जाता है। उदाहरण के लिए, हम बीएफएस को लागू करने के लिए कतार का उपयोग करते हैं, ए * एल्गोरिदम लागू करने के लिए डीएफएस और न्यूनतम-ढेर को लागू करने के लिए ढेर। इन मामलों में, हमें खोज पेड़ को स्पष्ट रूप से बनाने की आवश्यकता नहीं है।

लेकिन मुझे एओ * एल्गोरिदम की खोज प्रक्रिया अनुकरण करने के लिए एक सरल डेटा संरचना नहीं मिल रही है। मैं जानना चाहता हूं कि खोज पेड़ का निर्माण स्पष्ट रूप से एओ * एल्गोरिदम लागू करने का एकमात्र तरीका है? क्या कोई मुझे एक कुशल कार्यान्वयन प्रदान कर सकता है? तुम्हारी मदद के लिए शुक्रिया।

Answer 1

अस्वीकरण: मैंने एओ * लागू नहीं किया है, इसलिए मैं गलत हो सकता हूं।

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

क्या कोई मुझे एक कुशल कार्यान्वयन प्रदान कर सकता है?

आपको कम से कम कुछ छद्म कोड या यहां तक ​​कि कोड का एक टुकड़ा प्रदान करके कुछ प्रयास दिखाने की ज़रूरत है जो दिखाती है कि आपने समस्या पर हमला कैसे किया है। फिर हम समझ सकते हैं कि डेटा संरचना में सुधार करके दक्षता में वृद्धि कैसे करें।