盲目搜索啟發式搜索

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

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

1）搜索按規定的路線進行，不使用與問題有關的啟發性信息。

2）適用于其狀態空間圖是樹狀結構的一類問題。131、寬度優先搜索

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

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

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

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

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

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

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

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

例如：寬度優先搜索用于八數碼難題。這個問題就是要把初始棋局變為如下目標棋局的問題：

搜索樹上的所有節點都標記它們所對應的狀態描述，每個節點旁邊的數字表示節點擴展的順序(按順時針方向移動空格)。圖中最后一個節點是目標節點。19八數碼難題的寬度優先搜索樹

2620對應動態演示圖212、深度優先搜索基本思想：從初始節點S開始，在其子節點中選擇一個節點進行考察，若不是目標節點，則再在該子節點中選擇一個節點進行考察，一直如此向下搜索。當到達某個子節點，且該子節點既不是目標節點又不能繼續擴展時，才選擇其兄弟節點進行考察。2023/2/222

深度優先搜索示意圖

2023/2/223

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

定義節點的深度如下：

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

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

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

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

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

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

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

(6)如果后繼節點中有任一個為目標節點，則求得一個解，成功退出；否則，轉向(2)。有界深度優先搜索2023/2/227算法動態演示圖

2023/2/228

例如：按深度優先搜索生成八數碼難題搜索樹，設置深度界限為5。

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

2023/2/230二、啟發式搜索

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

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

啟發信息進行搜索技術一般需要某些有關具體問題領域特性的、與具體問題求解過程有關的、并可指導搜索過程朝著最有希望方向前進的控制信息，把此種信息叫做啟發信息。

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

特點：重排OPEN表，選擇最有希望的節點加以擴展種類：最佳優先搜索、A*算法等2023/2/2331、啟發式搜索策略

啟發信息按其用途可分為3種：

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

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

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

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

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

一般形式：

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

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

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

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

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

有序搜索算法框圖

2023/2/242

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

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

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

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

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

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

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

f*(n)=g*(n)+h*(n)2023/2/253希望估價函數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)，它依賴于有關問題的領域的啟發信息。h叫做啟發函數。2023/2/254A算法和A*算法的定義

定義1

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

定義2

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

定義3

采用h*(x)的下界h(x)為啟發函數的A算法，稱為A*算法。當h=0時，A*算法就變為有序搜索算法。

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