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