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