盲目搜索啟發(fā)式搜索

盲目搜索按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策略。效率低、主要用于簡單問題求解。啟發(fā)式搜索在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。搜索原理什么是搜索？根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條代價較少的推理路線，使問題得到圓滿解決的過程。1與圖有關(guān)的術(shù)語狀態(tài)空間圖——由節(jié)點(不一定是有限的節(jié)點)及連接節(jié)點的分枝的集合構(gòu)成。有限節(jié)點圖——節(jié)點數(shù)目有限的圖稱為有限節(jié)點圖。有向圖——一對節(jié)點用分枝線連接起來，從一個節(jié)點指向另一個節(jié)點。這種圖叫做有向圖。始節(jié)點叫父節(jié)點或雙親節(jié)點，終節(jié)點叫子節(jié)點。擴(kuò)展——求解父節(jié)點的所有子節(jié)點，叫做擴(kuò)展。路徑——在一系列節(jié)點n1,n2,,nm中，從n1開始，ni總有分枝連接ni+1，稱從n1到nm之間的分枝集合是路徑。路徑中不包含兩個及以上相同的分枝，如果n1和nm是同一個節(jié)點，則稱這種路徑為閉路。不構(gòu)成閉路的稱為樹。在用狀態(tài)空間圖來表示問題時，對問題的求解就是求出從初始節(jié)點到目標(biāo)節(jié)點的路徑。圖搜索策略1.圖搜索的定義——一種計算機(jī)在狀態(tài)圖中尋找路徑的方法。2.CLOSED表的引入編號節(jié)點號父節(jié)點號CLOSED表(記錄擴(kuò)展過的節(jié)點)OPEN表的引入節(jié)點號父節(jié)點號OPEN表(記錄待擴(kuò)展的節(jié)點)舉例：八數(shù)碼魔方例子中OPEN表變化過程節(jié)點號父節(jié)點號S0空AS0BS0CS0DS0EAFACLOSED表變化過程編號節(jié)點號父節(jié)點號0S0空1AS02BS0圖搜索的一般過程(1)建立一個只含有起始節(jié)點S的搜索圖G，把S放到一個叫做OPEN表的未擴(kuò)展節(jié)點表中。(2)建立一個叫做CLOSED的已擴(kuò)展節(jié)點表，其初始為空表。(3)LOOP：若OPEN表是空表，則失敗退出。(4)選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點為節(jié)點n。(5)若n為一目標(biāo)節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置)。圖搜索的一般過程(6)擴(kuò)展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。(7)對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設(shè)置一個通向n的指針。把M的這些成員加進(jìn)OPEN表。對已經(jīng)在OPEN或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。(8)按某一任意方式或按某個探試值，重排OPEN表。(9)GOLOOP。開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點嗎？把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針修改指針方向重排OPEN表失敗成功圖搜索一般過程的框圖是是否否一、盲目搜索

盲目搜索又叫做無信息搜索，一般只適用于求解比較簡單的問題。主要包括寬度優(yōu)先搜索、等深度優(yōu)先搜索等。特點：

1）搜索按規(guī)定的路線進(jìn)行，不使用與問題有關(guān)的啟發(fā)性信息。

2）適用于其狀態(tài)空間圖是樹狀結(jié)構(gòu)的一類問題。131、寬度優(yōu)先搜索

定義：如果搜索是以接近起始節(jié)點的程度依次擴(kuò)展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-firstsearch)。

基本思想：從初始節(jié)點S開始，逐層地對節(jié)點進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點，在第n層的節(jié)點沒有全部擴(kuò)展并考察之前，不對第n＋1層的節(jié)點進(jìn)行擴(kuò)展。OPEN表中的節(jié)點總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點排在前面，后進(jìn)入的排在后面。14寬度優(yōu)先搜索示意圖15寬度優(yōu)先搜索算法：

(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標(biāo)節(jié)點，則求得一個解答)。

(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。

(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點表中。

(4)擴(kuò)展節(jié)點n。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第(2)步。

(5)把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。

(6)如果n的任一個后繼節(jié)點是個目標(biāo)節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。2023/2/216寬度優(yōu)先搜索算法框圖17寬度優(yōu)先搜索方法分析：寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第8步具體化為本算法中的第6步，這實際是將OPEN表作為“先進(jìn)先出”的隊列進(jìn)行操作。寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在，那么對有限圖來說，就說該法失敗退出；對于無限圖來說，則永遠(yuǎn)不會終止)。18

例如：寬度優(yōu)先搜索用于八數(shù)碼難題。這個問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題：

搜索樹上的所有節(jié)點都標(biāo)記它們所對應(yīng)的狀態(tài)描述，每個節(jié)點旁邊的數(shù)字表示節(jié)點擴(kuò)展的順序(按順時針方向移動空格)。圖中最后一個節(jié)點是目標(biāo)節(jié)點。19八數(shù)碼難題的寬度優(yōu)先搜索樹

2620對應(yīng)動態(tài)演示圖212、深度優(yōu)先搜索基本思想：從初始節(jié)點S開始，在其子節(jié)點中選擇一個節(jié)點進(jìn)行考察，若不是目標(biāo)節(jié)點，則再在該子節(jié)點中選擇一個節(jié)點進(jìn)行考察，一直如此向下搜索。當(dāng)?shù)竭_(dá)某個子節(jié)點，且該子節(jié)點既不是目標(biāo)節(jié)點又不能繼續(xù)擴(kuò)展時，才選擇其兄弟節(jié)點進(jìn)行考察。2023/2/222

深度優(yōu)先搜索示意圖

2023/2/223

在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點（深度相等的節(jié)點可以任意排列）。其結(jié)果是搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。替代路徑與前面已經(jīng)試過的路徑不同之處僅僅在于改變最后n步，而且保持n盡可能小。3、深度優(yōu)先搜索2023/2/2243.1.3深度優(yōu)先搜索2023/2/225對于許多問題，其狀態(tài)空間搜索樹的深度可能為無限深，或者可能至少要比某個可接受的解答序列的已知深度上限還要深。為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴(kuò)展下去)，往往給出一個節(jié)點擴(kuò)展的最大深度——深度界限。任何節(jié)點如果達(dá)到了深度界限，那么都將把它們作為沒有后繼節(jié)點處理。值得說明的是，即使應(yīng)用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。有界深度優(yōu)先搜索

定義節(jié)點的深度如下：

(1)起始節(jié)點(即根節(jié)點)的深度為0。

(2)任何其它節(jié)點的深度等于其父輩節(jié)點深度加上1。2023/2/226含有深度界限的深度優(yōu)先搜索算法：

(1)把起始節(jié)點S放到未擴(kuò)展節(jié)點OPEN表中。如果此節(jié)點為一目標(biāo)節(jié)點，則得到一個解。

(2)如果OPEN為一空表，則失敗退出。

(3)把第一個節(jié)點(節(jié)點n)從OPEN表移到CLOSED表。

(4)如果節(jié)點n的深度等于最大深度，則轉(zhuǎn)向(2)。

(5)擴(kuò)展節(jié)點n，產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒有后裔，則轉(zhuǎn)向(2)。

(6)如果后繼節(jié)點中有任一個為目標(biāo)節(jié)點，則求得一個解，成功退出；否則，轉(zhuǎn)向(2)。有界深度優(yōu)先搜索2023/2/227算法動態(tài)演示圖

2023/2/228

例如：按深度優(yōu)先搜索生成八數(shù)碼難題搜索樹，設(shè)置深度界限為5。

下圖繪出了搜索樹，粗線條的路徑表明含有5條應(yīng)用規(guī)則的一個解。從圖可見，深度優(yōu)先搜索過程是沿著一條路徑進(jìn)行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。2023/2/229八數(shù)碼難題的深度優(yōu)先搜索樹

2023/2/230二、啟發(fā)式搜索

盲目搜索的不足：效率低，耗費過多的計算空間與時間。寬度優(yōu)先搜索、深度優(yōu)先搜索，或等代價搜索算法,是按事先規(guī)定的路線進(jìn)行搜索，或按已經(jīng)付出的代價決定下一步要搜索的節(jié)點，其主要差別是OPEN表中待擴(kuò)展節(jié)點的順序問題。如果找到一種方法用于排列待擴(kuò)展節(jié)點的順序，即選擇最有希望的節(jié)點加以擴(kuò)展，那么，搜索效率將會大為提高。2023/2/231二、啟發(fā)式搜索

盲目搜索的共同特點：沒有利用問題本身的特性信息，在決定要被擴(kuò)展的節(jié)點時，都沒有考慮該節(jié)點在解的路徑上的可能性有多大，它是否有利于問題求解以及求出的解是否為最優(yōu)解等。2023/2/232二、啟發(fā)式搜索

啟發(fā)信息進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域特性的、與具體問題求解過程有關(guān)的、并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息，把此種信息叫做啟發(fā)信息。

把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。

特點：重排OPEN表，選擇最有希望的節(jié)點加以擴(kuò)展種類：最佳優(yōu)先搜索、A*算法等2023/2/2331、啟發(fā)式搜索策略

啟發(fā)信息按其用途可分為3種：

(1)用于決定要擴(kuò)展的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴(kuò)展。

(2)在擴(kuò)展一個節(jié)點的過程中，用于決定要生成哪一個或哪幾個后繼節(jié)點，以免盲目地同時生成所有可能的節(jié)點。

(3)用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點。2023/2/2342、估價函數(shù)用來估算節(jié)點希望程度的量度，叫做估價函數(shù)(evaluationfunction)。估價函數(shù)的任務(wù)就是估計OPEN表中各節(jié)點的重要程度。一個節(jié)點的“希望”(promise)有幾種不同的定義方法:1)估算目標(biāo)節(jié)點到此節(jié)點的距離；

2)解答路徑包括被估價過的節(jié)點，并計算全條路徑的長度或難度。2023/2/2352、估價函數(shù)

用符號f來標(biāo)記估價函數(shù)，用f(n)表示節(jié)點n的估價函數(shù)值。暫時令f為任意函數(shù)，以后將會提出f是從起始節(jié)點約束地通過節(jié)點n而到達(dá)目標(biāo)節(jié)點的最小代價路徑上的一個估算代價。

一般形式：

f(n)=g(n)+h(n)g(n)是從s0到n的實際代價。

h(n)是從節(jié)點n到目標(biāo)節(jié)點sg的估計代價。2023/2/2363、有序搜索

用估價函數(shù)f來排列GRAPHSEARCH第8步中OPEN表上的節(jié)點。根據(jù)習(xí)慣，OPEN表上的節(jié)點按照它們f函數(shù)值的遞增順序排列。根據(jù)推測，某個具有低估價值的節(jié)點較有可能處在最佳路徑上。應(yīng)用某個算法(例如等代價算法)選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴(kuò)展的節(jié)點。這種搜索方法叫做有序搜索或最佳優(yōu)先搜索，而其算法就叫做有序搜索算法或最佳優(yōu)先算法?？梢娝偸沁x擇最有希望的節(jié)點作為下一個要擴(kuò)展的節(jié)點。有序搜索(orderedsearch)又稱為最好優(yōu)先搜索(best-firstsearch)。2023/2/2373、有序搜索

尼爾遜（Nilsson）曾提出一個有序搜索的基本算法。估價函數(shù)f按照如下方法確定：一個節(jié)點希望程度越大，其f值就越小。被選為擴(kuò)展的節(jié)點，是估價函數(shù)最小的節(jié)點。2023/2/238有序狀態(tài)空間搜索算法(1)把起始節(jié)點S放到OPEN表中，計算f(S)并把其值與節(jié)點S聯(lián)系起來。(2)如果OPEN是個空表，則失敗退出，無解。(3)從OPEN表中選擇一個f值最小的節(jié)點i。結(jié)果有幾個節(jié)點合格，當(dāng)其中有一個為目標(biāo)節(jié)點時，則選擇此目標(biāo)節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點i。(4)把節(jié)點i從OPEN表中移出，并把它放入CLOSED的擴(kuò)展節(jié)點表中。(5)如果i是個目標(biāo)節(jié)點，則成功退出，求得一個解。

2023/2/239(6)擴(kuò)展節(jié)點i生成其全部后繼節(jié)點。對于i的每一個后繼節(jié)點j：(a)計算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點i的指針，以便一旦找到目標(biāo)節(jié)點時記住一個解答路徑。(c)如果j已在OPEN表上或CLOSED表上，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f值。如果新的f值較小，則(i)以此新值取代舊值。(ii)從j指向i，而不是指向它的父輩節(jié)點。(iii)如果節(jié)點j在CLOSED表中，則把它移回OPEN表(7)轉(zhuǎn)向(2)，即GOTO(2)。有序狀態(tài)空間搜索算法2023/2/240注釋：步驟（6.c）是一般搜索圖所需要的，該圖中可能有一個以上的父輩節(jié)點。具有最小估價函數(shù)f（j）的節(jié)點被選作父輩節(jié)點。但是，由于搜索樹，它最多只有一個父輩節(jié)點，所以步驟（6.c）可以略去。有序狀態(tài)空間搜索算法2023/2/241

有序搜索算法框圖

2023/2/242

有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個最好的解甚至全部的解。如果沒有適用的準(zhǔn)確的希望量度，那么f的選擇將涉及兩個方面的內(nèi)容：一方面是時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意解。有序狀態(tài)空間搜索算法2023/2/243有序搜索例子使用八數(shù)碼難題例子說明過程GRAPHSEARCH是如何應(yīng)用估價函數(shù)排列節(jié)點的。采用簡單的估價函數(shù)

f(n)=d(n)+W(n)

其中：d(n)是搜索樹中節(jié)點n的深度；W(n)用來計算對應(yīng)于節(jié)點n的數(shù)據(jù)庫中錯放的棋子個數(shù)。2023/2/244起始節(jié)點棋局28316475的f值等于1+4=5。有序搜索例子2023/2/245八數(shù)碼難題的有序搜索樹2023/2/2462023/2/247從圖可見，這里所求得的解答路徑和用其它搜索方法找到的解答路徑相同。不過，估價函數(shù)的應(yīng)用顯著地減少了被擴(kuò)展的節(jié)點數(shù)(如果我們只用估價函數(shù)f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過程)。八數(shù)碼難題的有序搜索樹2023/2/248正確地選擇估價函數(shù)對確定搜索結(jié)果具有決定性的作用。使用不能識別某些節(jié)點真實希望的估價函數(shù)會形成非最小代價路徑；而使用一個過多地估計了全部節(jié)點希望的估價函數(shù)(就像寬度優(yōu)先搜索方法得到的估價函數(shù)一樣)又會擴(kuò)展過多的節(jié)點。八數(shù)碼難題的有序搜索樹2023/2/2494、A*算法A*算法的估價函數(shù)：令估價函數(shù)f使得在任意節(jié)點上其函數(shù)值f(n)能估算出從節(jié)點S到節(jié)點n的最小代價路徑的代價與從節(jié)點n到某一目標(biāo)節(jié)點的最小代價路徑的代價之總和，也就是說f(n)是約束通過節(jié)點n的一條最小代價路徑的代價的一個估計。因此，OPEN表上具有最小f值的那個節(jié)點就是所估計的加有最少嚴(yán)格約束條件的節(jié)點，而且下一步要擴(kuò)展這個節(jié)點是合適的。2023/2/250A*算法中幾個有用的記號：令k(ni，nj)表示任意兩個節(jié)點ni和nj之間最小代價路徑的實際代價(對于兩節(jié)點間沒有通路的節(jié)點，函數(shù)k沒有定義)。于是，從節(jié)點n到某個具體的目標(biāo)節(jié)點ti，某一條最小代價路徑的代價可由k(n,ti)給出。令h*(n)表示整個目標(biāo)節(jié)點集合｛ti｝上所有k(n,ti)中最小的一個，因此，h*(n)就是從n到目標(biāo)節(jié)點最小代價路徑的代價，而且從n到目標(biāo)節(jié)點能夠獲得h*(n)的任一路徑就是一條從n到某個目標(biāo)節(jié)點的最佳路徑(對于任何不能到達(dá)目標(biāo)節(jié)點的節(jié)點n，函數(shù)h*沒有定義)。2023/2/251

通常感興趣的是想知道從已知起始節(jié)點S到任意節(jié)點n的一條最佳路徑的代價k(S,n)。為此，引進(jìn)一個新函數(shù)g*，這將使引入的記號得到某些簡化。對所有從S開始可達(dá)到n的路徑來說，函數(shù)g*定義為

g*(n)=k(S,n)2023/2/252

因而f*(n)值就是從S開始約束通過節(jié)點n的一條最佳路徑的代價，而f*(S)=h*(S)是一條從S到某個目標(biāo)節(jié)點中間無約束的一條最佳路徑的代價。

其次，定義函數(shù)f*，使得在任一節(jié)點n上其函數(shù)值f*(n)就是從節(jié)點S到節(jié)點n的一條最佳路徑的實際代價加上從節(jié)點n到某目標(biāo)節(jié)點的一條最佳路徑的代價之和，即

f*(n)=g*(n)+h*(n)2023/2/253希望估價函數(shù)f是f*的一個估計，此估計可由下式給出：

f(n)=g(n)+h(n)其中：g是g*的估計；h是h*的估計。對于g(n)來說，一個明顯的選擇就是搜索樹中從S到n這段路徑的代價，這一代價可以由從n到S尋找指針時，把所遇到的各段弧線的代價加起來給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價路徑)。這個定義包含了g(n)≥g*(n)。對于h*(n)的估計h(n)，它依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。h叫做啟發(fā)函數(shù)。2023/2/254A算法和A*算法的定義

定義1

在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為A算法。

定義2

在A算法中，如果對所有的x，h(x)≤h*(x)成立,則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。2023/2/255

定義3

采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā?/p>

A*算法是一種有序搜索算法，其特點在于對估價函數(shù)的定義上。對于一般的有序搜索，總是選擇f值最小的節(jié)