算法合集之組合游戲略述——淺談sg游戲的若干拓展及變形(編輯修改稿)
2024-11-14 18:37 本頁面
【文章內(nèi)容簡(jiǎn)介】 ? 一個(gè)節(jié)點(diǎn)和兩個(gè)節(jié)點(diǎn)顯然成立； ? 假設(shè) N個(gè)節(jié)點(diǎn)時(shí)成立， ?情況一：若去掉與根節(jié)點(diǎn)相連的邊 根節(jié)點(diǎn) 中間節(jié)點(diǎn) G’ G圖 11/12/2021 石家莊二中 賈志豪 第 12頁 Cutting Edges游戲 ? 情況一：若去掉與根節(jié)點(diǎn)相連的邊 G’ 根節(jié)點(diǎn) 中間節(jié)點(diǎn) G’ 根節(jié)點(diǎn) 中間節(jié)點(diǎn) SG值為 0 11/12/2021 石家莊二中 賈志豪 第 13頁 Cutting Edges游戲 ?證明猜想 （數(shù)學(xué)歸納法） ? 以樹中節(jié)點(diǎn)個(gè)數(shù)作為階段； ? 一個(gè)節(jié)點(diǎn)和兩個(gè)節(jié)點(diǎn)顯然成立； ? 假設(shè) N個(gè)節(jié)點(diǎn)時(shí)成立， ?情況一：若去掉與根節(jié)點(diǎn)相連的邊 ?情況二：若去掉 G’ 中 的邊 11/12/2021 石家莊二中 賈志豪 第 14頁 Cutting Edges游戲 ? 情況二：若去掉 G’ 中 的邊 G’ 根節(jié)點(diǎn) 中間節(jié)點(diǎn) 根節(jié)點(diǎn) 中間節(jié)點(diǎn) G’ SG值不確定 11/12/2021 石家莊二中 賈志豪 第 15頁 Cutting Edges游戲 根節(jié)點(diǎn) G’ SG值為 0到 SG( G’ )1，取不到 SG( G’ ) 至多有 N1個(gè)點(diǎn) 根節(jié)點(diǎn) 中間節(jié)點(diǎn) G’ 至多有 N個(gè)點(diǎn) SG值為 1到 SG(G’ )， 取不到 SG(G’ )+1 ? 考慮左圖的 SG值意味著什么？？ 由歸納假設(shè) 定理： SG(G)=SG(G’)+1 11/12/2021 石家莊二中 賈志豪 第 16頁 Cutting Edges游戲 ? 更復(fù)雜的情況 G’1 G’2 G’T 根節(jié)點(diǎn) 11/12/2021 石家莊二中 賈志豪 第 17頁 Cutting Edges游戲 ?根據(jù)樹結(jié)構(gòu)的拓?fù)湫? ?試著去對(duì) G圖進(jìn)行拆分 ? 拆法一（一般樹形結(jié)構(gòu)拆法） G’1 G’2 G’T … G’1 G’2 G’T 11/12
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1