廣度和深度優(yōu)先搜索

《廣度和深度優(yōu)先搜索》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、◆2深度優(yōu)先搜索和廣度優(yōu)先搜索——產(chǎn)生式系統(tǒng)深度優(yōu)先搜索和廣度優(yōu)先搜索一、產(chǎn)生式系統(tǒng)首先通過(guò)一個(gè)具體事例說(shuō)明什么是產(chǎn)生式系統(tǒng)。[例題4-1八數(shù)碼難題]在3X3的棋盤上，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字。棋盤中留有一個(gè)空格?？崭裰車钠遄涌梢砸频娇崭裰小Ｒ蠼獾膯?wèn)題是：找到一種移動(dòng)方法，實(shí)現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變。例如輸入：（代表從前一布局到后一布局）283164705123804765[分析]狀態(tài)表示：用二維數(shù)組來(lái)表示布局。(si,sj)表示第i行、第j列上放的棋子數(shù)字?？崭裼?表示。產(chǎn)生規(guī)則：

2、原規(guī)則規(guī)定空格周圍的棋子可以向空格移動(dòng)。但如果換一種角度觀察，也可看做空格向四周移動(dòng)。這樣處理更便于編程。如果空格位置在(si,sj)，則有四條規(guī)則：(1)空格向上移動(dòng):Ifsi-1>=1thench(si,sj):=ch(si-1,sj);ch(si-1,sj):=0(2)空格向下移動(dòng):Ifsi+1<=3thench(si,sj):=ch(si+1,sj);ch(si+1,sj):=0(3)空格向左移動(dòng):Ifsj-1>=1thench(si,sj):=ch(si,sj-1);ch(si,sj-1):=0(4)

3、空格向右移動(dòng):Ifsj+1<=3thench(si,sj):=ch(si,sj+1);ch(si,sj+1):=0搜索策略：(1)把初始狀態(tài)作為當(dāng)前狀態(tài)；(2)從當(dāng)前狀態(tài)出發(fā)，運(yùn)用四條移動(dòng)規(guī)則，產(chǎn)生新的狀態(tài)；(3)判斷新的狀態(tài)是否達(dá)到目的狀態(tài)，如果是，轉(zhuǎn)(5)；(4)把新的狀態(tài)記錄下來(lái)，取出下一個(gè)中間狀態(tài)作為當(dāng)前狀態(tài)，返回(2)；(5)輸出從初始狀態(tài)到目標(biāo)狀態(tài)的路徑，結(jié)束。這個(gè)例子就是產(chǎn)生式系統(tǒng)。產(chǎn)生式系統(tǒng)的組成：產(chǎn)生式系統(tǒng)是由三個(gè)基本要素組成的：一個(gè)綜合數(shù)據(jù)庫(kù)（GOLBLEDATABASE），一組產(chǎn)生式規(guī)則（

4、Setofrules），和一個(gè)控制系統(tǒng)（ControlSystem）。1、綜合數(shù)據(jù)庫(kù):它是產(chǎn)生式系統(tǒng)所有的主要數(shù)據(jù)結(jié)構(gòu)。它主要表示問(wèn)題的狀態(tài)，即初始狀態(tài)，目標(biāo)狀態(tài)，和中間狀態(tài)等，以及狀態(tài)之間的關(guān)系。它不是固定不變的，在求解過(guò)程中，它的內(nèi)容將越來(lái)越多，狀態(tài)之間的關(guān)系也越來(lái)越復(fù)雜。經(jīng)常用來(lái)表示數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)有串，集合，數(shù)組，樹，表，記錄，隊(duì)列等。[例題4-1八數(shù)碼難題]使用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)表示狀態(tài)，若壓縮數(shù)據(jù)存儲(chǔ)，把二維數(shù)組壓縮為串，則數(shù)據(jù)庫(kù)采用的數(shù)據(jù)結(jié)構(gòu)就是串。2、產(chǎn)生式規(guī)則：是對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作的一系列規(guī)則。規(guī)

5、則的一般形式是：if條件then操作即滿足應(yīng)用的先決條件后，就對(duì)數(shù)據(jù)庫(kù)實(shí)行后面的操作。3、控制策略：它規(guī)定了操作的順序既在什么條件下用什么規(guī)則進(jìn)行操作，什么條件下停止操作，即它規(guī)定了問(wèn)題的搜索策略和路線。一般的，控制策略分為兩大類：3.1不可撤回方式(IRREVOCABLE)3.2試探法(TENTATIVE)：3.2.1回溯法(BACKTRACKING)3.2.2圖搜索法(GRAPH-SEARCH)4、搜索策略：搜索策略有兩種基本方式：一種是不考慮給定問(wèn)題的特有性質(zhì)，按事先規(guī)定好的順序依次運(yùn)用規(guī)則，這是一種盲目

6、搜索的方法，或稱為無(wú)信息引導(dǎo)的搜索。另一種是考慮問(wèn)題的特有性質(zhì)，優(yōu)先選用較合適的數(shù)據(jù)和規(guī)則，這稱為啟發(fā)式搜索，或有信息引導(dǎo)的搜索。目前，從這兩種基本方式出發(fā)，已創(chuàng)造出多種具體的搜索方法。歸納起來(lái)有以下幾種：◆2深度優(yōu)先搜索和廣度優(yōu)先搜索——產(chǎn)生式系統(tǒng)(一)求任一路徑的搜索策略：回朔法(Backtracking)、爬山法(Hillclimbing)、深度優(yōu)先搜索法(Depth-first)、廣度優(yōu)先搜索法(Breadth-first)、限定范圍搜索法(Beamsearch)、最優(yōu)策略(Bestfirst)(二)求

7、最優(yōu)路徑的搜索策略：大英博物館法(BritishMuseum)、分支定界法(BranchandBound)、動(dòng)態(tài)規(guī)劃法(DynamicProgramming)、最佳圖搜索法(A*)(三)與或圖搜索法：一般與或圖搜索法(AO*)、極大極小法(Minimax)、a-b剪枝法(Alpha-betaPruning)、啟發(fā)式剪枝法(HeuristicPurning)產(chǎn)生式系統(tǒng)的應(yīng)用[例題4—2]有N枚硬幣(N為偶數(shù))正面朝上排成一排，每次將N—1枚硬幣翻過(guò)來(lái)放在原位置上，不斷地重復(fù)上述過(guò)程，直到最后全部硬幣翻成反面朝上為

8、止。編程讓計(jì)算機(jī)把翻幣的最簡(jiǎn)過(guò)程及翻幣次數(shù)打印出來(lái)(用x代表正面，O代表反面)。[分析]狀態(tài)表示：顯然可以用一個(gè)數(shù)組a描述當(dāng)前的狀態(tài)，當(dāng)元素a[i]=“*”時(shí)，第i枚硬幣朝上，a[i]=“o”時(shí)，第i枚硬幣朝下。移動(dòng)規(guī)則：根據(jù)題意每次翻動(dòng)N—1枚硬幣，相當(dāng)于固定一枚硬幣，把其他各枚硬幣翻個(gè)。所以每次有n種操作方案：固定第i{i∈1．．n}枚硬幣，使其他硬幣翻面。搜索策略：把初始狀態(tài)(即