【文章內(nèi)容簡介】 DBECFGS34445 543搜索樹（非循環(huán)路徑）2SA DB D EAC E E B B FD F B F C E A C GG C G FG33 333222444444444444555 555等代價搜索算法SA DB D A EE B B FB F C E A C GGG FC3 44 555 25 433 47 8 9 61011C ED FG4 511 12 13 13134 在每一步 , 選擇具有最低累計權(quán)值的點進行擴展啟發(fā)式搜索n 盲目搜索的問題： “組合爆炸 ”n 利用問題的某些控制信息 (如解的特征 )來引導搜索 .這種控制信息稱為搜索的 啟發(fā)信息 .n 利用啟發(fā)式信息定義節(jié)點的 啟發(fā)函數(shù) h(n)n 特點 : 深度優(yōu)先 , 效率高 , 無回溯 , 但不能保證得到最佳解 。n 探索算法 :n 全局擇優(yōu)搜索 (最好優(yōu)先搜索 ), 局部擇優(yōu)搜索n 數(shù)據(jù)結(jié)構(gòu)： OPEN表 、 CLOSED表 啟發(fā)信息n 啟發(fā)式搜索就是利用啟發(fā)性信息進行制導的搜索。n 啟發(fā)性信息就是有利于盡快找到問題之解的信息。n 按其用途劃分，啟發(fā)性信息一般可分為以下三類： (1)用于擴展節(jié)點的選擇 ，即用于決定應先擴展哪一個節(jié)點，以免盲目擴展。 (2)用于生成節(jié)點的選擇 ，即用于決定應生成哪些后續(xù)節(jié)點，以免盲目地生成過多無用節(jié)點。 (3)用于刪除節(jié)點的選擇 ，即用于決定應刪除哪些無用節(jié)點，以免造成進一步的時空浪費。n 重排 OPEN表，使搜索沿某個被認為最有希望的路徑擴展。n 應用這種排序過程，需要某些估算節(jié)點 “希望 ”的量度。n 用來估算節(jié)點希望程度的量度，叫做 估價函數(shù)（ evaluation function），有時也叫作啟發(fā)函數(shù) 。n 一個節(jié)點的 “希望 ”（ promise）有幾種不同 的定義方法。n 在狀態(tài)空間問題中，一種方法是估算目標節(jié)點到此節(jié)點的距離；n 估算全路徑的長度或難度（包括此節(jié)點）。n 我們用符號 f來標記估價函數(shù)，用 f（ n） 表示節(jié)點 n的估價函數(shù)值。啟發(fā)函數(shù)n 如何定義一個估價（啟發(fā)）函數(shù)呢？估價（啟發(fā)）函數(shù)并無固定的模式，需要具體問題具體分析。通?？梢詤⒖嫉乃悸酚校? （ 1） 一個節(jié)點到目標節(jié)點的距離或差異的度量； （ 2）一個節(jié)點處在最佳路徑上的概率； （ 3）或者根據(jù)經(jīng)驗的主觀打分。 啟發(fā)函數(shù)八數(shù)碼難題（ 8puzzle）f1(T) = 恰好正確地處在目標狀態(tài)的字碼數(shù)目 :1 3 247658f1 = 4從實用角度，計算與目標的距離更有實際意義！從實用角度，計算與目標的距離更有實際意義！f2 = 41 3 247658f2(T) =沒有處在目標狀態(tài)的字碼數(shù)目（相當于粗略地給出了當前狀態(tài)與目標的距離）1 2 38 47 6 5目標：f3(T) = 不在目標位置的字碼距離目標位置水平距離和垂直距離之和。– 該函數(shù)給出了一個更好的距離評估f2 = 1 + 1 + 2 + 2 = 61 3 2476581 2 38 47 6 5目標： 啟發(fā)式搜索算法n n 啟發(fā)式搜索要用啟發(fā)函數(shù)來導航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎上再增加啟發(fā)函數(shù)值的計算與傳播過程，并且由啟發(fā)函數(shù)值來確定節(jié)點的擴展順序。兩種策略 : n 局部擇優(yōu)搜索 擴展節(jié)點 N后僅對 N的子節(jié)點按啟發(fā)函數(shù)值大小以升序排序，再將它們依次放入 OPEN表的 首部。n 全局擇優(yōu)搜索 在 OPEN表中保留所有已生成而未考察的節(jié)點，并用啟發(fā)函數(shù)h(x)對它們?nèi)窟M行估價，從中選出最優(yōu)節(jié)點進行擴展，而不管這個節(jié)點出現(xiàn)在搜索樹的什么地方。全局擇優(yōu)搜索算法n Step1: 把初始節(jié)點 S0放入 OPEN表中 ,計算 h(S0)。n Step2: 若 OPEN表為空 ,則搜索失敗 ,退出 .n Step3: 移出 OPEN中第一個節(jié)點 N放入 CLOSED表 中 , 并標以順序編號 n。n Step4: 若目標節(jié)點 Sg=N, 則搜索成功 ,結(jié)束 .n Step5: 若 N不可擴展 , 則轉(zhuǎn) Step2。n Step6: 擴展 N,計算每個子節(jié)點的函數(shù)值 h(x),將所有子節(jié)點配上指向 N的返回指針后放入 OPEN表中 , 再 按函數(shù)值的升序重新排序 OPEN表中的節(jié)點 , 轉(zhuǎn) Step2。全局擇優(yōu)搜索例子n 九宮重排問題 , 定義評價函數(shù) 。 h(n):目標格局與現(xiàn)格局 (Sn)相比 ,位置不同的牌數(shù). 初始格局 S0 目標格局 Sg 2 8 3 1 2 3 1 4 === 8 4 7 6 5 7 6 5h(S0) = 3局部擇優(yōu)搜索算法n Step1: 把初始節(jié)點 S0放入 OPEN表中 ,計算 h(S0)。n Step2: 若 OPEN表為空 ,則搜索失敗 ,退出 .n Step3: 移出 OPEN中第一個節(jié)點 N放入 CLOSED表 中 , 并標以順序編號 n。n Step4: 若目標節(jié)點 Sg=N, 則搜索成功 ,結(jié)束 .n Step5: 若 N不可擴展 , 則轉(zhuǎn) Step2。n Step6: 擴展 N,計算每個子節(jié)點的函數(shù)值 h(x),并將所有子節(jié)點按 函數(shù)值的升序排序后 , 配上指向 N的返回指針放入OPEN表的首部 , 轉(zhuǎn) Step2。局部搜索算法n 特點： 從單獨的一個當前狀態(tài)出發(fā)，通常只移動到與之相鄰的狀態(tài)，并且不保留解的路徑。n 優(yōu)點 ：n 需要很少的內(nèi)存n 經(jīng)常能在很大或無限的狀態(tài)空間中找到合理的解爬山法（ Hill climbing）n 一種基本的局部啟發(fā)式搜索方法n 基本算法：擴展節(jié)點 N后僅對 N的子節(jié)點按啟發(fā)函數(shù)值大小以升序排序，再將選擇啟發(fā)函數(shù)值 最小的節(jié)點 放入 OPEN表的首部。（ 啟發(fā)函數(shù)值越小離目標越近 ）n 相當于深度優(yōu)先算法 +啟發(fā)式搜索n 線式搜索 ，不能回溯n 向目標值增加的方向持續(xù)移動啟發(fā)式搜索 :A算法n 評價函數(shù) f(x) = g(x) + h(x)，表示通過節(jié)點 x的估計代價值。nmSGg(n)g(m)h(n)h(m)比較 f(n)和 f(m) 大小，決定節(jié)點搜索順序，即在 OPEN表中的順序啟發(fā)式搜索 :A算法n 評價函數(shù) f(x) = g(x) + h(x) n 當 f(x) = g(x) 時， 為寬度優(yōu)先搜索n 當 f(x) = 1/g(x)時， 為深度優(yōu)先搜索n 當 f(x) = h(x) 時， 為全局優(yōu)先搜索nmSGg(n)g(m)h(n)h(m)啟發(fā)式搜索 :A算法n 評價函數(shù)的一般形式 : f(n) = g(n) + h(n)g(n):從 S0到 Sn的實際代價 (搜索的橫向因子 )h(n):從 N到目標節(jié)點的估計代價 ,稱為 啟發(fā)函數(shù) (搜索的縱向因子 )。n 特點 : 效率高 , 無回溯 , n 搜索算法OPEN表 : 存放待擴展的節(jié)點 . CLOSED表 : 存放已被擴展過的節(jié)點 .啟發(fā)式搜索 :A算法n Step1: 把附有計算 f(S0)初始節(jié)點 S0放入 OPEN表中 。n Step2: 若 OPEN表為空 ,則搜索失敗 ,退出 .n Step3: 移出 OPEN中第一個節(jié)點 N放入 CLOSED表中 , 并標以順序編號 n。n Step4: 若目標節(jié)點 Sg=N, 則搜索成功 ,結(jié)束 .n Step5: 若 N不可擴展 , 則轉(zhuǎn) Step2。n Step6: 擴展 N, 生成一組附有 f(x)的子節(jié)點 ,作完以下處理后 ,將余下子節(jié)點配上指向 N的返回指針后放入 OPEN表中 , 再 按函數(shù)值的升序重新排序 OPEN表中的節(jié)點 , 轉(zhuǎn) Step2。n 刪除重復節(jié)點和修改返回指針 .八數(shù)碼難題（ 8puzzle problem）1 2 38 4567（目標狀態(tài)）12 384567（初始狀態(tài)）A算法的應用八數(shù)碼難題 :評價函數(shù) n 簡單的評價函數(shù) h(n)=d(n)+W(n)n 其中： d(n)是搜索樹中節(jié)點 n的深度； W(n)用來計算對應于節(jié)點 n的數(shù)據(jù)庫中錯放的棋子個數(shù)。 初始棋局初始棋局 f值等于值等于 0+4=4 12 384567（初始狀態(tài)）57234512 38456712 38456712 3845671+31+5 1+5112 38 456712 38456712 3845672+42+3 2+312 38 456712 38 45673+2 3+412 38 4567123845673+3 3+41 2 38 45674+181 3245671 2 38 45675+0 5+2八數(shù)碼難題的搜索樹12 38460+4 5啟發(fā)式搜索 :A*算法n 評價函數(shù)的一般形式