廣度優(yōu)先搜索

1、12.3廣度優(yōu)先搜索廣度優(yōu)先搜索從初始狀態(tài)開始，從初始狀態(tài)開始，應用算符生成第一層狀態(tài)，應用算符生成第一層狀態(tài)，檢查目標狀態(tài)是否在這些后繼狀態(tài)中。若沒有，再檢查目標狀態(tài)是否在這些后繼狀態(tài)中。若沒有，再用算符將所有第一層的狀態(tài)逐一擴展，用算符將所有第一層的狀態(tài)逐一擴展，得到第二層狀態(tài)，得到第二層狀態(tài)，并逐一檢查第二層狀態(tài)中是否包含目標狀態(tài)。并逐一檢查第二層狀態(tài)中是否包含目標狀態(tài)。若沒有，若沒有，再用算符逐一擴展第二層的所有狀態(tài)，再用算符逐

2、一擴展第二層的所有狀態(tài)，…………，如此依次擴展、檢查下去，直至發(fā)現(xiàn)目標狀態(tài)如此依次擴展、檢查下去，直至發(fā)現(xiàn)目標狀態(tài)為止。這就是所謂的廣度優(yōu)先搜索。為止。這就是所謂的廣度優(yōu)先搜索。一、廣度優(yōu)先搜索的基本思路一、廣度優(yōu)先搜索的基本思路在廣度優(yōu)先搜索中，解答樹上狀態(tài)的擴展沿狀態(tài)深度的“斷層”進行，也就是說，狀態(tài)的擴展是按它們接近起始狀態(tài)的程度依次進行的。長度為n1的任一狀態(tài)進行擴展之前，必須先考慮長度為n的每種可能的算符序列。因此，對于同一層

3、狀態(tài)來說，求解問題的價值是相同的。我們可以按任意順序來擴展它們，這里采用的原則是先生成的狀態(tài)先擴展。只要目標狀態(tài)在解答樹的有限層上，廣度優(yōu)先搜索第一次擴展到該狀態(tài)，便保證找到一條通向它的最佳路徑。為了滿足先生成的狀態(tài)先擴展的原則，我們采用隊列的數(shù)據(jù)結構存貯狀態(tài)。隊列是一種線性表，對于它所有的插入都在表尾的一端進行，所有的刪除都在表首的一端進行。如同現(xiàn)實生活中的等車、買票的排隊，新來的成員總是加入隊尾，每次離開的總是隊列頭上的人，即當前“

4、最老”的成員。因此，隊列也被稱為“先進先出表”（FIFO表）。在廣度優(yōu)先搜索中，我們將擴展出的狀態(tài)存貯在一個稱為list的數(shù)組里，數(shù)組容量為listmax。list數(shù)組采用“先進先出”的隊列結構，設兩個指針open、closed，分別是隊尾指針和隊首指針。其中l(wèi)ist[1‥cloed1]存貯已擴展狀態(tài)（即這些狀態(tài)的兒子狀態(tài)已擴展出）；list[cloed‥open]存貯待擴展狀態(tài)（即這些狀態(tài)的兒子狀態(tài)尚待擴展）。當open=closed

5、時，則表示隊列空；當open=listmax時，則表示隊列滿(見上圖)。List數(shù)組的元素為狀態(tài)。typenode=狀態(tài)的數(shù)據(jù)類型varlist：array[1listmax]ofnode；隊列cloed，open：integer；隊首指針和隊尾指針廣度優(yōu)先搜索的算法流程如下：open←1；closed←0；初始狀態(tài)進入隊列l(wèi)ist[open]←初始狀態(tài)；while(closedopen)(open≤listmax)dobegin若隊列

6、非空且未溢出，則移出隊首狀態(tài)，擴展其子狀態(tài)closed←closed1；exp(list[closed])；擴展隊首狀態(tài)的所有子狀態(tài)end；whileifopen≥listmax若擴展出的狀態(tài)數(shù)超出list表的容量上限then輸出內(nèi)存溢出信息else找到了初始狀態(tài)所能到達的所有狀態(tài)list[1]list[open]；采用廣度優(yōu)先搜索的試題一般有兩種類型：⑴求初始狀態(tài)所能到達的所有狀態(tài)⑵求初始狀態(tài)到某目標狀態(tài)的最短路徑顏色碼圖形面積分析：

7、分析：1、圖形定義圖形定義紙中央作坐標原點，過原點作平行于紙兩邊的y軸和x軸。Y軸的坐標區(qū)間為，x軸的坐?????????22bb標區(qū)間為（如下圖）?????????22aa紙上的每一坐標位置看作是一個可涂64種顏色的色點，其面積為單位1。這樣ab的紙即成了一個具有ab個色點的點陣，紙的面積與色點數(shù)相等。設squa—染色矩陣，其中squa[i，j]為（i，j）的色碼（≤i≤，≤j≤，1≤squa[i，j]??????2b??????2b

8、??????2a??????2a≤）??????2bacolhave—顏色標志表，其中colhave[j]為顏色j存在的標志(1≤j≤)；??????2ba我們輸入數(shù)據(jù)的同時構造squa矩陣和colhave表：fill(squa，sizeof(squa)，1)；fi←1tondo依次讀入每個矩形的信息beginfj←1to5do讀nj；讀入矩形i的信息colhave[n5]←true；置顏色n5存在fj←n1ton31do矩形i涂上顏色

9、n5fk←n2ton41dosqua[j，k]←n5；endfsqua矩陣中的每一坐標點(x，y)有8個可能的相鄰點，位于不同方向。(如上圖(b))中圓圈內(nèi)的數(shù)字表征這8個方向。括號(△yi，△xi)為方向i的相鄰點(y’，x’)與(y，x)的垂直增量和水平增量(1≤i≤8)2、圖形面積的計算方法、圖形面積的計算方法按顏色碼遞增順序搜索每一種顏色。每搜索一種顏色i(1≤i≤64)時，若colhave表中存在該顏色，則按順序搜索squa矩