क्या यह समस्या एनपी-पूर्ण है?

Question

कहें कि सादे दृष्टि में ट्रिंकेट (यादृच्छिक राशि) से भरे डिब्बे x की एक पंक्ति है (आप देख सकते हैं कि प्रत्येक बिन में कितने ट्रिंक हैं)। अब दो खिलाड़ी हैं जो अपनी बारी के अंत में एक बिन चुन सकते हैं। वे एक मोड़ नहीं छोड़ सकते हैं। अधिकतम खिलाड़ी ट्रिंकेट प्राप्त करने के लिए एक खिलाड़ी के लिए रणनीति के साथ आओ।

x भी है।

क्या यह एक एनपी-पूर्ण समस्या है? क्या यह बुलियन एसएटी के समान है?

Answer 1

यह बहुत आसान समस्या है, और यह एनपी पूरा नहीं है। यहां एल्गोरिदम का संक्षिप्त वर्णन है, यह गतिशील प्रोग्रामिंग पर आधारित है।

क्या [i] - सरणी जो ट्रिंक की संख्या संग्रहीत कर सकती है।
एफ [i, j] - सरणी निर्धारित करना कि सबसे अच्छा कदम क्या है यदि केवल i से j तक के डिब्बे उपलब्ध हैं। 0 का मतलब बाएं तरफ से लेना है, 1 मतलब सही तरफ से लेना है।
जी [i, j] - सरणी जहां चाल की 'भलाई' संग्रहित की जाती है।

for (i=1 to n) F[i,i] = 0 
for (i=1 to n) G[i,i] = Can[i] 

for (i=1 to n-1) 
    for (j=1 to n-i) 
     tmp1 = Can[j] - G[j+1,j+i] 
     tmp2 = Can[j+i] - G[j,j+i-1] 
     if (tmp1>tmp2) 
     { 
      F[j,j+i] = 0; 
      G[j,j+i] = tmp1; 
     } 
     else 
     { 
      F[j,j+1] = 1; 
      G[j,j+i] = tmp2; 
     } 

टिप्पणियों की कमी के लिए खेद है, लेकिन यदि आप गतिशील प्रोग्रामिंग के बारे में कुछ लेख पढ़ते हैं तो आपको बिना किसी समस्या के इसे प्राप्त होगा।

Answer 2

नहीं, यह O(x^2) में गतिशील प्रोग्रामिंग के साथ आसानी से सुलभ है। समस्या 10 here देखें।

Answer 3

यह समस्या अल्फा-बीटा-प्रुनिंग के लिए बिल्कुल सही प्रतीत होती है, क्योंकि यह आपके बिंदुओं के लिए कम बाध्यता प्राप्त करना आसान है। मान लें कि खिलाड़ी को भी डिब्बे की संख्या का सामना करना पड़ता है। फिर वह सभी डिब्बे को या तो अजीब स्थितियों पर या सभी पर प्राप्त करने के लिए खेल सकता है:

कहें कि हमारे पास 1 0 1 0 1 0 है, तो वह बाईं ओर 1 ले सकता है, और जो कुछ भी विरोधी करता है, वह सिर्फ 1 को उठाता रहता है।

तो निचले बाउंड की गणना करने में आसान है, यहां तक ​​कि पदों पर सभी डिब्बे और अजीब स्थितियों पर सभी डिब्बे की राशि का अधिकतम योग है।

"विषम" प्लेयर के लिए आप केवल (लंबाई + 1)/2 छोटे मूल्यों का योग ले सकते हैं, जो कि "यहां तक ​​कि" प्लेयर के लिए बाध्य जितना अच्छा नहीं है, बल्कि गणना करने में भी आसान है।

मुझे लगता है कि इन सीमाओं के साथ खोज पेड़ व्यावहारिक अनुप्रयोगों के लिए दुर्लभ होगा (मुझे लगता है कि आप हमेशा इस प्रकार की समस्या के लिए "पैथोलॉजिकल" काउंटर-उदाहरण पा सकते हैं) इसलिए समाधान काफी तेज़ होना चाहिए।

Answer 4

यह स्पष्ट है कि पहले खिलाड़ी के पास टाई/जीत रणनीति है। उसे बस इतना करना है कि क्या अजीब स्थिति डिब्बे या यहां तक ​​कि स्थिति के डिब्बे में कुल योग होता है, और फिर वह आसानी से ऐसा खेल सकता है कि वह प्रतिद्वंद्वी को "हारने" समानता के डिब्बे लेने के लिए मजबूर करता है।

उदाहरण के लिए:

2,6,11,4,7,3

यहाँ अजीब पदों बेहतर (20 बनाम 13) हैं, इसलिए खिलाड़ी 1 2. का चयन करना चाहिए तो खिलाड़ी 2 का चयन करना होगा या तो 6 या 3, जो भी पदों पर हैं। यदि 3 चुना जाता है, तो खिलाड़ी 1 को 7 चुनना चाहिए, और इसी तरह। असल में, खिलाड़ी 1 को हमेशा अपने प्रतिद्वंद्वी द्वारा चुने गए स्थान के बगल में स्थित स्थिति चुननी चाहिए, और यह टाई या जीत की गारंटी देता है।