算法合集之由感性認(rèn)識(shí)到理性認(rèn)識(shí)——透析一類(lèi)搏弈游戲的解答過(guò)程-閱讀頁(yè)
2025-01-24 09:23本頁(yè)面
【正文】 … +f(an)。 ? 游戲 A 中， f(x) = x。 ? 游戲 C 中， f(x) = ?。 ? 回憶關(guān)于游戲 A、 B 的結(jié)論的證明過(guò)程 ? 函數(shù) f 是否滿(mǎn)足要求，關(guān)鍵在于 S 是否滿(mǎn)足下面的條件。 ? 若 S≠ 0，則先行者必然存在一種取子方法 S→T ，且 T=0。 ? 在游戲 A 中， $(3)={(2), (1), (0)}。 ? 在游戲 C 中， $(7)={(5), (1, 4), (2, 3)}。 ? 在游戲 A 中， $(3)={(2), (1), (0)}，故 g(3)={(2), (1), (0)}={10, 01, 00}。 ? 在游戲 C 中， g(7)={(5), (1, 4), (2, 3)}。 ? 設(shè) S=(a1, a2, …, a n)，由于先行者只能選擇一堆石子，不妨設(shè)選擇了 a1； ? 因?yàn)?S=f(a1)+(a2, …, a n)=0，所以 f(a1)=(a2, …, a n)； ? 先行者可能將局面 (a1)變?yōu)榫置?(b1, …, b m)， (b1, …, b m)屬于集合 g(a1)； ? 設(shè)這時(shí)的局面為 T，我們有 T=(b1, …, b m)+(a2, …, a n)； ? T=(b1, …, b m)+(a2, …, a n)=(b1, …, b m)+f(a1)； ? 如果要求 T≠ 0，則必然有 (b1, …, b m)≠ f(a1)； ? 因此，函數(shù) f(a1)的值，不屬于集合 g(a1)。 ? 設(shè) S=(a1, a2, … , an)， p=S=f(a1)+f(a2)+… +f(an)； ? 因?yàn)?p≠ 0，所以必然存在 k，使得 f(ak)+pf(ak)，不妨設(shè) k=1， f(a1)+p=x； ? 因?yàn)?p=S=f(a1)+(a2, …, a n)，故 (a2, …, a n)=p+f(a1)=x； ? 如果先行者把局面 (a1)變?yōu)榫置?(b1, …, b m)， (b1, …, b m)屬于集合 g(a1)； ? 設(shè)這時(shí)的局面為 T，我們有 T=(b1, …, b m)+(a2, …, a n)； ? T=(b1, …, b m)+(a2, …, a n)=(b1, …, b m)+x； ? 如果要使 T=0，相當(dāng)于要找到 (b1, …, b m)，使得 (b1, …, b m)等于 x； ? 如果可以保證 x 屬于集合 g(a1)，則肯定可以找到相應(yīng)的的 (b1, …, b m)； ? 因?yàn)?xf(a1)，所以， x 屬于集合 {0, 1, …, f(a 1)–1}； ? 如果集合 g(a1)包含集合 {0, 1, …, f(a 1)–1}，則 x 一定屬于 g(a1)。 ? 集合 g(a1)包含集合 {0, 1, …, f(a 1)–1}。 ? 用大寫(xiě)字母 N 表示非負(fù)整數(shù)集，即 N={0, 1, 2, …} 。 ? 定義函數(shù) f(n)： f(n)=min{G(n)}，即 f(n)等于集合 G(n)中的最小數(shù)。 ? 若 S=0，則 S 負(fù)；若 S≠ 0，則 S 勝。 ? 游戲 C 的初始局面 S=(3, 4, 6)，有 S=1+2+3=01+10+11=0，故 S 負(fù)。 ? 用符號(hào) S，表示局面 S 所對(duì)應(yīng)的二進(jìn)制數(shù)。 ? 定義集合 g(x)：設(shè) $(x)={S1, S2, …, S k}，則 g(x)={S1, S2, …, S k}。 ? 定義函數(shù) f(n)： f(n)=min{G(n)}，即 f(n)等于集合 G(n)中的最小數(shù)。 ? 若 S≠ 0，則先行者有必勝策略；若 S=0，則后行者有必勝策略。 ? 游戲 D（ POI’2022， Stripes）： ? 一排石子有 L 個(gè)，甲乙兩人輪流從中取“緊緊挨著的” A 或 B 或 C 枚石子。已知 A, B, C, L，問(wèn)甲乙二人誰(shuí)有必勝策略。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類(lèi)搏弈游戲的解答過(guò)程 張一飛 17 八、 總結(jié) 1. 從算法優(yōu)化的角度 取石子游戲?qū)儆谝活?lèi)典型的搏弈游戲。但窮舉的時(shí)空復(fù)雜度太高，本文所提出的解法，有效的控制了算法的時(shí)空復(fù)雜度，可以看作是對(duì)窮舉法的一個(gè)優(yōu)化。首先，我們用一個(gè) n 元組表示一個(gè)局面，這是很直觀很容易想到的。進(jìn)一步分析發(fā)現(xiàn)， n 元組中如果出現(xiàn)兩個(gè)相同的數(shù)字，則把它們消去，不影響局面的勝負(fù)。最后，通過(guò)與二進(jìn)制數(shù)的對(duì)比，又簡(jiǎn)化到用一個(gè)數(shù)來(lái)表示一個(gè)局面。那么，減少的搜索量都到哪里去了呢？舉個(gè)例子，對(duì)于游戲 A 中的 5 個(gè)局面： (3, 3, 1), (1, 3, 3), (5, 5, 1), (2, 3)： a. 采用 n 元組：這 5 個(gè)局面互不相同； b. 采用無(wú)序 n 元組：局面 (3, 3, 1)和 (1, 3, 3)相同； c. 采用集合：局面 (3, 3, 1), (1, 3, 3), (5, 5, 1)都相同，可以用集合 {1}表示； d. 采用二進(jìn)制數(shù)： 4 個(gè)局面所對(duì)應(yīng)的二進(jìn)制數(shù)都是 1，故都相同。而優(yōu)化的關(guān)鍵，就在于“ 相同局面 ”的定義。我們沒(méi)有簡(jiǎn)單的按照局面的勝負(fù)，來(lái)對(duì)局面歸類(lèi)，就是這個(gè)原因。這就是認(rèn)識(shí)的感性階段。 隨著研究的深入，這些感覺(jué)和印象的東西反復(fù)了多次，于是在人們的腦子里生起了一個(gè)認(rèn)識(shí)過(guò)程中的突變 ，最后 產(chǎn)生出合乎 邏輯 的結(jié)論。 由感性認(rèn)識(shí)到理性認(rèn)識(shí) —— 透析一類(lèi)搏弈游戲的解答過(guò)程 張一飛 18 人們認(rèn)識(shí)事物的過(guò)程，就是由感性認(rèn)識(shí)上升到理性認(rèn)識(shí)的過(guò)程。當(dāng)我們遇到了一個(gè)復(fù)雜的問(wèn)題，或許人人都知道從簡(jiǎn)單入手，但卻并不是每個(gè)人都能從中得到一般性的規(guī)律。我們就由此入手，將一堆石子與一個(gè)子局面相類(lèi)比，并得出了兩個(gè)子局面相等時(shí)的結(jié)論。但我們并沒(méi)有停留在這一步，而是將局面的分解與二進(jìn)制數(shù)的加法相類(lèi)比，從而發(fā)現(xiàn)了局面與二進(jìn)制數(shù)之間的關(guān)系。 通過(guò)分析“用集合來(lái)表示一個(gè)局面”的結(jié)論，我發(fā)現(xiàn)這實(shí)質(zhì)上是簡(jiǎn)化了局面的表示，從而聯(lián)想到能否進(jìn)一步化簡(jiǎn)，比如說(shuō)用一個(gè)數(shù)來(lái)表示。我們稱(chēng)這個(gè)過(guò)程為“ 由表及里 ”。但在解游戲 C 時(shí)，我們卻僅僅提到了解游戲 A 和 B 的精華：構(gòu)造一個(gè)函數(shù) f。 將局面與二進(jìn)制數(shù)相類(lèi)比，我們先試著把局面的勝負(fù)直接與二進(jìn)制的 1 和 0相類(lèi)比。這一步叫“ 去偽存真 ”。
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1