【正文】 2022/8/21 106 啟發(fā)式搜索 ——（ 掌握 ） A算法實例 ——八數(shù)碼游戲 ? 1)設(shè)計評價函數(shù) f(n) ? f(n)=d(n)+w(n),其中 ? d(n)節(jié)點 n在搜索圖中的 節(jié)點深度 ，對 g(n)的度量 ； ? w(n)代表啟發(fā)式函數(shù) h(n),其值是節(jié)點 n與目標狀態(tài)節(jié)點ng相比較，不考慮空格， 錯位的棋牌個數(shù) ； 初始布局 目標布局 移動數(shù)碼 56748321586427312022/8/21 107 啟發(fā)式搜索 ——（ 掌握 ） 啟發(fā)式算法 A實例 ——八數(shù)碼游戲 ? 1)設(shè)計評價函數(shù) f(n) ? f(n)計算實例 ?初始布局 s 目標布局 ng 5674832。 f(n)排序 OPEN表中的節(jié)點， f(n)值最小者排在首位 ，重排 OPEN表； 2。若 f(n,ni) f(ni)點 ,則令 f(ni) = f(n,ni),并移動子節(jié)點指向老父節(jié)點的指針，改為指向新父節(jié)點。把 M的這些成員加進 OPEN表。 2022/8/21 102 啟發(fā)式搜索 ——（ 掌握 ） ? 算法 A的設(shè)計與一般圖搜索類似，劃分為二個階段： ? 初始化 ? 搜索循環(huán) ? MOVEFIRST(OPEN)取出 OPEN表首的節(jié)點 n ? ⑥ 擴展出 n的子節(jié)點 ,插入搜索圖 G和 OPEN表 ? 對每個子節(jié)點 ni,計算 f(n,ni)=g(n,ni)+h(ni) ? ⑦ 適當(dāng)?shù)臉擞浐托薷闹羔?（ 子節(jié)點 ?父節(jié)點 ） ? ⑧ 排序 OPEN表 （評價函數(shù) f(n)的值排序） 2022/8/21 103 啟發(fā)式搜索 ——（ 掌握 ） ? ⑥ 擴展出 n的子節(jié)點 ,插入搜索圖 G和 OPEN表 ? 對每個子節(jié)點 ni,計算 f(n,ni)=g(n,ni)+h(ni) ? ⑦ 適當(dāng)?shù)臉擞浐托薷闹羔?（ 子節(jié)點 ?父節(jié)點 ） ? (i)全新節(jié)點： f(ni)=f(n,ni) ? (ii)已出現(xiàn)在 OPEN表 中的節(jié)點 ? (iii)已出現(xiàn)的 CLOSE表 中的節(jié)點 ? IF f(ni)f(n,ni) THEN ? 修改指針指向 新 父結(jié)點 n ? f(ni)=f(n,ni) ? ⑧ 排序 OPEN表 （ f(n)值從小到大排序） 2022/8/21 104 OPEN表是空表，則失敗退出 ； 算法 A OPEN表上的第一個節(jié)點，把它從 OPEN表移出并放進 CLOSE表中，稱此節(jié)點為節(jié)點 n； 只包含起始節(jié)點 S的搜索圖 G,把 S放到一個叫 OPEN的未擴展節(jié)點表中；建立一個叫做CLOSE的已擴展節(jié)點表，其初始為空表； n，同時生成不是 n的祖先的那些子節(jié)點的集合 M,把 M的這些成員作為 n的后繼節(jié)點添入圖 G中； 對于 M中每個子節(jié)點 ni,計算 f(n,ni) = g(n,ni) + h(ni)。 ?A算法， A*算法（掌握?。? ? 局部排序 ——僅對 新 擴展出來的子節(jié)點排序 ，使這些 新 節(jié)點中 最有希望 者能優(yōu)先取出考察和擴展； ?爬山法（了解， 對 深度優(yōu)先法 的改進 ）； 2022/8/21 98 啟發(fā)式搜索 ——（ 掌握 ） ? 【 基本思想 】 ? 設(shè)計體現(xiàn)啟發(fā)式知識的 評價函數(shù) f(n)； ? 指導(dǎo) 一般圖搜索 中 OPEN表待擴展節(jié)點的排序 ： ? 【 評價函數(shù) f(n)=g(n)+h(n) （掌握） 】 ? n搜索圖 G中 的節(jié)點 ； ? f(n) G中從初始狀態(tài)節(jié)點 s，經(jīng)由節(jié)點 n到達目標節(jié)點 ng， 估計 的 最小路徑代價 ； ? g(n) G中從 s到 n， 目前實際 的路徑代價； ? h(n)從 n到 ng， 估計 的最小路徑代價； 2022/8/21 99 啟發(fā)式搜索 ——（ 掌握 ） S n ng 目標狀態(tài)節(jié)點 ng 初始狀態(tài)節(jié)點 S 節(jié)點 n 搜索圖 G h(n): nng的估計最小路徑代價 g(n):sn的實際路徑代價 f(n):snng的 估計 最小路徑代價 ??2022/8/21 100 啟發(fā)式搜索 ——（ 掌握 ） ? 【 評價函數(shù) f(n)=g(n)+h(n) （掌握） 】 ? n搜索圖 G中 的節(jié)點 ； ? f(n) G中從 s經(jīng) n到 ng， 估計 的 最小路徑代價 ； ? g(n) G中從 s到 n， 目前實際 的路徑代價； ? h(n)從 n到 ng， 估計 的 最小路徑代價 ； ? h(n)值 依賴于 啟發(fā)式知識 加以計算； ? h(n)稱為 啟發(fā)式函數(shù) （ 掌握意義！ ） 。但對空間要求和深度優(yōu)先搜索一樣是適中的。它結(jié)合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點。 ? 寬度優(yōu)先搜索 需要指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復(fù)雜度和最大搜索深度呈線性關(guān)系。 2022/8/21 92 搜索最優(yōu)策略的比較 ? 表注： b是分支系數(shù)， d是解答的深度， m是搜索樹的最大深度， l是深度限制。 2022/8/21 91 ? 迭代加深搜索看起來會很浪費，因為很多節(jié)點都可能擴展多次。 ? 如果根節(jié)點不是目標，則深度加 1，通過典型的深度優(yōu)先算法，生成深度為 1的樹。 2022/8/21 90 ? 迭代加深搜索 ，試圖嘗試所有可能的深度限制： ? 首先深度為 0， ? 然后深度為 1， ? 然后為 2，等等。 （ 3）有界深度搜索的主要問題是 深度限制值dm的選取 。 2022/8/21 88 （ 2） 深度限制 dm不能太大 。 當(dāng)問題有解，且解的路徑長度小于或等于 dm時，則搜索過程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。 2022/8/21 86 有界深度搜索和迭代加深搜索 有界深度優(yōu)先搜索 過程總體上按深度優(yōu)先算法方法進行，但對搜索深度需要給出一個深度限制 dm，當(dāng)深度達到了 dm的時候，如果還沒有找到解答，就停止對該分支的搜索，換到另外一個分支進行搜索。 ? 共同優(yōu)缺點： ?可直接應(yīng)用一般圖搜索算法實現(xiàn) ， 不需要設(shè)計特別的節(jié)點排序方法 ， 從而簡單易行 ， 適合于許多復(fù)雜度不高的問題求解任務(wù) 。 寬度優(yōu)先搜索的優(yōu)點和缺點 2022/8/21 85 總結(jié) ? 適用場合 ?深度優(yōu)先 ——當(dāng)一個問題有多個解答或多條解答路徑 ，且只須找到其中一個時；往往應(yīng)對搜索深度加以限制 。 ? 寬度優(yōu)先搜索中，時間需求是一個很大的問題，特別是當(dāng)搜索的深度比較大時，尤為嚴重，但是空間需求是比執(zhí)行時間更嚴重的問題。 ? 如果目標發(fā)現(xiàn)，則算法終止。 ?“先產(chǎn)生的節(jié)點先擴展” 2022/8/21 81 Procedure Breadthfirstsearch Begin 把初始節(jié)點放入隊列； Repeat 取得隊列最前面的元素為 current。 2022/8/21 79 寬度優(yōu)先實例 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 1 2 5 6 7 3 1 2 3 8 4 7 6 5 目標 8 2 3 4 1 8 7 6 5 4 9 10 11 12 13 14 15 16 17 2022/8/21 80 寬度優(yōu)先搜索 ?如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做 寬度優(yōu)先搜索。 2022/8/21 78 狀態(tài)空間搜索 —— （ 2）一般圖搜索算法 ? OPEN表中節(jié)點簡單的排序方式 ： ? 深度優(yōu)先 ——擴展當(dāng)前節(jié)點后生成的子節(jié)點總是 置于OPEN表的前端 ，即 OPEN表 作為 棧 ， 后進先出 ，使 搜索優(yōu)先向縱深方向發(fā)展 。很多問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜索下去，而不會回到正確的路徑上。 深度優(yōu)先搜索的優(yōu)點 2022/8/21 77 深度優(yōu)先搜索的缺點 既不是完備的，也不是最優(yōu)的。 2022/8/21 75 深度優(yōu)先搜索的性質(zhì) ?一般不能保證找到最優(yōu)解 ?當(dāng)深度限制不合理時， 可能找不到解 ，可以將算法改為 可變深度限制 ?最壞情況時，搜索空間等同于窮舉 ?是一個通用的與問題無關(guān)的方法 2022/8/21 76 ? 深度優(yōu)先搜索 的 優(yōu)點 是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需要保存搜索樹的一部分，它由當(dāng)前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點標志所組成。該過程直到棧變成為空。 2022/8/21 73 Procedure Depth First Search Begin 把初始節(jié)點壓入棧，并設(shè)置棧頂指針； While 棧不空 do Begin 彈出棧頂元素； If 棧頂元素 =goal，成功返回并結(jié)束； Else 以任意次序把棧頂元素的子女壓入棧中； End While End ?基于棧實現(xiàn)的深度優(yōu)先搜索算法： 2022/8/21 74 ? 初始節(jié)點放到棧中，棧指針指向棧的最上邊的元素。 ?為保證找到解，應(yīng)選擇適當(dāng)?shù)?深度界限 ，或者采取不斷加大深度界限的辦法，反復(fù)搜索，直到找到解。 2022/8/21 70 深度優(yōu)先實例 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 4 6 8 9 11 13 14 16 18 19 1 2 3 8 4 7 6 5 目標 5 7 10 12 15 17 20 21 2022/8/21 71 深度優(yōu)先搜索 ? 在深度優(yōu)先搜索中，首先擴展最新產(chǎn)生的 (最深的 )節(jié)點，深度 相等的節(jié)點可以任意排列。并且要重新加入open表。 2022/8/21 46 以下面的八數(shù)碼為例，看一般圖的搜索算法 初始布局 目標布局 移動數(shù)碼