毒老鼠算法

A. 算法笔记之博弈问题——猫和老鼠

博弈问题，需要注意，对于每个玩家，都会争取：

LeetCode913. 猫和老鼠

两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。

图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。

老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。

在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。

此外，猫无法移动到洞中（节点 0）。

然后，游戏在出现以下三种情形之一时结束：

如果猫和老鼠出现在同一个节点，猫获胜。
如果老鼠到达洞中，老鼠获胜。
如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：

如果老鼠获胜，则返回 1；
如果猫获胜，则返回 2；
如果平局，则返回 0 。

题目描述比较长，但其实还是很好理解的。需要注意，每个玩家都会争取自己获胜。本题就是简单的深度优先搜素+记忆化问题了。

这里考虑的是怎么才能算平局，我们采取的方法是，如果有n个节点，到2n轮如果还没出结果，就认为可以平局了。

需要注意的是记忆化，memo[i][j][k] 代表猫在i，老鼠在j，在第k轮的结果。

B. 逻辑算法题(不断更新)

问：有1000瓶药剂和10只老鼠，药剂中有1瓶毒药，喝了一周内死亡（有的题目改成了五分钟，五分钟真亏他能喂完），如何在仿早一周内找到这瓶毒药。
答：将这1000瓶药剂编号0~999，并转换为二进制 就是0000000001~1111101000，从右向左开始，让第一只老鼠喝所有右起第一位编号为1的药剂，第二只老鼠喝所有右起第二位编号为1的药剂，依次类推，10只老鼠喝完10位的药剂，一周后，如果第一只老鼠死亡，那么毒药的从右起第一位为1，未死亡的话就为0，所以根据死亡状态就可以知道该瓶毒药的二进制。
例如状态是：死亡，存活，死亡，存活，存活，存活，死亡，存活，死亡，存活 = 010111010=186
从上面例银瞎子就可以知道第二种和第三种问题的解法了吧

测试时间提升为两周就说明第一周测试不死的老鼠可以拿来继续第二周的测试 ，所以老鼠的状态就变成了三种：存活（未实验），死亡，实验后存活。
将全部药剂编号后转为三进制数，老鼠右起依次喝0编号的药剂，如果死亡，那么该位编号为0，锋大空如果未死亡，那么可能为1和2，第二周把存活的老鼠继续喝该位1编号的药剂，如果死亡就为1，存活就为2，这样就找到了毒药的三进制编号，然后转换成下标即可。

总结:有 n 只小白鼠 m周的时间可以从 (m+1)^n 个瓶子中检验出毒药来。

C. 深度优先算法 和 宽度优先算法 的优缺点

1、深度优先算法占内存少但速度较慢，广度优先算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。
2、深度优先与广度优先的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。
3、这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度优先下一次扩展的是本次扩展出来的子节点中的一个，而广度优先扩展的则是本次扩展的节点的兄弟点。在具体实现上为了提高效率,所以采用了不同的数据结构。

D. 有3只老鼠,8瓶水,其中一个有毒,喝到有毒的水之后,老鼠一周后会准时死亡

给瓶子编号0~7，并把编号翻译成二进制串，刚好可以用三位二进制来表示。让三只老鼠分别对应三位二进制，然后形成如下交叉表：
老鼠1 老鼠2 老鼠3
0 = 0 0 0
1 = 0 0 1
2 = 0 1 0
3 = 0 1 1
4 = 1 0 0
5 = 1 0 1
6 = 1 1 0
7 = 1 1 1
其中二进制位为1的地方表示哪只老鼠吃哪瓶药。即：
老鼠1应该喝4,5,6,7号的药；
老鼠2应该喝2,3,6,7号的药；
老鼠3应该喝1,3,5,7号的药。
最后观察的时候，可以根据老鼠死了的情况，0表示没死，1表示死了。
比如三只老鼠死了的情况是(1,0,1)则表示5号药是有毒的。因为只有这种情况下才会导致老鼠1和老鼠3死掉。
至于程序嘛。。。懒得写了 = = 只是单纯的把0 1 串转换成整数而已。