【文章內容簡介】 按上下左右序走步 2/27/2023 45 寬度優(yōu)先搜索的性質 ? 當問題有解時，一定能找到解 ? 當問題為單位代價值，且問題有解時，一定能找到最優(yōu)解 ? 方法與問題無關，具有通用性 ? 效率較低 ? 屬于圖搜索方法 第三章 一般搜索原理 2/27/2023 46 第三章 一般搜索原理 深度優(yōu)先搜索 成功 是 把第一個節(jié)點 (n)從 OPEN表移至 CLOSED表 把 n的后繼節(jié)點放入 OPEN表的前端，提供返回節(jié)點 n的指針 把 S放入 OPEN表 是 否 否 OPEN為空？ 節(jié)點 n的深度是否等于深度界限？ 失敗 開始 是否有任何后繼節(jié)點為目標節(jié)點？ 是 否 S是否為目標節(jié)點？ 否 成功 2/27/2023 47 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 1 2 3 4 5 6 7 8 9 a b c d 1 2 3 8 4 7 6 5 目標 。 。 第三章 一般搜索原理 八數碼難題的深度優(yōu)先搜索樹 2/27/2023 48 深度優(yōu)先搜索的性質 ? 一般不能保證找到最優(yōu)解 ? 當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制 ? 最壞情況時，搜索空間等同于窮舉 ? 是一個通用的與問題無關的方法 第三章 一般搜索原理 2/27/2023 49 第三章 一般搜索原理 等代價搜索 成功 是 把具有最小 g(i)值的節(jié)點 i從 OPEN表移至 CLOSED表 計算其后繼節(jié)點 j的 g(j)值。把其后繼節(jié)點放入 OPEN表 把 S放入 OPEN表 否 否 OPEN為空？ 失敗 開始 i是否為目標節(jié)點？ 是 S是否為目標節(jié)點？ 否 成功 是 令 g(s)=0 2/27/2023 50 什么是啟發(fā)式搜索 ? 盲目搜索的效率低，耗費過多的計算時間和空間，容易產生組合爆炸。 ? 利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。 ? 對搜索產生幫助的信息稱為啟發(fā)信息 第三章 一般搜索原理 2/27/2023 51 啟發(fā)式信息對搜索方法的影響 ? 啟發(fā)信息的多少用啟發(fā)信息強度來表示 ? 不同的啟發(fā)信息對搜索方法帶來不同的影響： ?強：降低搜索工作量，但可能導致找不到最優(yōu)解 ?弱：一般導致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解 第三章 一般搜索原理 2/27/2023 52 啟發(fā)式搜索類型 ? 啟發(fā)信息按用途可分為 3類： ? 用于決定要擴展的下一個節(jié)點（ 這個節(jié)點稱為最有希望的節(jié)點 ），以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展 ? 在擴展一個節(jié)點的過程中，用于決定要生成哪些其后繼節(jié)點 ， 以免盲目地生成所有節(jié)點。 ? 用于決定哪些節(jié)點應從搜索樹中拋棄或修剪。 ? 用來估算節(jié)點希望程度的方法為估價函數 第三章 一般搜索原理 2/27/2023 53 對啟發(fā)式搜索的認識 ? 有些啟發(fā)信息能夠大大減少搜索工作量，但不能保證能夠得到最小代價路徑 ? 我們往往希望獲得路徑代價和求該路徑所需的搜索代價的綜合為最小 ? 由于計算綜合代價很困難，因此，比較兩種方法的優(yōu)劣，依賴使用的經驗 ? 使用估價函數實際是對 OPEN表進行排序，再按順序擴展節(jié)點，進行搜索 第三章 一般搜索原理 2/27/2023 54 有序搜索 ? 若按估價函數的增序對 OPEN表進行排序，這種搜索方法叫做有序搜索或最佳優(yōu)先搜索 ? 有序搜索的有效性取決于估價函數的選擇，否則有可能失去一個最好的解甚至全部的解 ? 如果沒有合適的選擇，可考慮兩個方面的內容： ? 一個是時間和空間的折中 ? 保證有一個解 第三章 一般搜索原理 2/27/2023 55 有序搜索框圖 第三章 一般搜索原理 成功 是 選取 f值最小的節(jié)點 i，從 OPEN表移至 CLOSED表 擴展 i，計算后繼節(jié)點 j的 f(j)，對 OPEN表重排序，調整親子關系 把 S放入 OPEN表，計算 f(s) 是 否 否 OPEN為空？ i是目標節(jié)點？ 失敗 開始 2/27/2023 56 估價函數： f(n)=d(n)+w(n) 其中， d(n):節(jié)點的深度 w(n):節(jié)點放錯棋子數目 第三章 一般搜索原理 八數碼難題的有序搜索樹 2 8 3 1 6 4 7 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 1 2 3 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 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 1 2 3 7 8 4 6 5 2 3 1 8 4 7 6 5 5 4 6 4 6 6 7 7 5 6 7 5 5 1 2 3 8 4 7 6 5 目標 5 估價函數值 2/27/2023 57 A算法 ? A算法是一種有序搜索的啟發(fā)式搜索算法。它采用估算節(jié)點 n的兩個代價： ?從起始點 s到 n的最小代價路徑的代價 ?從 n到某個目標節(jié)點的最小代價路徑的代價 ? 估價函數的形式： f(n) = g(n) + h(n) 其中： g(n)：是對 g*(n)的估價值 h(n)：是對 h*(n)的估價值 ,稱為啟發(fā)函數 第三章 一般搜索原理 2/27/2023 58 A算法 估價函數的說明 ? g*(n)：從 s到 n的最佳路徑的代價 ? h*(n)：從 n到某個目標節(jié)點的最佳路徑的代價 ? f*(n)=g*(n)+h*(n)： 從 s經過 n到某個目標節(jié)點的最佳路徑的代價 ? g(n)、 h(n)、 f(n)分別是 g*(n)、 h*(n)、 f*(n)的估計值 ? 表明，估價函數 f(n)是對從起始點 s經過 n到某個目標節(jié)點的最佳路徑的代價的估計值 第三章 一般搜索原理 2/27/2023 59 A算法流程 1, OPEN:=(s), f(s):=g(s)+h(s)。 2, LOOP: IF OPEN=( ) THEN EXIT(FAIL)。 3, n:=FIRST(OPEN)。 4, IF GOAL(n) THEN EXIT(SUCCESS)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 6, EXPAND(n) →{mi}, 計算 f(n, mi):=g(n, mi)+h(mi)。 第三章 一般搜索原理 2/27/2023 60 A算法流程（續(xù)） ADD(mj, OPEN), 標記 mj到 n的指針； I