算法合集之組合游戲略述——淺談sg游戲的若干拓展及變形(編輯修改稿)
2024-11-14 18:37 本頁面
【文章內(nèi)容簡介】 ? 一個節(jié)點和兩個節(jié)點顯然成立； ? 假設(shè) N個節(jié)點時成立， ?情況一：若去掉與根節(jié)點相連的邊 根節(jié)點 中間節(jié)點 G’ G圖 11/12/2021 石家莊二中 賈志豪 第 12頁 Cutting Edges游戲 ? 情況一：若去掉與根節(jié)點相連的邊 G’ 根節(jié)點 中間節(jié)點 G’ 根節(jié)點 中間節(jié)點 SG值為 0 11/12/2021 石家莊二中 賈志豪 第 13頁 Cutting Edges游戲 ?證明猜想 （數(shù)學(xué)歸納法） ? 以樹中節(jié)點個數(shù)作為階段； ? 一個節(jié)點和兩個節(jié)點顯然成立； ? 假設(shè) N個節(jié)點時成立， ?情況一：若去掉與根節(jié)點相連的邊 ?情況二：若去掉 G’ 中 的邊 11/12/2021 石家莊二中 賈志豪 第 14頁 Cutting Edges游戲 ? 情況二：若去掉 G’ 中 的邊 G’ 根節(jié)點 中間節(jié)點 根節(jié)點 中間節(jié)點 G’ SG值不確定 11/12/2021 石家莊二中 賈志豪 第 15頁 Cutting Edges游戲 根節(jié)點 G’ SG值為 0到 SG( G’ )1，取不到 SG( G’ ) 至多有 N1個點 根節(jié)點 中間節(jié)點 G’ 至多有 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é)點 11/12/2021 石家莊二中 賈志豪 第 17頁 Cutting Edges游戲 ?根據(jù)樹結(jié)構(gòu)的拓?fù)湫? ?試著去對 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號-1