啟發(fā)式搜索與博弈

啟發(fā)式搜索與博弈學(xué)習(xí)目標(biāo)：1、了解什么是啟發(fā)式搜索；2、會(huì)用啟發(fā)式所搜算法求解問(wèn)題；3、了解博弈樹(shù)搜索算法一、啟發(fā)式搜索

1、含義：?jiǎn)l(fā)式搜索(HeuristicallySearch)又稱(chēng)為有信息搜索(InformedSearch)，它是利用問(wèn)題擁有的啟發(fā)信息來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍、降低問(wèn)題復(fù)雜度的目的，這種利用啟發(fā)信息的搜索過(guò)程稱(chēng)為啟發(fā)式搜索。一、啟發(fā)式搜索

2、特點(diǎn)：（1）大多數(shù)是深度優(yōu)先搜索的改進(jìn)；（2）在有多條路徑可走時(shí)，會(huì)給出該走哪條路徑的建議；（3）利用問(wèn)題求解的先驗(yàn)知識(shí)，使之盡快找到問(wèn)題的解；（4）可采用估值的方法進(jìn)行搜索指導(dǎo)；（5）生產(chǎn)的狀態(tài)空間小，搜索時(shí)間短且效率高、控制性好，使問(wèn)題易于得到解。

一、啟發(fā)式搜索

3、類(lèi)型，按其用途可以分為以下三類(lèi)：（1）有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息；（2）有效地幫助確定后繼節(jié)點(diǎn)生成的信息；（3）有效地幫助確定節(jié)點(diǎn)刪除的信息。

一、啟發(fā)式搜索

4、估價(jià)函數(shù)：

估價(jià)函數(shù)是用來(lái)估價(jià)節(jié)點(diǎn)重要性程度的函數(shù)。其一般形式是：f(n)=g(n)+h(n)二、如何進(jìn)行啟發(fā)式搜索

1、啟發(fā)式搜索的一般搜索流程三、博弈問(wèn)題中的啟發(fā)式搜索

1、什么是博弈樹(shù)

博弈樹(shù)是指由于動(dòng)態(tài)博弈參與者的行動(dòng)有先后次序，因此可以依次將參與者的行動(dòng)展開(kāi)成一個(gè)樹(shù)狀圖形。[1]博弈樹(shù)是擴(kuò)展型的一種形象化表述。它能給出有限博弈的幾乎所有信息。其基本構(gòu)建材料包括結(jié)、枝和信息集。結(jié)包括決策結(jié)和終點(diǎn)結(jié)兩類(lèi)；決策結(jié)是參與人采取行動(dòng)的時(shí)點(diǎn)，終點(diǎn)結(jié)是博弈行動(dòng)路徑的終點(diǎn)。枝是從一個(gè)決策結(jié)到它的直接后續(xù)結(jié)的連線(有時(shí)用箭頭表述)，每一個(gè)枝代表參與人的一個(gè)行動(dòng)選擇。博弈樹(shù)上的所有決策結(jié)分割成不同的信息集。每一個(gè)信息集是決策集集合的一個(gè)子集，該子集包括所有滿足下列條件的決策結(jié)：(1)每一個(gè)決策結(jié)都是同一參與人的決策結(jié)；(2)該參與人知道博弈進(jìn)入該集合的某個(gè)決策結(jié)，但不知道自己究竟處于哪一個(gè)決策結(jié)。三、博弈問(wèn)題中的啟發(fā)式搜索

2、基本特點(diǎn)

(1)

博弈的初始格局是初始節(jié)點(diǎn)。

(2)在博弈樹(shù)中，"或"節(jié)點(diǎn)和"與"節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是"或"關(guān)系，對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是"與"關(guān)系。雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)。

(3)所有自己一方獲勝的終局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終局都認(rèn)為是不可解節(jié)點(diǎn)。三、博弈問(wèn)題中的啟發(fā)式搜索

3、極大極小分析法，其基本思想：

(1)

設(shè)博弈雙方分別為A和B，然后為其中一方尋找一個(gè)最優(yōu)行動(dòng)方案；

（2）為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的結(jié)果進(jìn)行比較，并計(jì)算可能的得分；

（3）為了計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分；

（4）當(dāng)端