毒老鼠演算法

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 串轉換成整數而已。