1、第5章：狀態(tài)空間搜索策略，搜索，5.1搜索概述，在解空間中尋找解的過程和搜索策略的出現(xiàn)問題(1)結(jié)構(gòu)差或無結(jié)構(gòu)問題，沒有解析解(2)理論上可解的問題，計(jì)算復(fù)雜度可能太高?；舅阉鞣椒?1)盲搜索，根據(jù)預(yù)定策略搜索，不考慮問題本身的特性(2)啟發(fā)式搜索通過使用與問題相關(guān)的啟發(fā)式信息來加速搜索過程。啟發(fā)式信息和評價(jià)函數(shù)反映了問題的特點(diǎn)?？捎糜诖_定搜索方向的信息評估函數(shù)的功能是根據(jù)作為選擇搜索方向的基礎(chǔ)的啟發(fā)式信息來計(jì)算對應(yīng)于特定搜索方向的評估值。本地搜索與全局搜索在確定搜索方向時(shí)，您是考慮本地信息還是全局信息？任何解決方案與最佳解決方案、搜索方法、圖形搜索方法、廣度優(yōu)先、深度優(yōu)先、有限深度優(yōu)先、啟

2、發(fā)式最佳圖形搜索方法(A*、AO*)、游戲搜索方法、MiniMax、Alpha-Beta修剪(Scorging)、現(xiàn)代優(yōu)化搜索方法，如爬山、模擬退火、遺傳算法、搜索策略評估、完整性，如果問題得到解決，是否能保證找到？優(yōu)化(Optimization)如果問題有不同的解決方案，你能找到最佳解決方案嗎？時(shí)間復(fù)雜度-找到一個(gè)解決方案需要多少時(shí)間和空間復(fù)雜度-在搜索過程中需要占用多少內(nèi)存，時(shí)空復(fù)雜度的度量，狀態(tài)空間圖的大小，分支因子，b，目標(biāo)節(jié)點(diǎn)的深度，d，路徑的最大長度，m，搜索深度限制，l，5.2，問題及其搜索過程的表示，狀態(tài)空間表示用“狀態(tài)”表示問題， 問題解決狀態(tài)通過“算子”的變化表明問題的解決

3、過程，基于“狀態(tài)”和“算子”的狀態(tài)空間是問題解決過程中任何時(shí)刻的狀態(tài)算子，即由操作問題的所有狀態(tài)(包括初始狀態(tài)和目標(biāo)狀態(tài))和所有可用算子組成的集合，使問題從一種狀態(tài)變?yōu)榱硪环N狀態(tài)，稱為問題的狀態(tài)空間。 初始狀態(tài)、中間狀態(tài)1、中間狀態(tài)2、目標(biāo)狀態(tài)、狀態(tài)空間示例：二階梵塔問題，有三個(gè)鋼針，它們的編號(hào)分別為1、2、3。在最初的狀態(tài)下，兩個(gè)金塊，甲和乙，穿在鋼針上。甲比乙小，甲位于乙之上.要求將兩個(gè)金塊全部移動(dòng)到另一個(gè)鋼針上，并規(guī)定一次只能移動(dòng)一個(gè)金塊，任何時(shí)候都不能將大塊放在小塊上。Sk=Sk0，Sk1表示問題的狀態(tài)，其中Sk0表示金鋼片a所在的鋼針號(hào)，Sk1表示金鋼片b所在的鋼針號(hào)。有九種可能的問

4、題狀態(tài)：SO=(1，l) S1=(1，2) S2=(1，3) S3=(2，1) S4=(2，2) S5=(2，3) S6=(3，1) S7=(3，2) S8 B(i，J)表示將金鋼片B從I #鋼針移動(dòng)到J #鋼針。有12種操作：a (1，3) a (2，1) a (2，3) a (3，1) a (3，2) b (1，3) b (2，1) b (2，3) b (3，1) b (3) A(1，3)，b (1，2)，a (3，2)，根據(jù)狀態(tài)和操作符，可以形成二階梵塔問題的狀態(tài)圖，最短路徑解，八數(shù)游戲(八數(shù)問題)描述如下：on這個(gè)游戲解決的問題是：給定一個(gè)卡片的初始布局或結(jié)構(gòu)(稱為初始狀態(tài))和一個(gè)目標(biāo)

5、布局(稱為目標(biāo)狀態(tài))，詢問如何移動(dòng)卡片來實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)換。5.3通用圖搜索算法，無論是狀態(tài)空間還是“與”的問題表示還是圖，問題求解過程都可以看作是在“圖”中搜索。基本思想不是存儲(chǔ)所有的搜索圖，而是逐步擴(kuò)展解決問題所需的搜索子圖。特定方法從初始狀態(tài)開始，不斷擴(kuò)展當(dāng)前節(jié)點(diǎn)，即生成子節(jié)點(diǎn)，直到目標(biāo)狀態(tài)出現(xiàn)在這些子節(jié)點(diǎn)中，或者沒有可擴(kuò)展的節(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)，打開表(未擴(kuò)展節(jié)點(diǎn)表)存儲(chǔ)未擴(kuò)展節(jié)點(diǎn)，關(guān)閉表(擴(kuò)展節(jié)點(diǎn)表)存儲(chǔ)擴(kuò)展節(jié)點(diǎn)，打開表：關(guān)閉表：算法步驟，步驟1將初始節(jié)點(diǎn)S0放入打開表，并建立只包含S0的圖g；第二步：從開放表中取出要擴(kuò)展的節(jié)點(diǎn)，放入封閉表中；(不同搜索策略之間的差異主要體現(xiàn)在

6、這一點(diǎn)上。)步驟3擴(kuò)展節(jié)點(diǎn)，并將擴(kuò)展后的未出現(xiàn)在G中的子節(jié)點(diǎn)放入Open表中；根據(jù)需要修改節(jié)點(diǎn)的指針；步驟4重復(fù)步驟2-3，直到狀態(tài)空間：待擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)或開表為空，盲目搜索策略，廣度(寬度)優(yōu)先搜索，教師制作的節(jié)點(diǎn)先擴(kuò)展深度優(yōu)先搜索，然后生成節(jié)點(diǎn)先擴(kuò)展有限深度優(yōu)先搜索，在深度優(yōu)先策略中增加深度限制，在廣度優(yōu)先和深度優(yōu)先之間折衷，完整，最小路徑解，效率，盲目搜索示例(狀態(tài)空間)為：八張標(biāo)有數(shù)字1、2、3、4、5、6、7和8的牌放在3*3的棋盤上。初始狀態(tài)S0和目標(biāo)狀態(tài)Sg分別如圖所示。您可以使用以下操作：左空格、上空格、右空格和下空格來查找從初始狀態(tài)到目標(biāo)狀態(tài)的解決方案路徑。廣度優(yōu)先搜索

7、算法如下：(1)將初始節(jié)點(diǎn)放入開放表中；(2)如果“打開”表為空，則沒有解決問題的方法，并且無法退出；(3)取出“打開”表中的第一個(gè)節(jié)點(diǎn)，將其放入“關(guān)閉”表中，并將該節(jié)點(diǎn)記錄為“否”；(4)展開節(jié)點(diǎn)N，如果沒有后續(xù)節(jié)點(diǎn)，轉(zhuǎn)到步驟(2)；(5)將N的所有后繼節(jié)點(diǎn)放在開放表的末尾，并提供從這些后繼節(jié)點(diǎn)到父節(jié)點(diǎn)的指針(編號(hào)為N)；(6)如果在新生成的后繼節(jié)點(diǎn)中存在目標(biāo)節(jié)點(diǎn)，則找到解決方案。從目標(biāo)節(jié)點(diǎn)到初始節(jié)點(diǎn)的返回指針可以得到解，算法成功退出。否則，轉(zhuǎn)到(2)繼續(xù)。s，l，o，m，f，p，q，n，f，f，開始節(jié)點(diǎn)，開始，將S0放入打開表，打開表是否為空，失敗，將第一個(gè)節(jié)點(diǎn)n移出打開表并將其放入，成功

8、，否，是，否，是，原理圖，算法框圖，Sg，解決方案的路徑是：S0 3 8 16 26(Sg)，寬度優(yōu)先搜索8位數(shù)字謎，寬度優(yōu)先搜索是一個(gè)完整的策略，即只要深度優(yōu)先搜索深度優(yōu)先搜索是一種稍后生成的節(jié)點(diǎn)先擴(kuò)展的策略。搜索過程如下：從初始節(jié)點(diǎn)S0開始，從其子節(jié)點(diǎn)中選擇一個(gè)新生成的節(jié)點(diǎn)進(jìn)行調(diào)查。如果子節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)并且可以展開，展開子節(jié)點(diǎn)，然后向下搜索，直到子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)也不能繼續(xù)展開，然后選擇其兄弟節(jié)點(diǎn)進(jìn)行調(diào)查。該圖如下：S0，1，2，3，7，6，8，4，5，9，啟動(dòng)節(jié)點(diǎn)，將S0放入打開表，S0是否為目標(biāo)節(jié)點(diǎn)，打開表是否為空表，將打開表中的第一個(gè)節(jié)點(diǎn)n移動(dòng)到關(guān)閉表中，節(jié)點(diǎn)n的深度是否等于深度

9、是否有后續(xù)節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，成功，失敗，成功，是，否，是，否，否，示意圖，算法框圖，深度優(yōu)先搜索算法如下(3)取出“打開”表中的第一個(gè)節(jié)點(diǎn)，將其放入“關(guān)閉”表中，并將該節(jié)點(diǎn)記錄為“否”；(4)檢查節(jié)點(diǎn)N是否為目標(biāo)節(jié)點(diǎn)，如果是，則得到問題的解決方案并成功退出；(5)如果節(jié)點(diǎn)n不可擴(kuò)展，請轉(zhuǎn)到(2)；(6)展開節(jié)點(diǎn)N，將其子節(jié)點(diǎn)放在打開表的頭部，為每個(gè)子節(jié)點(diǎn)設(shè)置一個(gè)指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)到(2)。從深度優(yōu)先搜索算法可以看出，一旦搜索進(jìn)入一個(gè)分支，它將沿著這個(gè)分支繼續(xù)。如果目標(biāo)恰好在這個(gè)分支上，它可以很快找到解決方案。然而，如果目標(biāo)不在該分支上，并且該分支是無限分支，則在搜索過程中不可能找到解決方案

10、。因此，深度優(yōu)先搜索是一個(gè)不完整的策略，即使問題有解決方案，它也可能無法找到解決方案。解的路徑是： so: l 11 12 13 14: SG，SG，有界深度優(yōu)先搜索八位數(shù)字謎，28 34 765，s0，1，28 31 47 65，2，23 84 765，11，28 34 765，28 36 47 5，8 3 2 1 4 7 6 5，2 8 3 7 1 4 6 5，2 3 8 4 7 6 5，2 3 8 4 7 6 5，2 8 3 7 6 5，2 3 7 6 5，2 8 3 4 5 5 7 6，2 8 3 6 4 4 7 5，2 8 3 6 4 7 5，3，7，13，8 3 2 1 4 7 6

11、 5， 2 8 3 7 1 4 6 5，1 2 3 8 4 7 6 5，2 3 4 8 7 6 5，2 8 4 3 7 6 5，2 8 3 4 5 7 6，2 8 3 6 4 1 7 5，2 8 3 6 7 7 5 4，4，8，8 3 2 1 4 7 6 5，8 1 3 2 4 7 6 5，5，6，28 37 46 15，28 37 14 65，9，10，1 23 84 76 5，1 23 78 46 5，5 以上討論的所有搜索方法都不使用問題本身的特征信息，而是根據(jù)預(yù)設(shè)的路徑進(jìn)行搜索，這是盲目的。事實(shí)上，如果我們能夠利用在搜索過程中獲得的問題的一些特征信息來指導(dǎo)搜索過程，將會(huì)對搜索非常有益。

12、這種搜索策略利用問題本身的特點(diǎn)來指導(dǎo)搜索過程，提高搜索效率，稱為啟發(fā)式搜索或信息搜索。啟發(fā)式搜索方法基于問題本身的啟發(fā)式信息，啟發(fā)式信息通過賦值函數(shù)作用于搜索過程。5.4啟發(fā)式搜索。啟發(fā)式算法利用問題的特殊性選擇要擴(kuò)展的節(jié)點(diǎn)，從而縮小搜索范圍，提高搜索速度。啟發(fā)式信息可以指導(dǎo)搜索過程，是與具體問題解決過程相關(guān)的控制信息。通常有三種類型：幫助確定擴(kuò)展節(jié)點(diǎn)的信息；幫助決定應(yīng)該生成哪些后續(xù)節(jié)點(diǎn)的信息；評估函數(shù)f(n):用于估計(jì)節(jié)點(diǎn)成本的函數(shù)被定義為在被節(jié)點(diǎn)n約束之后從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)Sg的所有路徑中的最佳路徑的成本估計(jì)值。一般形式是f(n)=g(n)h(n)g(n)，它是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n

13、的實(shí)際成本.您可以從節(jié)點(diǎn)n追溯到初始節(jié)點(diǎn)S0，并以最低的成本獲得當(dāng)前路徑。將這條路徑上所有有向邊的成本相加，得到g(n)的值。H(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)S0的最佳路徑的估計(jì)成本。它需要根據(jù)問題本身的特點(diǎn)來確定，這反映了問題本身的啟發(fā)式信息，所以它也稱為啟發(fā)式函數(shù)。評估函數(shù)示例：f(n)=d(n) W(n)，搜索樹中節(jié)點(diǎn)n的深度，n、中的“不在位置”位數(shù)f(S0)=？=0 3=3，根據(jù)搜索過程中選擇的擴(kuò)展節(jié)點(diǎn)范圍，可分為全局首選搜索和局部首選搜索。1.從打開表的所有節(jié)點(diǎn)中全局選擇一個(gè)具有最小賦值函數(shù)值的節(jié)點(diǎn)進(jìn)行擴(kuò)展；2.從新生成的子節(jié)點(diǎn)中本地選擇具有最小賦值函數(shù)值的節(jié)點(diǎn)進(jìn)行擴(kuò)展。局部最佳優(yōu)先搜

14、索算法，比較OPEN表中所有節(jié)點(diǎn)的f(n)，將OPEN表從小到大重新排列。該算法的效率與垂直搜索算法相似，但它是一種啟發(fā)式搜索方法，因?yàn)樗褂门c問題特征相關(guān)的評估函數(shù)來確定下一步要擴(kuò)展的節(jié)點(diǎn)。開始，將s放入open表，計(jì)算評估函數(shù)f (s)，OPEN表為空？將OPEN表中的第一個(gè)節(jié)點(diǎn)n放入CLOSED表中。n是目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展n，計(jì)算所有子節(jié)點(diǎn)的評估函數(shù)值，并提供它們的指針返回節(jié)點(diǎn)n，失敗、成功、局部最佳優(yōu)先搜索算法框圖，是、否、是、否，將子節(jié)點(diǎn)發(fā)送到OPEN表中，并根據(jù)評估函數(shù)值從小到大重新排列其中的所有節(jié)點(diǎn)。例如：8字謎題，5，7，搜索到的路徑用黃線表示。本主題使用一個(gè)簡單的評估函數(shù)f(n

15、)=W(n)，其中W(n)用于計(jì)算對應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫中放錯(cuò)位置的棋子數(shù)量。因此，初始節(jié)點(diǎn)象棋游戲的f(n)值等于4。第一步有三種情況，我們選擇f(n)最小的：依此類推。最后，我們通過七個(gè)步驟得到結(jié)果。(3)、(5)、(5)、(5)，最佳優(yōu)先算法有時(shí)不能得到最優(yōu)解，因?yàn)樗脑u價(jià)函數(shù)f忽略了從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代值。因此，我們可以考慮對評估函數(shù)f(n)進(jìn)行一些修改或限制。5.5 A*算法，對評價(jià)函數(shù)增加一些限制，以保證最優(yōu)評價(jià)函數(shù)f*(n) g*(n) h*(n)，從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià)，以及從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià)的啟發(fā)式搜索算法得到最優(yōu)解，以及相關(guān)限制1。g(n)是g*(n)和g. 2的估計(jì)。h(n)是h*(n)的下界，也就是說，任何節(jié)點(diǎn)n都有H (n) H * (n)。算法示例1:八位數(shù)問題，解1: H (n)=W (n)。雖然h*(n)不能被精確地知道，但是當(dāng)采用單位成本時(shí)，通過估計(jì)“非現(xiàn)場”數(shù)字的數(shù)量，可以得出結(jié)論，通過移動(dòng)至少W(n)個(gè)步驟可以達(dá)到目標(biāo)，并且顯然存在W(n)個(gè)h*(n)，這滿足了A*算法的限制。解決方案2: H (n)=P(n)，其中