题解 P4232 【无意识之外的捉迷藏】

· · 题解

后续剧情在下面，首先是不带剧情的题解

先来看看30分

n<=3，我们可以分情况讨论

大部分情况都非常显然，在这里只说一下最复杂的一种情况吧

这种情况下，阿空选择原地不动显然严格劣势于选择走到2或者3，因此阿空可能的选择有两种。

阿燐可以选择下一步停在2或者3，同样也是两种。

那么具体选择哪一种呢？

由于双方选择2或者3都不是严格优势的做法，所以这种情况不存在纯策略意义下的最优策略，最优策略一定是2与3的混搭(以一定概率出2，一定概率出3)。

设阿空的期望收益为E。(则阿燐的期望收益为-E) 双方都是最优策略，则任何一方单方面改变策略都无法提高自己的期望收益。

那么这意味着，你所作出的策略应该满足这么一个条件，即对于对方所有可能的策略，你的收益期望值都不会低于E。否则，对方就可以有意改变自己走向2或3的概率，来提高她自己的收益并使其大于-E，这就与上句话矛盾了。 寻找最优策略的过程就是使这个E最大化的过程。

我们设阿燐走向2的概率为x，就可以列出方程

x+2(1-x)>=E

(t+1)x+(1-x)>=E

此例中，排除严格劣势的策略后，两个式子都取到了等号

所以有x+2(1-x)=(t+1)x+(1-x)

可以解出收益的期望值E为(2t+1)/(t+1)。

然后是正解

首先看看图的类型，有向无环图，说明阿燐和阿空只能朝着一个方向走，不可能循环。

又因为游戏时间有限,信息完全，所以状态数量是有限的，为O(n^2*t)级别。 (经提醒，即使有环也不会出现循环依赖，因为时间维度永远在向前走)

计算某种状态的期望值所的依赖的是其所有子状态的期望值，由于无环，不会出现循环依赖，所以子问题的规模比原问题小。

这样就可以通过递归来解决了。

那么具体怎么做呢？

我们来通过样例2进行解释。

用s(r,k,t)来表示阿燐站在第r个节点，阿空站在第k个节点，游戏还剩下t个时刻时阿燐期望生存的时间。

为了计算出s(2,1,4),根据初始状态能转移到的状态，我们画出两人的收益表。

(因为是零和博弈，所以这里以阿燐的收益为准，阿空的收益为相反数)。

可以看出问题被化为了一个个子问题，规模也变小了。

那么我们递归下去先计算好暂时不知道的每一项。

这里应当使用记忆化搜索来存储已经计算好的子问题，因为同一个子问题可能被计算多次(其实就是DP)。

然后得出一个具体数值的表:

根据n<=3中提到的方法，我们同样可以列出式子，然后会发现它就是线性规划。 直接套板子就可以了。

求这个线性规划其实就是在求解纳什均衡。

更详细说明可以参考下文: http://www.ixueshu.com/document/ea63e86bd7c77896.html

设所用线性规划算法的时间复杂度为O(f(n))

则算法的总时间复杂度O(n^2tf(n))

标程用的单纯形，最坏情况下复杂度是指数级别的，但最大规模数据(n=20,边全满,t=20)只跑了不到50ms就过了...

那么这就是本题的解法了。

后续剧情

（六）无意识之外的捉迷藏

这次.....真的没有那么容易了。

这个问题的复杂程度超出了自己的想象... 不得不说，这是一件很痛苦的事情。

我为了解决这个问题，四处查询资料，学习新知识，在中途还因为选择方向错误而碰了壁。

多亏地灵殿有一些空出来的房间，这几天干脆就住在了这里。

这里的饭真香啊。觉说我们是很友好的人，虽然我心里也会胡思乱想一些奇怪的事情，不过她好像并不怎么介意。

嗯，那么话不多说，我们就少绕点弯路，来谈一谈问题最终的解决思路吧。

首先看看图的类型，有向无环图，那么说明阿燐和阿空只能朝着一个方向走，不可能产生循环。有 n 个节点，时间最多为 t。这意味着在这个问题中，所有可能出现的情况数是 n^2*t这个级别。

为什么呢？因为阿燐的位置有 n 个选择，阿空也有 n 个，双方位置确定时，当前 的时间可能有 t 种，所以就是 nnt 中状态咯。

我们用 s(r,k,t)来表示阿燐站在第 r 个节点，阿空站在第 k 个节点，游戏还剩下 t 个时刻时阿燐期望生存的时间。

嗯，就以这个图为例吧。

我们最终的目的就是计算 s(2,1,4)。

这时阿燐有 3 种选择。走到 3,4 或原地不动。

阿空有 4 种选择，走到 2,3,5 或原地不动。

那么这就产生了 12 种结果

那么，为了计算 s(2,1,4)我们需要先计算一系列的 s(x,x,x)。

还记得刚才的结论吗？计算某种状态的期望值所的依赖的是其所有子状态的期望值，由于无环，不会出现循环依赖，所以子问题的规模比原问题小。

这样，我们就可以”递归”来解决了。

那么根据这个表，怎样算出具体的策略和生存时间期望呢？

这又是另一个问题了。

我们可以这样简单理解，何为最优策略？

双方都是最优策略，意味着任何一方单方面改变策略都无法提高自己的收益。

双方达成的这种平衡，就叫做”纳什均衡”。

假如对方可能做出 a,b,c 三种选择。那么无论对方最终做出了怎样的选择，你的收益一定是一样的。因为如果对方选择 a 收益更高，那么她就可以有意地提高做出 a 选择的概率，来提高自己的收益，这和”任何一方单方面改变策略都无法提高自己的收益”相矛盾。

不过很遗憾，最终的解决方案并不是这样的，因为很难用较低的时间代价判断出哪些策略相组合会严格劣于其他策略的组合。最终选用的方案是线性规划，由于比较复杂，就不详细说明了。

好啦，那么这样，恋恋心头的难题就解决了。

真想让你们也看看恋恋笑容洋溢的表情呢。

这次的地底旅行，也快要结束了吧？