这个问题是否完整？

假设有一行x装满饰品（随机数量）的箱子，在明显（你可以看到每个箱子里有多少饰品）。现在有两名球员可以轮到他们从任何一端选择一个垃圾桶。他们不能放弃回合。提出一个玩家获得最大数量小饰品的策略。这个问题是否完整？

x是偶数。

这是一个NP完整的问题？它是否类似于布尔SAT？

2010-06-25 user376070

你真的想制定一个策略，可以与任意对手竞争，或者你想为给定的饰品线创建一系列动作（玩家一个*和*玩家二），这样玩家获得最大可能数量的饰品？ – phimuemue 2010-06-25 09:08:07

@phimuemue - 本质上，如果我是player1，我需要遵循什么样的策略才能获胜。鉴于玩家2做任何形式的移动。尽管他也会发挥自己的优势。我认为你需要列举所有可能的路径并找到该路径的回报。玩家只是继续走这条路。 – user376070 2010-06-25 09:31:44

问一个游戏（在游戏理论的意义上，这是什么）是否是NP完全没有意义。不过，你可以问一个特定的策略是否是NP完全的。 – 2010-06-25 09:41:31

这是非常简单的问题，它不是NP完整的。这里是算法的简短描述，它是基于动态规划的。

可以[i] - 存储一些饰品的数组。
F [i，j] - 确定什么是最好的举动，如果只有罐头从i到j是可用的。 0表示从左侧取，1表示从右侧取。
G [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; 
     }

对评论缺乏抱歉，但如果您阅读了一些关于动态编程的文章，您将会得到它没有任何问题。

来源

2010-06-25 10:07:27

不，它可以通过O(x^2)中的动态编程轻松解决。看问题10 here。

来源

2010-06-25 10:02:37 IVlad

这个问题似乎是alpha-beta-pruning的完美选择，因为它很容易为你的积分导出一个下界。假设玩家面对偶数个垃圾箱。然后他可以通过某种方式获得偶数或全部奇数位置上的所有仓位：

假设我们有1 0 1 0 1 0，那么他可以将左边的1和无论对手做什么，他只是继续拿起1。

所以一个容易计算的下界是偶数位置所有仓位的总和和奇数位置上所有仓位的总和的最大值。

对于“奇怪”的玩家，你可以只取（长度+ 1）/ 2的最小值的总和，这不如“偶数”玩家的界限，但也很容易计算。

我觉得在这些范围内搜索树对于实际应用来说是稀疏的（我猜你总是可以找到这种类型的问题的“病态”反例），所以解决方案应该非常快。

来源

2010-06-25 11:43:41 Landei

很明显，第一个球员有一个领带/赢的战略。他所要做的就是检查奇数仓位或者偶数仓位是否有更多的总数，然后他可以轻松地打出对手，让对手拿起“失败”奇偶的仓位。

例如：

2,6,11,4,7,3

这里奇数位置为更好（20对13），所以播放器1应该选择2.然后播放器2必须选择6或3，它们都处于均匀位置。如果选择3，玩家1应选择7，依此类推。实际上，选手1应该总是选择对手所选择的位置旁边的位置，并保证打平或取胜。

来源

2010-06-25 22:10:53

这个问题是否完整？

回答

相关问题