समस्या
अल्फ़ा-बीटा प्रूनिंग मिनिमैक्स जैसा ही उत्तर देती है, लेकिन उन शाखाओं को छोड़ देती है जो परिणाम नहीं बदल सकतीं। यह दो सीमाएँ रखती है: alpha, वह सबसे अच्छा स्कोर जो MAX को पहले से पक्का है, और beta, वह सबसे अच्छा स्कोर जो MIN को पहले से पक्का है।
गेम ट्री पूर्ण है: हर आंतरिक नोड के branching चाइल्ड हैं, और सभी पत्तियाँ एक ही गहराई पर हैं। leaves पत्तियों के स्कोर बाएँ से दाएँ देता है। रूट MAX नोड है और स्तर MAX, MIN, MAX, … के क्रम में बदलते हैं।
alpha = -∞ और beta = +∞ से शुरू करके चाइल्ड को बाएँ से दाएँ खोजें:
- 'MAX नोड पर हर चाइल्ड के बाद: best = max(best, value), फिर alpha = max(alpha, best)।'
- 'MIN नोड पर हर चाइल्ड के बाद: best = min(best, value), फिर beta = min(beta, best)।'
- जैसे ही alpha ≥ beta हो, उस नोड के बाकी चाइल्ड छोड़ दें।
alpha_beta(leaves, branching) लागू करें।
इनपुट
leaves: बाएँ से दाएँ पत्तियों के स्कोर; लंबाई branching की कोई घात है।
branching: हर आंतरिक नोड के चाइल्ड की संख्या।
आउटपुट
[value, evaluated] लौटाएँ: रूट का मिनिमैक्स मान और कितनी पत्तियों का मूल्यांकन हुआ।
सीमाएँ
2 ≤ branching ≤ 5, leaves की लंबाई = branching^depth जहाँ 1 ≤ depth ≤ 8, अधिकतम 10,000 पत्तियाँ
-1,000 ≤ हर पत्ती ≤ 1,000
उदाहरण
इनपुट:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
अपेक्षित आउटपुट:
expected = [3, 7]इनपुट:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 7};इनपुट:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 7};व्याख्या
पहला MIN नोड 3, 12, 8 देखता है और 3 लौटाता है, इसलिए alpha = 3। दूसरा MIN नोड 2 देखता है, beta = 2 ≤ alpha, इसलिए 4 और 6 छोड़ दिए जाते हैं। तीसरा 14, 5, 2 देखता है और 2 लौटाता है। रूट का मान max(3, 2, 2) = 3 है, 9 में से 7 पत्तियों के बाद।
इनपुट:
leaves = [5, 6, 7, 4]
branching = 2
अपेक्षित आउटपुट:
expected = [5, 4]इनपुट:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
अपेक्षित आउटपुट:
std::vector<long long> expected = {5, 4};इनपुट:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
अपेक्षित आउटपुट:
long[] expected = new long[] {5, 4};व्याख्या
बायाँ MIN नोड 5 और 6 का मूल्यांकन करके 5 लौटाता है, इसलिए alpha = 5। दायाँ MIN नोड 7 (beta = 7), फिर 4 (beta = 4 ≤ 5) का मूल्यांकन करता है। सभी 4 पत्तियों का मूल्यांकन होता है और मान 5 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
गेम ट्री को बाएँ से दाएँ traverse करो, और MAX व MIN के लिए best guaranteed bounds साथ रखते चलो.
संकेत 2
Recursive minimax search use करो, जो हर child के बाद current bound update करे और दो bounds के cross होते ही रुक जाए.
संकेत 3
सिर्फ actual visited leaves count करना, और याद रखना root एक MAX node से start होता है.
अपेक्षित जटिलता
O(b^d) time in the worst case, O(d) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।