अल्फा बीटा खोज समय जटिलता

Question

मैं मिनीमैक्स और अल्फा-बीटा छंटनी की मूल बातें समझता हूं। सभी साहित्य में, वे सबसे अच्छे मामले के लिए जटिलता के बारे में बात करते हैं ओ (बी^(डी/2)) जहां बी = शाखाकरण कारक और डी = पेड़ की गहराई, और आधार मामला तब होता है जब सभी पसंदीदा नोड्स होते हैं पहले विस्तारित

"सर्वश्रेष्ठ मामले" के मेरे उदाहरण में, मेरे पास 4 स्तरों का बाइनरी पेड़ है, इसलिए 16 टर्मिनल नोड्स में से, मुझे अधिकतम 7 नोड्स में विस्तार करने की आवश्यकता है। यह ओ से संबंधित कैसे है (बी^(डी/2))?

मुझे समझ में नहीं आता कि वे ओ (बी^(डी/2)) कैसे आते हैं।

कृपया, क्या कोई इसे मुझे समझा सकता है? बहुत बहुत धन्यवाद!

Answer 1

ओ (बी^(डी/2)) अल्फा-बीटा छंटनी की सबसे अच्छी स्थिति समय जटिलता के अनुरूप है। Explanation:

एक (औसत या निरंतर) ख के कारक शाखाओं, और घ परतों की खोज गहराई, पत्ती नोड का मूल्यांकन पदों की अधिकतम संख्या (जब इस कदम आदेश pessimal है) के साथ

हे (ख है बी ... * बी) = ओ (बी^डी) - एक साधारण मिनीमैक्स खोज के समान ही। यदि खोज के लिए चलने का क्रम इष्टतम है (जिसका अर्थ है कि सबसे अच्छी चाल हमेशा पहले खोजी जाती हैं), मूल्यांकन किए गए पत्ते नोड स्थितियों की संख्या विषम के लिए ओ (बी * 1 * बी * 1 * ... * बी) के बारे में है गहराई और ओ (बी * 1 * बी * 1 * ... * 1) गहराई के लिए, या ओ (बी^(डी/2))। बाद के मामले में, जहां खोज की पाली भी है, प्रभावी ब्रांचिंग कारक को इसके वर्ग रूट में घटा दिया गया है, या समकक्ष, खोज गणना की समान राशि के साथ दोगुनी हो सकती है।

b * का विवरण 1 * ख * 1 * ... कि सभी पहले खिलाड़ी के चाल सबसे अच्छा एक खोजने के लिए अध्ययन किया जाना चाहिए, लेकिन प्रत्येक के लिए, केवल सबसे अच्छा दूसरे खिलाड़ी के इस कदम का खंडन करने के लिए आवश्यक है सबसे पहले (और सबसे अच्छा) पहला प्लेयर चाल - अल्फा-बीटा सुनिश्चित करता है कि कोई अन्य दूसरा प्लेयर चाल पर विचार किया जाना चाहिए। इसलिए आपके मामले में की तुलना

हे एक समारोह के सीमित व्यवहार का वर्णन करता है जब तर्क एक विशेष मान या अनंत की ओर जाता है,:

बस रखो, तुम "छोड़" हर दो स्तर ठीक ओ (बी^(डी/2)) बी और डी के छोटे मूल्यों के साथ वास्तव में समझ में नहीं आता है।