【文章內(nèi)容簡(jiǎn)介】 其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 1. A*算法的估價(jià)函數(shù) k(ni， nj)：表示任意兩個(gè)節(jié)點(diǎn) ni和 nj之間最小代價(jià)路徑的實(shí)際代價(jià) (對(duì)于兩節(jié)點(diǎn)間沒(méi)有通路的節(jié)點(diǎn)，函數(shù) k沒(méi)有定義 )。 k(n,ti)：從節(jié)點(diǎn) n到某個(gè)具體的目標(biāo)節(jié)點(diǎn) ti，某一條最小代價(jià)路徑的代價(jià)。 h*(n)：表示整個(gè)目標(biāo)節(jié)點(diǎn)集合｛ ti｝上所有 k(n,ti)中最小的一個(gè)，因此， h*(n)就是從 n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從 n到目標(biāo)節(jié)點(diǎn)能夠獲得 h*(n)的任一路徑就是一條從 n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑 (對(duì)于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn) n，函數(shù) h*沒(méi)有定義 )。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 30/79 啟發(fā)式搜索 A*算法 定義 g* 為 g*(n)=k(S,n) 從已知起始節(jié)點(diǎn) S到任意節(jié)點(diǎn) n的一條最佳路徑代價(jià)。 定義函數(shù) f*， f*(n)=g*(n)+h*(n) 使得在任一節(jié)點(diǎn) n上其函數(shù)值 f*(n)就是從節(jié)點(diǎn) S到節(jié)點(diǎn) n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn) n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 31/79 啟發(fā)式搜索 A*算法 希望估價(jià)函數(shù) f是 f*的一個(gè)估計(jì)，此估計(jì)可由下式給出： f(n)=g(n)+h(n) 其中： g是 g*的估計(jì)； h是 h*的估計(jì)。 對(duì)于 g(n)：一個(gè)明顯的選擇就是搜索樹(shù)中從 S到 n這段路徑的代價(jià)，這一代價(jià)可以由從 n到 S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來(lái)給出 (這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價(jià)路徑 )。這個(gè)定義包含了 g(n)≥g*(n)。 h(n)：對(duì) h*(n)的估計(jì)，依賴(lài)于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息。這種信息可能與八數(shù)碼難題中的函數(shù) W(n)所用的那種信息相似。把 h叫做啟發(fā)函數(shù)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 32/79 啟發(fā)式搜索 A*算法 2. A算法和 A*算法的定義 定義 在 GRAPHSEARCH過(guò)程中，如果第 8步的重排 OPEN表是依據(jù) f(x)=g(x)+h(x) 進(jìn)行的，則稱(chēng)該過(guò)程為 A算法。 定義 在 A算法中，如果對(duì)所有的 x存在 h(x)≤h*(x),則稱(chēng) h(x)為 h*(x)的下界，它表示某種偏于保守的估計(jì)。 定義 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱(chēng)為 A*算法。當(dāng) h=0時(shí)， A*算法就變?yōu)橛行蛩阉魉惴ā? A算法和 A*搜索算法的目標(biāo)有所不同： A搜索算法雖然希望能找到問(wèn)題的最優(yōu)解，但主要追求的是求解效率；而 A*搜索算法直接目標(biāo)就在于要找到問(wèn)題的最優(yōu)解及其解的路徑，即便搜索效率有所降低也在所不惜。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 33/79 啟發(fā)式搜索 A*算法 開(kāi)始 把 S放入 OPEN表 ,記 f=h OPEN為空表？ 失敗 選取 OPEN表中未設(shè)置過(guò)的具有最小 f值 的節(jié)點(diǎn) BESTNODE，放入 CLOSED表 BESTNODE=Sg？ 成功 是 是 擴(kuò)展 BESTNODE，產(chǎn)生后繼節(jié)點(diǎn) SUVVESSOR 建立從 SUCCESSOR返回 BESTNODE的指針 計(jì)算 g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR) SUCCESSOR∈ OPEN？ 否 是 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 34/79 啟發(fā)式搜索 A*算法 把 SECCESSOR放入 OPEN表， 加入 BESTNODE的后裔表 g(SUCCESSOR)g(OLD)？ 否 重新確定 OLD的父輩節(jié)點(diǎn)為 BESTNODE， 并修正父輩節(jié)點(diǎn)的 g值和 f值，記下 g(OLD) SUCCESSOR∈ CLOSED？ 否 是 SECCESSOR=OLD，把它添到 BESTNODE的后繼節(jié)點(diǎn)表中 是 否 計(jì)算 f值 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 35/79 博弈樹(shù)搜索 博弈概述 何謂博弈？ 博弈就是下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類(lèi)競(jìng)爭(zhēng)性智能活動(dòng)。 “二人零和非偶然性全信息”博弈 （ 1）二人零和： 對(duì)壘的 MAX、 MIN雙方輪流采取行動(dòng)，博弈的結(jié)果只有三種情況： MAX方勝， MIN方勝，和局。 （ 2）全信息： 在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前格局及過(guò)去的歷史。 （ 3）非偶然性： 任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對(duì)自己最為有利而對(duì)對(duì)方最為不利的對(duì)策，不存在“碰運(yùn)氣”，“僥幸”及“偶然失誤”等隨機(jī)因素。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 36/79 博弈樹(shù)搜索 博弈概述 參加博弈的各方都希望己方取得勝利。因此，當(dāng)一方面臨多個(gè)行動(dòng)方案選擇時(shí)， 博弈的各方總是要挑選對(duì)自己最為有利而對(duì)對(duì)方最不利的那個(gè)行動(dòng)方案。 假如 MAX方的目標(biāo)： 盡可能使自己達(dá)到最大（或最高）的分?jǐn)?shù)分枝節(jié)點(diǎn)， 可用 “或” 關(guān)系來(lái)描述，稱(chēng)之為 MAX方 節(jié)點(diǎn)； 而當(dāng)輪到 MIN方行動(dòng)時(shí)， MIN方的目標(biāo)： 盡可能使 MIN方獲得最?。ɑ蜃畹停┑姆?jǐn)?shù)分枝節(jié)點(diǎn)， 這對(duì) MIN方來(lái)說(shuō)，這些行動(dòng)方案或分?jǐn)?shù)分枝節(jié)點(diǎn)之間，可以用 “與” 關(guān)系來(lái)描述，是由MIN方 自主進(jìn)行控制的，故又稱(chēng)之為 MIN節(jié)點(diǎn)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 37/79 博弈樹(shù)搜索 博弈概述 把上述雙方逐層交替的博弈過(guò)程用與 /或樹(shù)（圖）描述表達(dá)出來(lái)，就得到了一棵具有“與 /或”節(jié)點(diǎn)交替出現(xiàn)的博弈樹(shù)。 博弈樹(shù)有如下特點(diǎn)： （ 1）博弈的初始格局是初始節(jié)點(diǎn)。 （ 2）在博弈樹(shù)中，由于 雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)逐層交替出現(xiàn)。 如果自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，則對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。 （ 3）把本方獲勝的終局定義為本原問(wèn)題，相應(yīng)最優(yōu)搜索路徑上的節(jié)點(diǎn)是可解節(jié)點(diǎn)，而所有使對(duì)方獲勝的終局和屬于對(duì)方最優(yōu)搜索路徑上的節(jié)點(diǎn)則是不可解節(jié)點(diǎn)。此外，所有其它的節(jié)點(diǎn)則是具有風(fēng)險(xiǎn)的中間節(jié)點(diǎn)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 38/79 博弈樹(shù)搜索 極小極大分析法 在二人博弈過(guò)程中，最直觀而可靠的常用分析方法就是極小極大化搜索法。其主要描述思想和算法： （ 1）設(shè)博弈的一方為 MAX方，其目標(biāo)是盡可能使自己得到最高分；另一方為 MIN方 , 其目標(biāo)是盡可能給 MAX方送出最低分。所謂極小極大化分析法是一種要輪流為每一方尋找一個(gè)最優(yōu)行動(dòng)方案的方法。在圖中，方框形狀“□”表示是 MAX方控制的或節(jié)點(diǎn)；圓形框形狀“○”表示 MIN方控制與節(jié)點(diǎn)。 （ 2）考慮每一方案實(shí)施后對(duì)方可能采取的所有行動(dòng)，并為其計(jì)算可能的得分； （ 3）為計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)所有端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱(chēng)為的靜態(tài)估值。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 39/79 博弈樹(shù)搜索 （ 4）當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算父輩節(jié)點(diǎn)的等分，推算方法是：對(duì)“或”節(jié)點(diǎn)，選擇其子節(jié)點(diǎn)中最大的得分作為父輩節(jié)點(diǎn)的得分（選擇對(duì)自己最有利的方案）；對(duì)“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小的得分作為作為父輩節(jié)點(diǎn)的得分（立足于最壞的情況）。這樣計(jì)算出的父輩節(jié)點(diǎn)的等分稱(chēng)為倒推值。 （ 5）如果一個(gè)行動(dòng)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)方案。 存儲(chǔ)受限問(wèn)題：先生成一定深度的博弈樹(shù)，進(jìn)行極小極大分析，找出當(dāng)前的最好的行動(dòng)方案。然后再已選定的分支上再擴(kuò)展一定的深度，如此反復(fù)。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 40/79 4 1 1 8 1 2 5 0 4 9 1 5 11 4 3 1 –1 5 8 10 1 4 2 5 5 9 6 0 6 4 10 –9 1 12 5 MAXMIN博弈樹(shù)的倒推值計(jì)算 h(S0)=？ 4 8 2 0 1 4 1 博弈樹(shù)搜索 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 41/79 博弈樹(shù)搜索 αβ剪枝技術(shù) 基本思想：邊生成博弈樹(shù)邊估算各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)。 具體剪枝方法： （ 1） 對(duì)于一個(gè)“與”節(jié)點(diǎn) MIN，若能估計(jì)出其倒推值上界 β，并且這個(gè) β值不大于 MIN的父輩節(jié)點(diǎn)（一定是“或”節(jié)點(diǎn)）的估計(jì)倒推值的下界 α，即 α≥ β，則就不必要再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。這一過(guò)程稱(chēng)為 α剪枝。 （ 2）對(duì)于一個(gè)“或”節(jié)點(diǎn) MAX，若能估計(jì)出其倒推值下界 α ，并且這個(gè) α 值不小于 MAX的父輩節(jié)點(diǎn)（一定是“與”節(jié)點(diǎn)）的估計(jì)倒推值的上界 β ，即 α≥ β，則就不必要再擴(kuò)展該 MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了。這一過(guò)程稱(chēng)為 β 剪枝。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 42/79 博弈樹(shù)搜索 αβ剪枝技術(shù) 從算法中看到： （ 1） MAX節(jié)點(diǎn)（包括起始節(jié)點(diǎn)）的 α值永不減少。 （ 2） MIN節(jié)點(diǎn)（包括起始節(jié)點(diǎn)）的 β值永不增加。 在搜索期間， α和 β值的計(jì)算如下： （ 1）一個(gè) MAX節(jié)點(diǎn)的 α值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。 （ 2）一個(gè) MIN節(jié)點(diǎn)的 β 值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 43/79 博弈樹(shù)搜索 αβ剪枝技術(shù) 例 一字棋搜索樹(shù) α和 β值計(jì)算 估價(jià)函數(shù) g(p)定義如下： （ 1）若當(dāng)前棋局對(duì)任何一方都不是獲勝的，則 g(p)=(所有空格都放上 MAX的棋子之后 3個(gè)棋子所組成的行列及對(duì)角線的總數(shù)） — （所有空格都放上 MIN的棋子之后 3個(gè)棋子所組成的行列及對(duì)角線的總數(shù)） （ 2）若 p是 MAX獲勝，則 g(p)=+∞ （ 3）若 p是 MIN獲勝，則 g(p)=∞ 上圖中， g(p)=64=2，其中 表示 MAX方， ○表示 MIN方 ○ 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 44/79 αβ剪枝技術(shù) 博弈樹(shù)搜索 ○ ○ ○ ○ ○ ○ 初始節(jié)點(diǎn) α=1 A B C 1 β=1 65=1 55=0 65=1 55=0 45=1 56=1 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 45/79 αβ剪枝技術(shù) 博弈樹(shù)搜索 4 1 1 8 1 2 5 0 4 9 1 5 11 4 3 1 –1 5 8 10 1 4 2 5 5 9 6 0 6 4 10 –9 1