由感性認(rèn)識到理性認(rèn)識.ppt

1、由感性認(rèn)識到理性認(rèn)識,透析一類搏弈游戲的解答過程,認(rèn)識事物的過程,人們認(rèn)識事物，總是從簡單入手。,究竟如何才能由淺入深呢？,并不是人人都能從簡單的事物中得到一般性的規(guī)律。,游戲,甲乙兩人面對若干排石子。 每一排石子的數(shù)目可以任意確定。 兩人輪流按下列規(guī)則取走一些石子： 每一步必須從某一排中取走兩枚石子； 這兩枚石子必須是緊緊挨著的； 如果誰無法按規(guī)則取子，誰就是輸家。,規(guī)則分析,如果一排有7枚石子 而你取了3、4這兩枚石子， 可以看作是將這一排分成了兩排， 其中一排有2枚石子，另一排有3枚石子。 局面的排數(shù)可能會隨著游戲的進(jìn)行而增加。,從簡單入手,用一個無序多元組(a1, a2, , an)，

2、來描述游戲過程中的一個局面。,若初始局面可以分成兩個相同的“子局面”，則乙有必勝策略。,若先行者有必勝策略，則稱為“勝局面”。 若后行者有必勝策略，則稱為“負(fù)局面”。,局面的分解,局面與集合,我們只關(guān)心局面的勝負(fù)。,(2, 2, 2, 7, 9, 9),這實(shí)質(zhì)上是簡化了局面的表示。 能不能進(jìn)一步簡化一個局面的表示呢？,一個局面可以用一個集合來描述。,類比,局面的加法 勝+負(fù)=勝； 負(fù)+勝=勝； 負(fù)+負(fù)=負(fù)； 勝+勝=不定。,二進(jìn)制數(shù)的不進(jìn)位加法：對二進(jìn)制數(shù)的每一位，采用01加法。,二進(jìn)制的01加法 VS 局面的加法 1 + 0 = 1；勝+負(fù)=勝； 0 + 1 = 1；負(fù)+勝=勝； 0 + 0

3、 = 0；負(fù)+負(fù)=負(fù)； 1 + 1 = 0；勝+勝=不定。,二進(jìn)制數(shù)的加法 VS 局面的加法,局面的加法，與二進(jìn)制數(shù)的加法，性質(zhì)完全相同。,聯(lián)想,能否用一個二進(jìn)制數(shù)，來表示一個局面呢？,#S=#(a1, , an)=f(a1)+f(an)。 關(guān)鍵就在于函數(shù)f(x)的構(gòu)造。,#(3, 3)=#(3)+#(3),#(3, 3, 1)=#(3)+#(3)+#(1),#(3, 3, 1)=f(3)+f(3)+f(1),用符號#S，表示局面S所對應(yīng)的二進(jìn)制數(shù)，簡稱局面S的值。 #S=0S負(fù)， #S0S勝。,構(gòu)造,集合 g(x)：表示局面(x)，下一步可能局面的值的集合。,g(7)=#(5), #(1,

4、4), #(2, 3),可以證明，令函數(shù)f(x)為g(x)中沒有出現(xiàn)的最小非負(fù)整數(shù)，滿足要求。 如果g(x)=0, 1, 2, 5, 7, 8, 9，則f(x)=3。 令G(x)為g(x)在非負(fù)整數(shù)集下的補(bǔ)集。 令f(x)=minG(x)，滿足要求。,例子,g(7)=0, 2，G(7)=1, 3, 4, 5, ,f(7)=minG(7)=min1, 3, 4, 5, =1,#(7, 3, 5)=f(7)+f(3)+f(5)=1+1+0=0 局面(7, 3, 5)是負(fù)局面 后走者（乙）有必勝策略,推廣,把游戲規(guī)則改變一下 一次取緊緊相鄰的兩枚石子； 一次取緊緊相鄰的三枚石子； 一次取緊緊相鄰的任

5、意多枚石子； 一次取某一排中的任意兩枚石子，不要求緊緊相鄰； 一次取某一排中的任意多枚石子，不要求緊緊相鄰； ,此類博弈游戲的特點(diǎn) 甲乙兩人取石子； 每一步只能對某一排石子進(jìn)行操作； 每一步操作的約束，只與這排石子的數(shù)目或一些常數(shù)有關(guān)； 操作在有限步內(nèi)終止，并不會出現(xiàn)循環(huán)； 誰無法繼續(xù)操作，誰就是輸家。,此類博弈游戲的一般性解法,判斷一個局面，究竟誰有必勝策略 設(shè)局面S=(a1, a2, , an)； S的值#S=f(a1)+f(an)（二進(jìn)制數(shù)的加法）； 如果#S0，則先行者有必勝策略； 如果#S=0，則后行者有必勝策略。 函數(shù)f(x)的求法 f(0)=0； g(x)表示局面(x)，下一步可

6、能局面的值的集合； 令G(x)為g(x)在非負(fù)整數(shù)集下的補(bǔ)集； 則f(x)=minG(x)。,小結(jié)（一）優(yōu)點(diǎn) & 缺點(diǎn),優(yōu)點(diǎn) 適用范圍廣，可以直接用于大多數(shù)此類游戲 與窮舉相比，速度快，時空復(fù)雜度低 缺點(diǎn) 另一個游戲 有若干堆石子，兩人互取。無法取子者輸。 一次只能在一堆中取，至少一枚，至多不限。 對于這個游戲，可以證明令f(x)=x，就滿足要求。 有些游戲可以直接推導(dǎo)出函數(shù)f(x)的表達(dá)式,小結(jié)（二）如何優(yōu)化算法,可以看作是對搜索算法的優(yōu)化。,無序組：(2, 5, 5) (5, 2, 5) (2, 3, 3) (2, 3, 4, 6) (3, 4),集合： 2 2 2 2, 3, 4, 6 3, 4,二進(jìn)制數(shù)： 01 01 01 01 11,優(yōu)化算法的過程，可以看作是對局面的表示進(jìn)行了簡化。 本質(zhì)：避免了對相同局面的窮舉，即避免重復(fù)搜索。,小結(jié)（三）如何由淺入深,F(x)=minG(x),由感性