廣度優(yōu)先搜索

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

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

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

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

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

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

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

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

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