【正文】 ,是 深度優(yōu)先搜索的一種改進(jìn) 。 該問題解的路徑是： （見 圖 720所示） S0→3→4→5→S g?！　　∵@樣，初始狀態(tài) S0的估價(jià)函數(shù)值為： f（ 0） = 0 + 3 = 3。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索77第七章 搜索策略例 　利用估價(jià)函數(shù)方法 求解圖 7 14所示的重排九宮問題 ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索76第七章 搜索策略　　　因此，單純的 “ 寬度優(yōu)先 ” 和 “ 深度優(yōu)先 ” 搜索法是 兩種極端的情形 ?！　　「鶕?jù) “ 最晚生成的優(yōu)先擴(kuò)展 ” 的深度優(yōu)先搜索規(guī)則 ，每次擴(kuò)展時(shí)，將所生成的各子節(jié)點(diǎn)中最晚的，作為控制策略引入到評價(jià)函數(shù) f(x)中，假定最晚生成的節(jié)點(diǎn)的代價(jià)最小，是最有希望的搜索方向。基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索75第七章 搜索策略⑵ 在 f(x)中， h(x)的權(quán)增大 ，搜索過程將 傾向于深度優(yōu)先搜索，強(qiáng)調(diào) “ 縱向深入 ” ，沿最有希望的方向前進(jìn)，利用啟發(fā)性知識(shí)， 提高搜索效率，壓縮搜索空間 ，但卻放棄了橫向掃描， 降低了搜索過程的完備性 ?！?例如， 在 寬度優(yōu)先搜索法 中：　　　　　 f（ x） = g（ x） = d（ x）　式中： d（ x）：搜索深度。　　　當(dāng) w減小， v增加 ,即 g（ x）的比重增大 ,這時(shí)表示 強(qiáng)調(diào) “歷史信息 ” 的作用和 “ 橫向掃描 ” 的搜索 。 v、 w≥0 。基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索73第七章 搜索策略關(guān)于估價(jià)函數(shù) f（ x）的討論　　　在 估價(jià) 函數(shù) f（ x） 中， g（ x）和 h（ x）各起 著不同的角色 。 其形式要根據(jù)問題的特性確定 。 g(x)可以根據(jù) 生成的搜索樹實(shí)際計(jì)算出來 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索72第七章 搜索策略　　　 f(x)估價(jià)函數(shù) 可以是 任意一種函數(shù) 。　　　它綜合考慮了 兩方面的因素 ：　　　　　　　　 已經(jīng)付出的代價(jià) 和 將要付出的代價(jià) 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索70第七章 搜索策略 估價(jià)函數(shù) 是用于 估價(jià)節(jié)點(diǎn)重要性的實(shí)值函數(shù) ?！　　?估價(jià)函數(shù) 能夠 提供一個(gè)評定候選擴(kuò)展節(jié)點(diǎn)的方法以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上 。由于這種搜索 針對性較強(qiáng) ，因而原則上 只需要搜索問題的部分狀態(tài)空間 ， 效率較高 。 啟發(fā)式搜索基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索68第七章 搜索策略 　　利用 與具體問題的解有關(guān)的控制性信息來確定下一個(gè)要考察的節(jié)點(diǎn) ，這種控制性信息稱之為 啟發(fā)式信息 ?！　　∫虼耍?這些搜索方法 都具有較大的 盲目性 ，產(chǎn)生的 無用節(jié)點(diǎn)較多，搜索空間較大，效率不高 ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索2 8 31 47 6 51 2 38 47 6 5(a)初始狀態(tài) (b)目標(biāo)狀態(tài)67第七章 搜索策略啟發(fā)式信息 　　前述的各種搜索方法都是 非啟發(fā)式搜索 。基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索66第七章 搜索策略例 ： 設(shè) 深度界限 dm = 4 ，用有界深度優(yōu)先搜索方法 求解圖 714所示（如下） 的重排九宮問題。⑸ 如果節(jié)點(diǎn) n的深度 d（ n） = dm，則轉(zhuǎn)第 ⑵ 步 ；⑹ 如果節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第 ⑵ 步；⑺ 擴(kuò)展節(jié)點(diǎn) n， 將其子節(jié)點(diǎn)放入 OPEN表的首部 ，并為其配置指向父節(jié)點(diǎn)的指針。⑶ 把 OPEN表中的第１個(gè)節(jié)點(diǎn)取出放入 CLOSED表中，并按順序冠以編號(hào) n；⑷ 考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)?！　　』靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索63第七章 搜索策略　　　因此， 若問題有解 （在問題樹中存在目標(biāo)節(jié)點(diǎn) Sg，且處在有限深度范圍內(nèi)）， 當(dāng)所選取的搜索深度限制值（ dm）大于或等于目標(biāo)節(jié)點(diǎn) Sg所處實(shí)際深度時(shí) ，則有界深度優(yōu)先搜索法 一定可以找到目標(biāo)節(jié)點(diǎn) Sg，保證推理過程的收斂性，求得問題的解。 有限深度優(yōu)先搜索基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索62第七章 搜索策略　　 為了 改進(jìn)深度優(yōu)先搜索法 ， 以免搜索過程陷入無窮分枝的死循環(huán) ，可以 引入搜索深度界限（設(shè)為 dm） ?！　　〉牵?若誤陷入無窮分枝 ，進(jìn)入死循環(huán)，則搜索過程無法收斂 ， 不能找到目標(biāo)節(jié)點(diǎn) ?！　　∫话阏f來它僅是一個(gè)過程， 需要進(jìn)一步改進(jìn) 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索60第七章 搜索策略　　　 如果問題有解 ，且 問題樹沒有無窮分枝 ，則 必在 OPEN表中出現(xiàn) Sg，過程必將在 ⑷ 停止，搜索成功 。 若是，則求得了問題的解，成功并退出 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索58第七章 搜索策略 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索深度優(yōu)先搜索的示例 59第七章 搜索策略深度優(yōu)先搜索的流程 深度優(yōu)先搜索的搜索過程如下 ：⑴ 把 初始節(jié)點(diǎn) S0放入 OPEN表 ；⑵ 如果 OPEN表為空，則問題無解，失敗并退出 。 深度優(yōu)先搜索基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索57第七章 搜索策略 由于 一個(gè)有解的問題常常含有 無窮分枝 ，深度優(yōu)先搜索過程 如果誤入無窮分枝，就不可能找到目標(biāo)節(jié)點(diǎn) ，所以它是不完備的 。　　　它是 從初始節(jié)點(diǎn) S0開始 ,按生成規(guī)則 生成下一級(jí)各子節(jié)點(diǎn) ， 檢查是否出現(xiàn)目標(biāo)節(jié)點(diǎn) Sg；　　　 若未出現(xiàn) ，則按 “ 最晚生成的子節(jié)點(diǎn)優(yōu)先擴(kuò)展 ” 的 原則 ， 再生成再下一級(jí)的子節(jié)點(diǎn)，再檢查是否出現(xiàn) Sg； 若仍未出現(xiàn)，則再 沿著最晚生成的子節(jié)點(diǎn)分枝生成子節(jié)點(diǎn) ， 如此下去 ， 即逐級(jí) “ 縱向 ” 深入搜索 。　　由圖可知，從 初始狀態(tài) S0轉(zhuǎn)移到目標(biāo)狀態(tài) Sg的最短路徑 為：　　　 S0→3→8→16→26 （ Sg）　　即為 重排九宮問題的解 。如圖 (a)初始狀態(tài) (b)目標(biāo)狀態(tài)2 8 31 47 6 51 2 38 47 6 5S0 Sg基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索55第七章 搜索策略解： 用寬度優(yōu)先搜索法， 生成規(guī)則為 ： 紙牌移入空格的次序是由空格左邊開始，順時(shí)針方向移動(dòng)，不允許斜方向移動(dòng)，不允許返回 。　　要求是： 只允許把 空格上、下、左、右的紙牌移入空格 ，而 空格移至該紙牌原有的位置 。 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索54第七章 搜索策略例 重排九宮問題 ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索53第七章 搜索策略　　 在 寬度優(yōu)先搜索 下， 如果問題有解， OPEN表中必然出現(xiàn)目標(biāo)節(jié)點(diǎn) Sg，而且算法一定 在 ⑷ 停止，這表示解已找到 。否則往下?！?⑶ 把 OPEN表中的第一個(gè)節(jié)點(diǎn)取出放入 CLOSED表 中，并 按順序冠以編號(hào) n；　 ⑷ 考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn) ?；靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索51第七章 搜索策略 基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索廣度優(yōu)先搜索的示例 52第七章 搜索策略寬度優(yōu)先搜索的流程　　 ⑴ 把 初始節(jié)點(diǎn) S0放入 OPEN表 ；　 ⑵ 如果 OPEN表為空，則問題無解，失敗并退出 ?！　?若沒有 ， 則 再將所有第一 層節(jié) 點(diǎn)逐一 擴(kuò) 展，得到第二 層節(jié)點(diǎn) ，并 逐一 檢查 第二 層節(jié) 點(diǎn)中是否包含有 Sg，如此 依次按照先生成、先 檢查 、先 擴(kuò) 展的原 則進(jìn) 行下去 ， 直到 發(fā)現(xiàn) Sg為 止 。216?！　?在 n層節(jié) 點(diǎn)未搜索完之前，不 進(jìn) 入 n+1層 搜索 。節(jié) 點(diǎn) 父 節(jié) 點(diǎn) 編 號(hào) 節(jié) 點(diǎn) 父 節(jié) 點(diǎn)OPEN表 CLOSED表基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索49第七章 搜索策略　　 寬 度 優(yōu) 先搜索 (BreadthFirst Search)又稱 為 廣度 優(yōu) 先搜索 ?！　?CLOSED表是一個(gè) “有 進(jìn) 無出 ”的 動(dòng)態(tài) 數(shù)據(jù) 結(jié) 構(gòu) ， 當(dāng)前 節(jié) 點(diǎn)進(jìn) 入 CLOSED表的最后 。　　 節(jié) 點(diǎn) 進(jìn) 入 OPEN表的排列 順 序，也是出表的 順 序 ?！　』靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索47第七章 搜索策略　　 OPEN表 用于 存放 剛 生成的 節(jié) 點(diǎn) ， 這 些 節(jié) 點(diǎn)將作 為 以后待考察的 對 象 。它是由 尼 爾 遜 （ ） 提出的一個(gè) 圖 搜索 過 程 GRAPHSEARCH ，它是表達(dá)能力很 強(qiáng) 的一個(gè) 搜索策略框架 。　　 重復(fù)上述 過 程 ，直到 目 標(biāo) 狀 態(tài) 出 現(xiàn) 或者不再有可供操作的狀 態(tài) 及算符 時(shí)為 止 ?！　』靖拍?狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索45第七章 搜索策略　　 方法是 先把 問題 的初始狀 態(tài) 作 為 當(dāng)前狀 態(tài) ， 選擇 適用的算符 對 其 進(jìn) 行操作 ，生成 一 組 子狀 態(tài) ， 檢查 目 標(biāo) 狀 態(tài) 是否在其中出 現(xiàn) ?！?　 這 種 尋 找 過 程 從 圖 中的初始 節(jié) 點(diǎn)開始，至目 標(biāo)節(jié) 點(diǎn) 為 止。 為了 節(jié)約計(jì)算機(jī)的存儲(chǔ)容量，提高搜索推理效率 ， 通常采用隱式存儲(chǔ)方式 ，進(jìn)行隱式圖搜索推理。 圖搜索的基本概念基本概念 狀態(tài)空間的搜索策略 與 /或圖的搜索策略 博弈樹搜索43第七章 搜索策略2) 隱 式存 儲(chǔ)　　只 存 儲(chǔ) 與 問題 求解有關(guān)的部分知 識(shí) (即部分狀 態(tài) 空 間 )，這 種存 儲(chǔ) 方式稱 為 隱 式存 儲(chǔ) 。1) 顯 式存 儲(chǔ) 把 與 問題 有關(guān)的全部狀 態(tài) 空 間圖 ，即 相 應(yīng) 的全部有關(guān)知識(shí) （敘述性知 識(shí) 、 過 程性知 識(shí) 和控制性知 識(shí) ）， 都直接存入知 識(shí)庫 ， 這 種存 儲(chǔ) 方式稱 為 顯 式存 儲(chǔ) 或 顯 式 圖 。 有限深度優(yōu)先搜索216。 寬度優(yōu)先搜索216。解 : 原始問題為：P: (Q5， F， {Q0， Q7} )對 P等價(jià)變換（即 “或 ”）后為 :P1: (Q5， F， Q0 )P2: (Q5， F， Q7 )因?yàn)?，?P1無解，而 P2有 7個(gè)解，即 aab， aba， baa， bbb， bcc，cbc， ccb.36對解 1(aab)可得 (分解 ,即 “與 ”)P21: (Q5, F, Q5 )P22: (Q5, b, Q7 )　而對 P21又可分解（即 “與 ”)得P211: (Q5, a, Q1 )P212: (Q1, a, Q5 )同理 對解 2(aba)可得P23: (Q5, F, Q3 )P24: (Q3, a, Q7 )　而對 P23又可分解（即 “與 ”)得P231: (Q5, a, Q1 )P232: (Q1, b, Q3 ) 37對解 3(baa)可得P25: (Q5, F, Q3 )P26: (Q3, a, Q7 )　而對 P25又可分解（即 “與 ”)得P251: (Q5, a, Q7 )P252: (Q1, a, Q3 )對解 4(bbb)可得P27: (Q5, F, Q5 )P28: (Q5, b, Q7 )　而對 P27又可分解（即 “與 ”)得P271: (Q5, b, Q7 )P272: (Q7, b, Q5 )38對解 5(bcc)可得P29: (Q5, F, Q6 )P30: (Q6, c, Q7 )　而對 P29又可分解（即 “與 ”)得P291: (Q5, b, Q7 )P292: (Q7, c, Q6 )對解 6(cbc)可得P31: (Q5, F, Q6 )P32: (Q6, c, Q7 )　而對 P31又可分解（即 “與 ”)得P311: (Q5, c, Q4 )P312: (Q4, b, Q6 )39對解 7(ccb)可得P33: (Q5, F, Q5 )P34: (Q5, b, Q7 )　而對 P33又可分解（即 “與 ”)得P331: (Q5, c, Q4 )P332: (Q4, c, Q5 )40 PP2P1P26P21 P24P22 P25P23 ……P211 P212 P231 P232 ……41第七章 搜索策略l 基本概念l 狀態(tài)空間的搜索技術(shù)l 與 /或圖的搜索策略l 博弈樹搜索216。