1、.實(shí)驗一：盲目搜索算法一、實(shí)驗?zāi)康恼莆彰つ克阉魉惴ㄖ坏膶挾葍?yōu)先搜索求解算法的基本思想。對于寬度優(yōu)先搜索算法基本過程，算法分析有一個清晰的思路，了解寬度優(yōu)先搜索算法在實(shí)際生活中的應(yīng)用。二、實(shí)驗環(huán)境PC機(jī)一臺，VC+6.0 三、實(shí)驗原理寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。同時，寬度優(yōu)先搜索算法是連通圖的一種遍歷策略。因為它的思想是從一個頂點(diǎn)V0開始，輻射狀

2、地優(yōu)先遍歷其周圍較廣的區(qū)域，故得名。其基本思想是：(1) 把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解答)。(2) 如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3) 把第一個節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點(diǎn)表中。(4) 擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。(5) 把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。(6) 如果n的任一個后繼節(jié)點(diǎn)是個目標(biāo)節(jié)點(diǎn)，則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。寬度優(yōu)先搜索示意圖和寬度優(yōu)先算法流程圖如下圖1和圖2所示：SBADCEFGHIJ圖1、寬度優(yōu)

3、先搜索示意圖起始 把S放入OPEN表Fangru OPEN是否為空表?否是失敗把第一個節(jié)點(diǎn)n,從OPEN表移出,并把它放入CLOSED表擴(kuò)展n,把它的后繼節(jié)點(diǎn)放入OPEN表的末端,提供回到n的指針是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)?否是成功圖2、寬度優(yōu)先算法流程圖四、實(shí)驗數(shù)據(jù)及步驟 這部分內(nèi)容是通過一個實(shí)例來對寬度優(yōu)先算法進(jìn)行一個演示，分析其思想。問題描述了迷宮問題的出路求解辦法。定義一個二維數(shù)組：intmaze55=0，1，0，0，0，0，1，0，1，0，0，0，0，0，0，0，1，1，1，0，0，0，0，1，0，; 它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著

4、走，要求編程序找出從左上角到右下角的最短路線。題目保證了輸入是一定有解的。 下面我們隊問題進(jìn)行求解：對應(yīng)于題目的輸入數(shù)組：0，1，0，0，0，0，1，0，1，0，0，0，0，0，0，0，1，1，1，0，0，0，0，1，0，我們把節(jié)點(diǎn)定義為(y，x)，(y，x)表示數(shù)組maze的項mazexy。于是起點(diǎn)就是(0，0)，終點(diǎn)是(4，4)。我們大概梳理一遍：初始條件：起點(diǎn)Vs為(0，0)，終點(diǎn)Vd為(4，4)，灰色節(jié)點(diǎn)集合Q=，初始化所有節(jié)點(diǎn)為白色節(jié)點(diǎn)，說明：初始全部都是白色（未訪問），即將搜索起點(diǎn)（灰色），已經(jīng)被搜索過了（黑色）。開始我們的寬度搜索。執(zhí)行步驟：1.起始節(jié)點(diǎn)Vs變成灰色，加入隊列Q，

5、Q=(0，0)2.取出隊列Q的頭一個節(jié)點(diǎn)Vn，Vn=0，0，Q=3.把Vn=0，0染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn)(1，0)4.不包含終點(diǎn)(4，4)，染成灰色，加入隊列Q，Q=(1，0)5.取出隊列Q的頭一個節(jié)點(diǎn)Vn，Vn=1，0，Q=6.把Vn=1，0染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn)(2，0)7.不包含終點(diǎn)(4，4)，染成灰色，加入隊列Q，Q=(2，0)8.取出隊列Q的頭一個節(jié)點(diǎn)Vn，Vn=2，0，Q=9.把Vn=2，0染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn)(2，1)，(3，0)10.不包含終點(diǎn)(4，4)，染成灰色，加入隊列Q，Q=(2，1)，(3，0)11.取出隊列Q的頭一個節(jié)點(diǎn)Vn

6、，Vn=2，1，Q=(3，0)12. 把Vn=2，1染成黑色，取出Vn所有相鄰的白色節(jié)點(diǎn)(2，2)13.不包含終點(diǎn)(4，4)，染成灰色，加入隊列Q，Q=(3，0)，(2，2)14.持續(xù)下去，知道Vn的所有相鄰的白色節(jié)點(diǎn)中包含了(4，4)15.此時獲得最終答案我們來看看廣度搜索的過程中節(jié)點(diǎn)的順序情況：圖3迷宮問題的搜索樹圖中標(biāo)號即為我們搜索過程中的順序，我們觀察到，這個搜索順序是按照上圖的層次關(guān)系來的，例如節(jié)點(diǎn)(0，0)在第1層，節(jié)點(diǎn)(1，0)在第2層，節(jié)點(diǎn)(2，0)在第3層，節(jié)點(diǎn)(2，1)和節(jié)點(diǎn)(3，0)在第3層。我們的搜索順序就是第一層-第二層-第三層-第N層這樣子。我們假設(shè)終點(diǎn)在第N層，因

7、此我們搜索到的路徑長度肯定是N，而且這個N一定是所求最短的。我們用簡單的反證法來證明：假設(shè)終點(diǎn)在第N層上邊出現(xiàn)過，例如第M層，MN，那么我們在搜索的過程中，肯定是先搜索到第M層的，此時搜索到第M層的時候發(fā)現(xiàn)終點(diǎn)出現(xiàn)過了，那么最短路徑應(yīng)該是M，而不是N了。所以根據(jù)廣度優(yōu)先搜索的話，搜索到終點(diǎn)時，該路徑一定是最短的。五、實(shí)驗核心代碼/* * 廣度優(yōu)先搜索*/void course(char *maze,int hang,int lie)int i=1,j=1,n=-1;step *Step; /定義一個存儲行走路線的棧Step=new step hang*lie; if(maze11=1)cout

8、此路無法行走!endlendl;getchar();exit(0);elsen+;mazeij=.;/.表示入口Stepn.x=i; /記錄入口的坐標(biāo)Stepn.y=j;while(mazehanglie!=.) /1表示走不通，+表示已經(jīng)走過但不通又回來的路徑，.表示已經(jīng)走過并通了的路徑if(mazeij+1!=1&mazeij+1!=.&mazeij+1!=+)/向右走mazeij+1=.;j=j+1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向右走到: (i,j)endl;else if(mazei+1j!=1&mazei+1j!=.&mazei+1j!=+)/向下

9、走mazei+1j=.;i=i+1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向下走到: (i,j)endl;else if(mazeij-1!=1&mazeij-1!=.&mazeij-1!=+)/向左走mazeij-1=.;j=j-1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向左走到: (i,j)endl;else if(mazei-1j!=1&mazei-1j!=.&mazei-1j!=+)/向上走mazei-1j=.;i=i-1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向上走到: (i,j)endl;else if(

10、mazei+1j+1!=1&mazei+1j+1!=.&mazei+1j+1!=+)/向右下走mazei+1j+1=.;j=j+1;i=i+1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向右下走到: (i,j)endl;else if(mazei+1j-1!=1&mazei+1j-1!=.&mazei+1j-1!=+)/向右上走mazei+1j-1=.;j=j+1;i=i-1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向右上走到: (i,j)endl;else if(mazei-1j+1!=1&mazei-1j+1!=.&mazei-1j+1!=+)

11、/向左下走mazei-1j+1=.;j=j-1;i=i+1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向左下走到: (i,j)endl;else if(mazei-1j-1!=1&mazei-1j-1!=.&mazei-1j-1!=+)/向左上走mazei-1j-1=.;j=j-1;i=i-1;n+;Stepn.x=i;Stepn.y=j;cout第n步: 向左上走到: (i,j)endl;else /返回上一步if(i=1&j=1) /當(dāng)回到入口時，說明無通路，結(jié)束循環(huán)break;elsemazeij=+; /將走不通的點(diǎn)置為+n-;i=Stepn.x; j=Stepn.y; cout此路不通!返回至上一步: (i,j)endl; /輸出返回信息 if(i=hang&j=lie)cout成功走到出口! 共n步;outway(maze,hang,lie,