【文章內(nèi)容簡介】 題的搜索樹如圖 11所示。深度界限 dm=5。2 8 31 6 47 5S0(a) 初始狀態(tài)1 2 38 47 6 5Sg(b) 目標狀態(tài)圖 10 八數(shù)碼難題28西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院圖 11 八數(shù)碼難題有界深度優(yōu)先搜索樹S01 2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 52 8 3 6 41 7 52 8 3 1 47 6 52 31 8 47 6 52 8 31 4 7 6 5 8 32 6 41 7 52 8 36 41 7 5 8 32 1 47 6 52 8 37 1 4 6 52 31 8 47 6 52 3 1 8 47 6 58 32 6 41 7 52 36 8 41 7 58 32 1 47 6 52 8 36 4 1 7 52 8 36 7 41 5Sg1 2 3 8 47 6 52 8 37 1 46 51 2 38 47 6 51 2 37 8 4 6 58 3 2 6 41 7 58 6 32 41 7 52 36 8 41 7 52 3 6 8 41 7 52 8 6 4 31 7 52 8 36 4 51 72 8 36 7 4 1 52 8 36 7 41 5 2 8 37 1 46 5 2 8 37 46 1 58 3 2 1 47 6 58 1 32 47 6 523 11164 6 12 14 175 7 8 9 13 181529西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院完備性 :在有界深度優(yōu)先搜索算法中，深度界限的選擇很重要。選擇過大，可能會影響搜索的效率；選擇過小，有可能求不到解。對于某些問題，可能它的解就位于某一分支較深的位置，而界限選取的沒有那么大，就會導(dǎo)致找不到問題的解。所以，有界深度優(yōu)先搜索策略是 不完備 的。 五．代價樹的寬度優(yōu)先搜索在前面的搜索算法討論中，沒有考慮搜索的代價問題，即假設(shè)狀態(tài)空間圖中各節(jié)點之間的有向邊的代價都是相同的，且都為一個單位量，也就是說從狀態(tài)空間圖中的任一個狀態(tài)到另一個狀態(tài)轉(zhuǎn)換所付出的代價都是一樣的。由此，在求解一個問題時，所付出的總代價即是從狀態(tài)空間圖的初始節(jié)點達到目標節(jié)點的解30西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院路徑的長度。然而，在實際問題求解中，往往是將一個狀態(tài)變換成另一個狀態(tài)時所付出的操作代價（或費用）是不一樣的，也就是狀態(tài)空間圖中各有向邊的代價是不一樣的。那么應(yīng)該采取何種搜索策略，以保證付出的代價（或費用）是最小呢？像前面所說的一樣，不可能將狀態(tài)空間圖的全部狀態(tài)節(jié)點輸入到計算機，而是僅僅存儲逐步擴展過程種所形成的搜索樹。代價搜索樹 ： 有向邊上標有代價的搜索樹稱為代價搜索樹，簡稱代價樹。 在代價樹種，從節(jié)點 i到其后繼節(jié)點 j的連線之代價記為 C(i,j)，而把從初始節(jié)點 S0到任意節(jié)點 x的路徑代價記為 g(x)，則 g(j)=g(i)+C(i,j)。31西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院代價樹寬度優(yōu)先搜索的 基本思想 是：每次從 OPEN表中選擇一個代價最小的節(jié)點，移入 CLOSED表。因此，每當對一節(jié)點擴展之后，就要計算它的所有后繼節(jié)點的代價，并將它們與OPEN表中已有的待擴展的節(jié)點按代價的大小從小到大依次排序。從而 OPEN表選擇被擴展節(jié)點時即選擇排在最前面的節(jié)點（代價最?。Ｆ渌阉魉惴ㄈ缦拢? 算法 5：代價樹的寬度優(yōu)先搜索算法Step1：把初始節(jié)點 S0放入 OPEN表中，令 g(S0)=0。Step2：如果 OPEN表為空，則問題無解，退出。Step3：把 OPEN表中代價最小的節(jié)點，即排在前端的第一個節(jié)點（即為節(jié)點 n），移入到 CLOSED表中。 32西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院Step4：如果節(jié)點 n是目標節(jié)點，則求得問題的解，退出；否則繼續(xù)。Step5：判斷節(jié)點 n是否可擴展，若不可擴展則轉(zhuǎn)Step2；否則轉(zhuǎn) Step6。Step6：對節(jié)點 n進行擴展，將它們所有的后繼節(jié)點放入 OPEN表中，并對每個后繼節(jié)點 j計算其代價g(j)=g(i)+C(i,j)，為每個后繼節(jié)點設(shè)置指向節(jié)點 n的指針。然后，根據(jù)節(jié)點的代價大小對 OPEN表中的所有節(jié)點進行從小到大的排序。Step7：轉(zhuǎn)向 Step2。代價樹寬度優(yōu)先搜索的框圖如圖 12所示。 33西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院YYNNY開 始把 S0送入 OPEN表，令 g(S0)=0把 OPEN表中的第一個節(jié)點移入 CLOSED表 (記為節(jié)點 n)對節(jié)點 n進行擴展，并對每個后繼節(jié)點 j計算其代價 g(j)=g(i)+C(i,j),并將它們放入 OPEN表，為每個后繼節(jié)點設(shè)置指向 n的指針對 OPEN表中的所有節(jié)點按其代價從小到大排序問題無解，退出OPEN空表嗎？節(jié)點 n為目標節(jié)點嗎？節(jié)點 n可擴展嗎？N成功，退出圖 12 代價樹寬度優(yōu)先搜索算法框圖 34西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院例 4：推銷員旅行問題 假設(shè) A、 B、 C、 D和 E是五個城市，推銷員從城市 A出發(fā)，到達城市 E，走怎樣的路線費用最省？五個城市間的交通圖及每個城市間的旅行費用如圖13所示，圖中的數(shù)字即是旅行費用。解：由于涉及旅行費用，所以利用代價樹寬度優(yōu)先搜索方法求解。為此，首先將旅行交通圖轉(zhuǎn)換為代價樹如圖 14所示。 圖 13 旅行交通圖ABCED610576835西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院轉(zhuǎn)換的方法 如下：從初始節(jié)點 A開始，把與它直接相鄰的節(jié)點作為它的后繼節(jié)點，對其他節(jié)點也作同樣的擴展。但若一個節(jié)點已作為某節(jié)點的前驅(qū)節(jié)點的話，則它就不能再作為該節(jié)點的后繼節(jié)點。例如，與節(jié)點B相鄰的節(jié)點有 A和 D，但由于在代價樹中， A已作為B的前驅(qū)節(jié)點出現(xiàn)，則它就不能再作為 B的后繼節(jié)點。另外，圖中的節(jié)點除了初始節(jié)點 A外，其他的節(jié)點都有可能在代價樹中多次出現(xiàn)，為了區(qū)分它的多次出現(xiàn)，分別用下標 1， 2， … 標出，但它們卻是圖中的同一個節(jié)點。例如， C1和 C2都代表圖中的節(jié)點 C。 利用代價樹的寬度優(yōu)先搜索策略對代價樹進行搜索，可得最優(yōu)解為： A B1 D1 E26 5 636西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院圖 14 旅行交通圖的代價樹AB1 C1C2 E2D2 E1E4D1B2 E36 105 7 87 685 637西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院其代價是 17。因而，從城市 A向城市 E旅行，費用最省得路線為： A→B→D→E六．代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索和寬度優(yōu)先搜索的區(qū)別 ：寬度優(yōu)先搜索法每次從 OPEN表中的全體節(jié)點中選擇代價最小的節(jié)點移入 CLOSED表，并對這一節(jié)點進行擴展或判斷（是否為目標節(jié)點），而深度優(yōu)先搜索法則是從剛剛擴展的節(jié)點之后繼節(jié)點中選擇一個代價最小的節(jié)點移入 CLOSED表，并進行擴展或判斷。代價樹的深度優(yōu)先搜索算法如下 ： 38西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院算法 6：代價樹的深度優(yōu)先搜索算法Step1：把初始節(jié)點 S0放入 OPEN表中。Step2：如果 OPEN表為空，則問題無解，退出。Step3：將 OPEN表中的第一個節(jié)點（代價最小的節(jié)點記為節(jié)點 n）移入到 CLOSED表中。Step4：如果節(jié)點 n是目標節(jié)點，則求得問題的解，退出；否則轉(zhuǎn) Step5。Step5：判斷節(jié)點 n是否可擴展。若不可擴展則轉(zhuǎn)Step2，否則轉(zhuǎn) Step6。Step6：對節(jié)點 n進行擴展，并將其后繼節(jié)點按有向邊代價從小到大排序后放入 OPEN表的前端，并為各后繼節(jié)點設(shè)置指向 n節(jié)點的指針。Step7：轉(zhuǎn)向 Step2。 39西南科技大學(xué)西南科技大學(xué) 信息工程學(xué)院信息工程學(xué)院注意 ： 在 Step6中，對節(jié)點 n的后繼節(jié)點進行排序是按照有向邊代價的大小進行的。代價樹深度優(yōu)先搜索的框圖如圖 15所示。 其原因在于：在深度優(yōu)先搜索中，假設(shè)節(jié)點 n的后繼節(jié)點有 i、 j、 k，則節(jié)點 i、 j、 k的代價分別為： g(i)=g(n)+C(n,i)， g(j)=g(n)+C(n,j)， g(k)=g(n)+C(n,k) 所以， g(i)、 g(j)、 g(k)的大小順序僅由 C(n,i)、C(n,j)