由感性認(rèn)識(shí)到理性認(rèn)識(shí)-透析一類搏弈游戲的解答過(guò)程.ppt

《由感性認(rèn)識(shí)到理性認(rèn)識(shí)-透析一類搏弈游戲的解答過(guò)程.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《由感性認(rèn)識(shí)到理性認(rèn)識(shí)-透析一類搏弈游戲的解答過(guò)程.ppt（18頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

由感性認(rèn)識(shí)到理性認(rèn)識(shí),——透析一類搏弈游戲的解答過(guò)程,認(rèn)識(shí)事物的過(guò)程,人們認(rèn)識(shí)事物，總是從簡(jiǎn)單入手。,究竟如何才能由淺入深呢？,并不是人人都能從簡(jiǎn)單的事物中得到一般性的規(guī)律。,游戲,甲乙兩人面對(duì)若干排石子。每一排石子的數(shù)目可以任意確定。兩人輪流按下列規(guī)則取走一些石子：每一步必須從某一排中取走兩枚石子；這兩枚石子必須是緊緊挨著的；如果誰(shuí)無(wú)法按規(guī)則取子，誰(shuí)就是輸家。,規(guī)則分析,如果一排有7枚石子而你取了3、4這兩枚石子，可以看作是將這一排分成了兩排，其中一排有2枚石子，另一排有3枚石子。局面的排數(shù)可能會(huì)隨著游戲的進(jìn)行而增加。,從簡(jiǎn)單入手,用一個(gè)無(wú)序多元組(a1,a2,…,an)，來(lái)描述游戲過(guò)程中的一個(gè)局面。,若初始局面可以分成兩個(gè)相同的“子局面”，則乙有必勝策略。,若先行者有必勝策略，則稱為“勝局面”。若后行者有必勝策略，則稱為“負(fù)局面”。,局面的分解,局面與集合,我們只關(guān)心局面的勝負(fù)。,(2,2,2,7,9,9),這實(shí)質(zhì)上是簡(jiǎn)化了局面的表示。能不能進(jìn)一步簡(jiǎn)化一個(gè)局面的表示呢？,一個(gè)局面可以用一個(gè)集合來(lái)描述。,類比,局面的加法勝+負(fù)=勝；負(fù)+勝=勝；負(fù)+負(fù)=負(fù)；勝+勝=不定。,二進(jìn)制數(shù)的不進(jìn)位加法：對(duì)二進(jìn)制數(shù)的每一位，采用01加法。,二進(jìn)制的01加法VS局面的加法1+0=1；勝+負(fù)=勝；0+1=1；負(fù)+勝=勝；0+0=0；負(fù)+負(fù)=負(fù)；1+1=0；勝+勝=不定。,二進(jìn)制數(shù)的加法VS局面的加法,局面的加法，與二進(jìn)制數(shù)的加法，性質(zhì)完全相同。,聯(lián)想,能否用一個(gè)二進(jìn)制數(shù)，來(lái)表示一個(gè)局面呢？,#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),用符號(hào)#S，表示局面S所對(duì)應(yīng)的二進(jìn)制數(shù)，簡(jiǎn)稱局面S的值。#S=0?S負(fù)，#S≠0?S勝。,構(gòu)造,集合g(x)：表示局面(x)，下一步可能局面的值的集合。,g(7)={#(5),#(1,4),#(2,3)},可以證明，令函數(shù)f(x)為g(x)中沒(méi)有出現(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)=min{G(x)}，滿足要求。,例子,g(7)={0,2}，G(7)={1,3,4,5,…},f(7)=min{G(7)}=min{1,3,4,5,…}=1,#(7,3,5)=f(7)+f(3)+f(5)=1+1+0=0局面(7,3,5)是負(fù)局面后走者（乙）有必勝策略,推廣,把游戲規(guī)則改變一下一次取緊緊相鄰的兩枚石子；一次取緊緊相鄰的三枚石子；一次取緊緊相鄰的任意多枚石子；一次取某一排中的任意兩枚石子，不要求緊緊相鄰；一次取某一排中的任意多枚石子，不要求緊緊相鄰；……,此類博弈游戲的特點(diǎn)甲乙兩人取石子；每一步只能對(duì)某一排石子進(jìn)行操作；每一步操作的約束，只與這排石子的數(shù)目或一些常數(shù)有關(guān)；操作在有限步內(nèi)終止，并不會(huì)出現(xiàn)循環(huán)；誰(shuí)無(wú)法繼續(xù)操作，誰(shuí)就是輸家。,此類博弈游戲的一般性解法,判斷一個(gè)局面，究竟誰(shuí)有必勝策略設(shè)局面S=(a1,a2,…,an)；S的值#S=f(a1)+…+f(an)（二進(jìn)制數(shù)的加法）；如果#S≠0，則先行者有必勝策略；如果#S=0，則后行者有必勝策略。函數(shù)f(x)的求法f(0)=0；g(x)表示局面(x)，下一步可能局面的值的集合；令G(x)為g(x)在非負(fù)整數(shù)集下的補(bǔ)集；則f(x)=min{G(x)}。,小結(jié)（一）優(yōu)點(diǎn)&缺點(diǎn),優(yōu)點(diǎn)適用范圍廣，可以直接用于大多數(shù)此類游戲與窮舉相比，速度快，時(shí)空復(fù)雜度低缺點(diǎn)另一個(gè)游戲有若干堆石子，兩人互取。無(wú)法取子者輸。一次只能在一堆中取，至少一枚，至多不限。對(duì)于這個(gè)游戲，可以證明令f(x)=x，就滿足要求。有些游戲可以直接推導(dǎo)出函數(shù)f(x)的表達(dá)式,小結(jié)（二）如何優(yōu)化算法,可以看作是對(duì)搜索算法的優(yōu)化。,無(wú)序組：(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ù)：0101010111,優(yōu)化算法的過(guò)程，可以看作是對(duì)局面的表示進(jìn)行了簡(jiǎn)化。本質(zhì)：避免了對(duì)相同局面的窮舉，即避免重復(fù)搜索。,小結(jié)（三）如何由淺入深,F(x)=min{G(x)},,由感性認(rèn)識(shí)到理性認(rèn)識(shí)的途徑,去偽存真去粗取精由此及彼由表及里,總結(jié),此類游戲的一般性解法F(x)=min{G(x)}算法優(yōu)化的本質(zhì)避免重復(fù)搜索如何由淺入深去偽存真，去粗取精由此及彼，由表及里,