博弈論：組合博弈
* 必?cái)↑c(diǎn)(P點(diǎn)) :前一個(gè)選手(Previous player)將取勝的位置稱為必?cái)↑c(diǎn)。
* 必勝點(diǎn)(N點(diǎn)) :下一個(gè)選手(Next player)將取勝的位置稱為必勝點(diǎn)。
* 必?cái)?#xff08;必勝）點(diǎn)的屬性：
* (1) 所有終結(jié)點(diǎn)是必?cái)↑c(diǎn)（P點(diǎn)）；
* (2) 從任何必勝點(diǎn)（N點(diǎn)）操作，至少有一種方法可以進(jìn)入必?cái)↑c(diǎn)（P點(diǎn)）；
* (3)無論如何操作， 從必?cái)↑c(diǎn)（P點(diǎn)）都只能進(jìn)入必勝點(diǎn)（N點(diǎn)）.
* 由上面的屬性得到該題的算法：
* 步驟1:將所有終結(jié)位置標(biāo)記為必?cái)↑c(diǎn)（P點(diǎn)）；
* 步驟2: 將所有一步操作能進(jìn)入必?cái)↑c(diǎn)（P點(diǎn)）的位置標(biāo)記為必勝點(diǎn)（N點(diǎn)）
* 步驟3:如果從某個(gè)點(diǎn)開始的所有一步操作都只能進(jìn)入必勝點(diǎn)（N點(diǎn)） ，則將該點(diǎn)標(biāo)記為必?cái)↑c(diǎn)（P點(diǎn)） ；
* 步驟4: 如果在步驟3未能找到新的必?cái)?#xff08;P點(diǎn)），則算法終止；否則，返回到步驟2。

關(guān)于博弈問題，較為常用的是P/N圖分析法
??????????
??p?n?p?n?p?n?p?n
??n ?n?n?n?n?n?n?n
??p?n?p?n?p?n?p?n
??n ?n?n?n?n?n?n?n
??p?n?p?n?p?n?p?n
??n ?n?n?n?n?n?n?n
??p?n?p?n?p?n?p?n

實(shí)際上就是按照規(guī)則畫圖；有以下三條規(guī)則：
number one ：每個(gè)圖的末狀態(tài)均為必?cái)↑c(diǎn)P
number two： 所有能夠一步到達(dá)必?cái)↑c(diǎn)的都是必勝點(diǎn)N
number three: 所有能夠一步到達(dá)必勝點(diǎn)的都是必?cái)↑c(diǎn) P
畫圖的時(shí)候，選定對(duì)角線定點(diǎn)里面的那個(gè)點(diǎn)位末狀態(tài)，題上的說明，那么一般找的規(guī)則就是從最底邊上，還有最開始的那一列開始確定P還是N點(diǎn)，這樣很方便的看出，當(dāng)行列都是奇數(shù)的時(shí)候，那么一定會(huì)必?cái)↑c(diǎn)。

轉(zhuǎn)自https://blog.csdn.net/Adusts/article/details/81385588

總結(jié)

以上是生活随笔為你收集整理的算法总结 -- 博弈论（PN图）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。