算法合集之由感性認識到理性認識——透析一類搏弈游戲的解答過程-資料下載頁
2025-01-09 09:23本頁面
【正文】 f(3)=1； ? g(4)={(2), (1, 1)}={f(2), f(1)+f(1)}={1, 0}， G(4)={2, 3, …} ， f(4)=2； ? g(5)={(3), (1, 2)}={f(3), f(1)+f(2)}={1, 1}， G(5)={0, 2, 3, …} ， f(5)=0； ? g(6)={(4), (1, 4), (2, 2)}={2, 1, 0}， G(6)={3, 4, …} ， f(6)=3； ? g(7)={(4), (1, 4), (2, 3)}={2, 2, 0}， G(7)={1, 3, 4, …} ， f(7)=1； ? 圖 2 所示的局面 S=(7, 3, 3)，有 S=f(7)+f(3)+f(3)=1+1+1=1，故 S 勝。 ? 游戲 C 的初始局面 S=(3, 4, 6)，有 S=1+2+3=01+10+11=0，故 S 負。 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 16 七、 結(jié)論 ? 此類搏弈游戲的一般性解法： ? 用一個 n 元組 (a1, a2, … , an)，來描述游戲過程中的一個局面。 ? 用符號 S，表示局面 S 所對應的二進制數(shù)。 ? 用符號 $(x)，表示局面 (x)的下一步所有可能出現(xiàn)的局面的集合。 ? 定義集合 g(x)：設(shè) $(x)={S1, S2, …, S k}，則 g(x)={S1, S2, …, S k}。 ? 令非負整數(shù)集為全集，集合 G(x)表示集合 g(x)的補集。 ? 定義函數(shù) f(n)： f(n)=min{G(n)}，即 f(n)等于集合 G(n)中的最小數(shù)。 ? 設(shè)局面 S=(a1, a2, … , an)， S=f(a1)+f(a2)+…+f(a n)，采用二進制數(shù)的加法。 ? 若 S≠ 0，則先行者有必勝策略；若 S=0，則后行者有必勝策略。 ? 適用范圍和限制條件： ? 甲乙兩人取石子游戲及其類似的游戲； ? 每一步只能對某一堆石子進行操作； ? 每一步操作的限制，只與這堆石子的數(shù)目或一些常數(shù)有關(guān)； ? 操作在有限步內(nèi)終止，并不會出現(xiàn)循環(huán)； ? 誰無法繼續(xù)操作，誰就是輸家。 ? 游戲 D（ POI’2022， Stripes）： ? 一排石子有 L 個，甲乙兩人輪流從中取“緊緊挨著的” A 或 B 或 C 枚石子。誰不能取了，誰就是輸家。已知 A, B, C, L，問甲乙二人誰有必勝策略。 ? 有了前面的結(jié)論，這個游戲就難不倒我們了。 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 17 八、 總結(jié) 1. 從算法優(yōu)化的角度 取石子游戲?qū)儆谝活惖湫偷牟挠螒颉８F舉所有的局面，理論上可以求得最優(yōu)策略。但窮舉的時空復雜度太高，本文所提出的解法，有效的控制了算法的時空復雜度，可以看作是對窮舉法的一個優(yōu)化。 優(yōu)化 算法的過程，可以看作是在優(yōu)化局面的表示。首先，我們用一個 n 元組表示一個局面，這是很直觀很容易想到的。因為我們只關(guān)心局面的勝負，于是得到了第一個性質(zhì)：這個 n 元組是無序的。進一步分析發(fā)現(xiàn)， n 元組中如果出現(xiàn)兩個相同的數(shù)字，則把它們消去，不影響局面的勝負。于是，我們改用集合來表示一個局面。最后，通過與二進制數(shù)的對比，又簡化到用一個數(shù)來表示一個局面。 優(yōu)化局面的表示，使得搜索量大大減少。那么，減少的搜索量都到哪里去了呢？舉個例子，對于游戲 A 中的 5 個局面： (3, 3, 1), (1, 3, 3), (5, 5, 1), (2, 3)： a. 采用 n 元組：這 5 個局面互不相同； b. 采用無序 n 元組：局面 (3, 3, 1)和 (1, 3, 3)相同； c. 采用集合：局面 (3, 3, 1), (1, 3, 3), (5, 5, 1)都相同，可以用集合 {1}表示； d. 采用二進制數(shù)： 4 個局面所對應的二進制數(shù)都是 1，故都相同。 算法的優(yōu)化，本質(zhì)上是 避免窮舉相同的局面 ，即避免重復搜索。而優(yōu)化的關(guān)鍵，就在于“ 相同局面 ”的定義。 “相同局面”的定義，必須能夠反映游戲的性質(zhì)。我們沒有簡單的按照局面的勝負，來對局面歸類，就是這個原因。 2. 從算法構(gòu)造的角度 人們認 識事物的過程中，開始只是看到了各個事物的現(xiàn)象。這就是認識的感性階段。在這個階段中， 還不能作出合乎邏輯的結(jié)論。 隨著研究的深入，這些感覺和印象的東西反復了多次，于是在人們的腦子里生起了一個認識過程中的突變 ，最后 產(chǎn)生出合乎 邏輯 的結(jié)論。 這就是認識的理性階段。 由感性認識到理性認識 —— 透析一類搏弈游戲的解答過程 張一飛 18 人們認識事物的過程，就是由感性認識上升到理性認識的過程。具體到解這類游戲，就是要 從簡單入手 。當我們遇到了一個復雜的問題，或許人人都知道從簡單入手，但卻并不是每個人都能從中得到一般性的規(guī)律。那么，我們究竟是如何 由淺入深 的呢？ 兩堆數(shù)目相等的石子 —— 這是個很簡單 的局面。我們就由此入手，將一堆石子與一個子局面相類比，并得出了兩個子局面相等時的結(jié)論。在此基礎(chǔ)上，我們研究了局面的勝負和其子局面的關(guān)系，并得出結(jié)論：可以用集合來描述一個局面。但我們并沒有停留在這一步，而是將局面的分解與二進制數(shù)的加法相類比，從而發(fā)現(xiàn)了局面與二進制數(shù)之間的關(guān)系。我們稱這個過程為“ 由此及彼 ”。 通過分析“用集合來表示一個局面”的結(jié)論，我發(fā)現(xiàn)這實質(zhì)上是簡化了局面的表示，從而聯(lián)想到能否進一步化簡，比如說用一個數(shù)來表示。在解游戲 C 時，我們并不在意它與游戲 A 的規(guī)則有多大的區(qū)別，而是注意到它與游戲 A 有著相似的性質(zhì)，從而想到用類似的方法解游戲 C。我們稱這個過程為“ 由表及里 ”。 在解游戲 A 和 B 的過程中，我們積累了很多經(jīng)驗。但在解游戲 C 時，我們卻僅僅提到了解游戲 A 和 B 的精華：構(gòu)造一個函數(shù) f。這就是“ 去粗取精 ”。 將局面與二進制數(shù)相類比，我們先試著把局面的勝負直接與二進制的 1 和 0相類比。發(fā)現(xiàn)不妥后，再將其改為與二進制數(shù)來類比。這一步叫“ 去偽存真 ”。 “ 由此及彼、由表及里 、 去粗取精、去偽存真 ” ，這就是由感性認識上升到理性認識的關(guān)鍵。
試題試卷相關(guān)推薦
鄂ICP備17016276號-1