從“k倍動(dòng)態(tài)減法游戲”出發(fā)探究一類組合游戲問題

1、從“K倍動(dòng)態(tài)減淡游戲”開始，通過組合游戲問題、列表、列表、1:介紹2:問題毽子3:動(dòng)態(tài)規(guī)劃通識(shí)解決方案4:基于動(dòng)態(tài)規(guī)劃的最優(yōu)化4.1“K倍動(dòng)態(tài)減淡游戲”5:不是基于動(dòng)態(tài)規(guī)劃的思考5.2貪心解決BOI 2008游戲P狀態(tài)意味著之前剛剛操縱的玩家有必勝戰(zhàn)略清理：P狀態(tài)的所有滯后都是N狀態(tài)，N狀態(tài)至少是一個(gè)滯后是P狀態(tài)。過程動(dòng)態(tài)規(guī)劃解決方案，第1步：將所有“勝利結(jié)束狀態(tài)”標(biāo)記為P狀態(tài)，將“失敗結(jié)束狀態(tài)”標(biāo)記為N狀態(tài)。步驟2:所有待定狀態(tài)發(fā)現(xiàn)中的所有后續(xù)狀態(tài)都被確定為N狀態(tài)，并設(shè)置為P狀態(tài)。步驟3:在所有待定狀態(tài)發(fā)現(xiàn)中，一次可以到達(dá)P狀態(tài)的狀態(tài)設(shè)置為N狀態(tài)。步驟4:如果在前面的兩個(gè)步驟中創(chuàng)建了新的P狀

2、態(tài)或N狀態(tài)，則流程結(jié)束，否則返回步驟2。時(shí)間復(fù)雜度所有狀態(tài)的決策數(shù)的總和，K倍動(dòng)態(tài)減博弈，有整數(shù)S(=2)，先行子從S中減去數(shù)X，至少等于1，但小于S。此后雙方交替將S減為正整數(shù)，但在前一輪渡邊杏超過對(duì)方減去的數(shù)的K倍，減少到0的一方獲勝。問：誰有必勝的策論？K=2，A第一輪減去2的A第二輪減去1的b第一輪減去4的A勝利，通式解決方案，NP(m，n)意味著s還剩下m牙齒，即將進(jìn)行下一步操作的玩家可以減去最大n狀態(tài)。如果要在NP(m，n)狀態(tài)下操作的玩家獲勝，則規(guī)定NP(m，n)=1，否則NP(m，n)=0。如果動(dòng)態(tài)規(guī)劃計(jì)算所有NP(m，n)，則是判定勝負(fù)的時(shí)間復(fù)雜度O(n3)。最優(yōu)化1，狀態(tài)單

3、調(diào)，狀態(tài)NP(m，N)是關(guān)于N單調(diào)的。記錄f(m)=minn|NP(m，n)=1，最優(yōu)化1，NP(m，n)=0隨機(jī)r=1，2，3n具有m-r0和nn牙齒時(shí)，n0，動(dòng)態(tài)過渡表達(dá)式：f(m)=minn|f(m-n)kn時(shí)間復(fù)雜度：O(S2)，2決策單調(diào)性最優(yōu)化，2決策單調(diào)性最優(yōu)化最后根據(jù)f(m)確定新“墻”的位置和長度，然后新建時(shí)間復(fù)雜度：O(S)，BOI 2008 game，n*n板，每個(gè)網(wǎng)格為黑色或白色。白色格子是游戲區(qū)，黑色格子代表障礙。指定兩個(gè)格點(diǎn)AB。分別是前后的起始晶格。a和B兩個(gè)牙齒不一致。游戲中雙方輪流操作。每次操作，玩家都會(huì)上下朝四個(gè)格子中的一個(gè)走一步，但不能進(jìn)入黑色格子。有一種

4、特殊情況，即，一個(gè)玩家正好進(jìn)入現(xiàn)在對(duì)方所在的格子里，就再走一步(不必是同一個(gè)方向)，“跳過對(duì)方”。勝負(fù)的判定是這樣的。如果一方進(jìn)入對(duì)方的開始格子，即使贏了，跳過對(duì)方也算是贏了。用，(x1，y1，x2，y2)表示狀態(tài)的通識(shí)解決方案。其中(x1，y1)是a的當(dāng)前位置，(x2，y2)是b的當(dāng)前位置。還需要一個(gè)狀態(tài)，以指示當(dāng)前作業(yè)是A還是B。因此，每個(gè)狀態(tài)的狀態(tài)切換成本為O(1)，但因?yàn)榭倳r(shí)間復(fù)雜度O(n4)太高，所以總狀態(tài)至少為O(n4)。狀態(tài)數(shù)為O(n4)也意味著沒有動(dòng)態(tài)規(guī)劃優(yōu)化的馀地，算法設(shè)計(jì)必須擺脫動(dòng)態(tài)規(guī)劃框架。貪心的想法，“第一”貪心的信號(hào)，兩個(gè)人要沿著兩個(gè)起點(diǎn)之間的最短路徑走。兩個(gè)人要走的

5、距離相同，所以如果沒有“跳過對(duì)方”的規(guī)則，先行者會(huì)贏！結(jié)論：如果前置任務(wù)A能避免B“跳過A”，那么A就贏了。如果后數(shù)B能在最短路徑上保證“跳過A”，那么B就贏了。BOI正式回答，D是AB之間的最短距離。如果d是奇數(shù)，a就贏了！因此，考慮到D點(diǎn)偶數(shù)，它存儲(chǔ)為數(shù)組LAi，位于AB最短路徑中，并且有距離A和I的晶格。NP_Ai、J、K表示輪到A運(yùn)行時(shí)LAi的第J個(gè)域中有A，LAd-i的第K個(gè)域中有B的狀態(tài)。NP_Bi、J、K表示B工作時(shí)A在LAi 1的第J個(gè)域中，B在LAd-i的第K個(gè)域中的狀態(tài)。BOI正式回答錯(cuò)誤，在BOI的正式回答中，數(shù)組NP_Ai，j，k和數(shù)組NP_Bi，j，k表示的狀態(tài)總數(shù)為

6、O(n3)數(shù)量級(jí)。但是，格式的3位數(shù)組并不意味著包含的數(shù)據(jù)是立方體。事實(shí)上，牙齒三維中沒有一個(gè)是O(n)。額外的最優(yōu)化，首先，不屬于任何排列LAi的白色格子涂黑，因?yàn)樗窈Ｑ?。觀察結(jié)果：對(duì)于每個(gè)I，陣列LAi的晶格將所有白色區(qū)域分為兩部分。一部分與A的距離小于I，另一部分大于I。額外的最優(yōu)化，每層LAi都是封閉的、有序的存儲(chǔ)，可以證明LAd-i晶格形成的環(huán)可以分為兩部分。一段LAd-i，k以a戰(zhàn)勝NP_Ai，j，k，另一段創(chuàng)建NP _ ai，存儲(chǔ)附加最優(yōu)化、邊界點(diǎn)即可！狀態(tài)是環(huán)形的，所以有兩個(gè)分界點(diǎn)。lefti、j、righti、j牙齒兩點(diǎn)，時(shí)間復(fù)雜度：O(n2)！概括地說，NP狀態(tài)定理和基于此的動(dòng)態(tài)規(guī)劃(NP狀態(tài)定理)建立了解決