【文章內(nèi)容簡介】 x 4 = 1? ?? ?21 3 圖搜索術(shù)語 amp。方法分類 ? 窮舉搜索（盲目搜索） 是對圖的最基本的搜索算法，是蠻力策略的一種表現(xiàn)形式。即不考慮給定問題的特有性質(zhì)，按事先定好的順序，依次運(yùn)用規(guī)則，盲目搜索的方法。 ? 啟發(fā)式搜索 是利用一些啟發(fā)信息，提前判斷出先搜索哪些狀態(tài)可能盡快找到問題的解或某些情況不可能取到最優(yōu)解，從而可以提前舍棄對這些狀態(tài)的嘗試。即考慮給定問題的特有性質(zhì)，選用合適的細(xì)則，提高搜索的效率。 ? 搜索分為兩大類： 隱含地檢查所有可能情況 22 3 圖搜索術(shù)語 amp。方法分類 ? 問題狀態(tài) :樹中的每一個(gè)結(jié)點(diǎn)確定所求解問題的一個(gè)問題狀態(tài)。 ? 狀態(tài)空間 :由根結(jié)點(diǎn)到其它結(jié)點(diǎn)的所有路徑（分支），就確定了這個(gè)問題的狀態(tài)空間。 ? 解狀態(tài) :是這樣一些問題狀態(tài) S，對于這些問題狀態(tài)，由根到 S的那條路徑確定了該解空間中的一個(gè)元組。 ? 答案狀態(tài) :是這樣一些解狀態(tài) S，對于這些解狀態(tài)而言，由根到 S的這條路徑確定了這問題的一個(gè)解（即它滿足隱式約束條件）。 ? 狀態(tài)空間樹 :解空間的樹結(jié)構(gòu)，又稱隱式圖。 23 3 圖搜索術(shù)語 amp。方法分類 ? 活結(jié)點(diǎn)： 如果已生成一個(gè)結(jié)點(diǎn)而它的所有兒子結(jié)點(diǎn)還沒有全部生成，則這個(gè)結(jié)點(diǎn)叫做活結(jié)點(diǎn)。 ? E結(jié)點(diǎn)： 當(dāng)前正在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)叫 E結(jié)點(diǎn)（正在擴(kuò)展的結(jié)點(diǎn)）。 ? 死結(jié)點(diǎn) ： 不再進(jìn)一步擴(kuò)展或者其兒子結(jié)點(diǎn)已全部生成的結(jié)點(diǎn)就是死結(jié)點(diǎn) 。 24 3 圖搜索術(shù)語 amp。方法分類 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● …… …… …… ? n皇后問題 ? 要在 n*n的國際象棋棋盤中放 n個(gè)皇后，使任意兩個(gè)皇后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對角線的任意棋子。求所有的解。 問題狀態(tài) 狀態(tài)空間 解狀態(tài) 答案狀態(tài) ● ● ● ● ● ● ● 25 二、廣度優(yōu)先搜索 ? 1 圖的廣度優(yōu)先遍歷 /搜索算法 ? 2 廣度優(yōu)先搜索的應(yīng)用 ? 例 求經(jīng)過城市最少的路線問題 ? 例 走迷宮問題 26 1 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索 ? 首先訪問出發(fā)點(diǎn) V，接著依次訪問 V的所有鄰接點(diǎn){Wi}，再依次訪問分別與 {Wi}鄰接的所有未曾訪問過的頂點(diǎn)， …… ，直至與 V相通的頂點(diǎn)都已訪問，若此時(shí)還有未訪問的頂點(diǎn)，則按相同的過程繼續(xù)。 ? 活結(jié)點(diǎn)的擴(kuò)展是按先來先處理的原則進(jìn)行。 ―先被訪問的頂點(diǎn)”的鄰接點(diǎn)先于“后被 ……‖ 被訪問 V1 V2 V4 V5 V3 V7 V6 V8 27 1 廣度優(yōu)先搜索 算法要素 ? 廣度優(yōu)先搜索：活結(jié)點(diǎn)的擴(kuò)展是按先來先處理的原則進(jìn)行；但搜索過程中還需暫時(shí)保存部分活結(jié)點(diǎn)。 ? 在算法中用“隊(duì)”來存儲(chǔ)每個(gè) E結(jié)點(diǎn)擴(kuò)展出的活結(jié)點(diǎn)。實(shí)際應(yīng)用中，用數(shù)組或鏈表實(shí)現(xiàn)隊(duì)列。 ? 開辟數(shù)組 visited[ ]記錄結(jié)點(diǎn)的搜索情況。 28 2 廣度優(yōu)先搜索 算法的基本思路 ? 算法設(shè)計(jì)的基本步驟 ? 1）確定圖的存儲(chǔ)方式； ? 2）圖的遍歷過程中的操作，其中包括為輸出問題解而進(jìn)行的存儲(chǔ)操作； ? 3）輸出問題的結(jié)論。 29 1 廣度優(yōu)先搜索 一般算法 ? 圖的搜索的不同實(shí)現(xiàn) ? 圖：鄰接表 /鄰接矩陣 ? 隊(duì)列：鏈表 /數(shù)組 ? 機(jī)制：遞歸 /非遞歸 ? 廣度優(yōu)先搜索用非 遞歸實(shí)現(xiàn)方便。 //從頂點(diǎn) v 開始的廣度優(yōu)先搜索 把頂點(diǎn) v標(biāo)記為已到達(dá)頂點(diǎn)； 初始化隊(duì)列 Q，其中僅包含一個(gè)元素 v。 while (Q不空 ) { 從隊(duì)列中刪除頂點(diǎn) w。 令 u 為鄰接于 w 的頂點(diǎn) 。 while (u) { if ( u 尚未被標(biāo)記 ) { 把 u 加入隊(duì)列； 把 u 標(biāo)記為已到達(dá)頂點(diǎn)； } u = 鄰接于 w 的下一個(gè)頂點(diǎn)； } } 30 1 廣度優(yōu)先搜索 鄰接表表示圖的算法 int visited[n]。 //n 為結(jié)點(diǎn)個(gè)數(shù) bfs(int k,graph head[]) { int i。 queue Q。 edgenode *p。 //定義隊(duì)列 InitQueue(Q)； //隊(duì)列初始化 print(―visit vertex‖,k)。 visited[k]=1。 //訪問源點(diǎn) vk EnQueue(Q,k)。 //vk已訪問，將其入隊(duì) while(!QueueEmpty(Q)) //隊(duì)非空則執(zhí)行 { i=DeQueue(Q)。 // vi出隊(duì)為 E結(jié)點(diǎn) p=head[i].firstedge。 //取 vi的邊表頭指針 while(pnull) //擴(kuò)展 E結(jié)點(diǎn) { if(visited[padjvex]=0) //若 vj未訪問過 { print (―visit vertex‖,padjvex)。//訪問 vj visited[padjvex]=1。 EnQueue(Q,padjvex)。 } //訪問過的 vj入隊(duì) p=pnext。 } //找 vi的下一鄰接點(diǎn) } 31 1 廣度優(yōu)先搜索 鄰接矩陣表示圖的算法 bfsm(int k, graph g[][100],int n) { int i,j。queue Q。 InitQueue(Q)。 print (―visit vertex‖, k)。 //訪問源點(diǎn) vk visited[k]=1。 EnQueue(Q,k)。 while(not QueueEmpty(Q)) { i=DeQueue(Q)。 //vi出隊(duì) for(j=0。jGn。j++) //擴(kuò)展結(jié)點(diǎn) if(g[i][j]==1 and visited[j]=0) { print(―visit vertex‖,j)。