人工智能ppt課件搜索問題

第一部分問題求解用搜索法對(duì)問題求解問題求解算法描述：?jiǎn)栴}實(shí)例：玩具世界與現(xiàn)實(shí)世界問題搜索求解性能的度量*無信息的搜索策略*有信息的搜索和探索*對(duì)抗搜索（與或圖搜索）高級(jí)搜索第一部分問題求解用搜索法對(duì)問題求解1

第二部分知識(shí)表示與推理謂詞邏輯與歸結(jié)原理

命題邏輯謂詞邏輯*歸結(jié)原理

Herbrand定理知識(shí)表示

知識(shí)概述*產(chǎn)生式表示語義網(wǎng)絡(luò)表示框架表示其他表示方法

第二部分知識(shí)表示與推理謂詞邏輯與歸結(jié)原理2第三部分人工智能高級(jí)專題基于模型的診斷配置問題智能規(guī)劃調(diào)度第三部分人工智能高級(jí)專題基于模型的診斷3搜索算法把問題作為輸入，并以行動(dòng)序列的形式返回問題的解。一旦找到一個(gè)解，那么它所建議的行動(dòng)就可以付諸實(shí)施，這被稱為執(zhí)行階段。因而我們可以對(duì)問題求解算法進(jìn)行設(shè)計(jì)，即“形式化、搜索、執(zhí)行”問題的形式化：一個(gè)問題可以形式化地定義為四個(gè)組成部分：初始狀態(tài)；可能的行動(dòng)的描述。最常見的形式化是使用一個(gè)后繼函數(shù)。給定一個(gè)特殊的狀態(tài)x，Successor(x)返回一個(gè)由有序?qū)?lt;action,successor>（〈行動(dòng)，后繼〉）組成的集合，其中每個(gè)行動(dòng)都是狀態(tài)x下的合法行動(dòng)之一，每個(gè)后繼都是行動(dòng)后從狀態(tài)x能夠達(dá)到的狀態(tài)。定義明確的問題及解搜索算法把問題作為輸入，并以行動(dòng)序列的形式返回問題的解。一旦4總之，初始狀態(tài)和它的后繼函數(shù)隱含的定義了問題的狀態(tài)空間----即從初始狀態(tài)可以達(dá)到的所有狀態(tài)的集合。狀態(tài)空間形成一個(gè)圖，其中節(jié)點(diǎn)是狀態(tài)，節(jié)點(diǎn)之間的弧就是行動(dòng)，狀態(tài)空間中的一條路徑就是通過行動(dòng)序列連接起來的一個(gè)狀態(tài)序列。目標(biāo)測(cè)試，用來確定當(dāng)前狀態(tài)是不是目標(biāo)狀態(tài)。路徑耗散函數(shù)為每條路徑分配一個(gè)數(shù)值化的耗散值。問題求解算法選擇能反映它自己性能度量的耗散函數(shù)。上述四個(gè)元素定義了一個(gè)問題，可以把它們集合在一起成為一個(gè)單一的數(shù)據(jù)結(jié)構(gòu)，作為問題求解算法的輸入。問題的解就是從初始狀態(tài)到目標(biāo)狀態(tài)的路徑。解的優(yōu)劣由路徑耗散函數(shù)度量，而最優(yōu)解是所有的解里路徑耗散值最小的解。總之，初始狀態(tài)和它的后繼函數(shù)隱含的定義了問題的狀態(tài)空間---5前面用初始狀態(tài)、后繼函數(shù)、目標(biāo)測(cè)試和路徑耗散來表示問題，這種形式化表示是合理的，不過它忽略了現(xiàn)實(shí)世界的許多方面，去除表示中細(xì)節(jié)的過程被稱為抽象化，而去除表示中細(xì)節(jié)的描述稱為問題形式化。前面用初始狀態(tài)、后繼函數(shù)、目標(biāo)測(cè)試和路徑耗散來表示問題，這種6問題實(shí)例玩具世界與現(xiàn)實(shí)世界問題我們首先來看一個(gè)八數(shù)碼游戲初始狀態(tài)目標(biāo)狀態(tài)它包括一個(gè)3X3的棋盤，棋盤上擺放著8個(gè)寫有數(shù)字的棋子，留下一個(gè)空位。與空位相鄰的棋子可以滑入到空位中。游戲的目的是要達(dá)到一個(gè)特定的目標(biāo)狀態(tài)。7245683112356784問題實(shí)例玩具世界與現(xiàn)實(shí)世界問題初始狀態(tài)目標(biāo)狀態(tài)它包括一個(gè)3X77245683172456831724568317245683172456831初始狀態(tài)行動(dòng)描述12356784目標(biāo)測(cè)試和計(jì)算路徑消耗搜索和執(zhí)行7245683172456831724568317245688標(biāo)準(zhǔn)的形式化如下：狀態(tài)；描述了指定8個(gè)棋子中的每一個(gè)以及空位在棋盤的9個(gè)方格上的分布。初始狀態(tài)：任何狀態(tài)都可以指定為初始狀態(tài)。注意要到達(dá)任何一個(gè)給定的目標(biāo)，可能的初始狀態(tài)中恰好只有一半可以作為初始狀態(tài)。后繼函數(shù)：用來產(chǎn)生通過四個(gè)行動(dòng)（把空位向Left，right,Up或Down)能夠達(dá)到的合法狀態(tài)。目標(biāo)測(cè)試：用來檢測(cè)狀態(tài)是否是目標(biāo)狀態(tài)。路徑耗散：設(shè)每一步的耗散值是1因此整個(gè)路徑的耗散值是路徑中的步數(shù)。這里的抽象化只保留了游戲規(guī)則相關(guān)的描述，而忽略所有物理操作的細(xì)節(jié)。標(biāo)準(zhǔn)的形式化如下：9八數(shù)碼游戲?qū)儆诨靻栴}家族，這類問題經(jīng)常被用作AI中新的搜索算法的測(cè)試問題。這類一般問題已知為NP完全問題，因此對(duì)這類問題不要期望在最壞情況下找到好于我們后面要講述的算法。八數(shù)碼游戲共有9！/2=181440個(gè)可達(dá)到的狀態(tài)，這是很容易求解的。15數(shù)碼問題則大約有1.3萬億個(gè)狀態(tài)，用最好的搜索算法最優(yōu)化地求解一個(gè)隨機(jī)的實(shí)例需要幾毫秒。24數(shù)碼游戲則大約有1025個(gè)狀態(tài)，用目前的機(jī)器和最優(yōu)化算法求解隨機(jī)的實(shí)例仍是相當(dāng)困難的。四皇后問題在一個(gè)4×4的國(guó)際象棋棋盤上，一次一個(gè)地?cái)[布四枚皇后棋子，擺好后要滿足每行、每列和對(duì)角線上只允許出現(xiàn)一枚棋子，即棋子間不許相互俘獲。如圖其中a，b滿足目標(biāo)條件，c，d，e為不合法狀態(tài)，即不可能構(gòu)成滿足目標(biāo)條件的中間勢(shì)態(tài)。八數(shù)碼游戲?qū)儆诨靻栴}家族，這類問題經(jīng)常被用作AI中新的搜索10四皇后問題的幾個(gè)狀態(tài)盡管對(duì)于這個(gè)問題和整個(gè)n皇后問題家族存在有效的專用算法，這類問題對(duì)于搜索算法仍然是個(gè)有趣的測(cè)試問題。形式化主要有兩類：一類是增量形式化，包括了增加狀態(tài)描述的算符，從空狀態(tài)開始：對(duì)于四皇后問題意味著每次行動(dòng)添加一個(gè)皇后到狀態(tài)中去。另一類是完全狀態(tài)形式化，4個(gè)皇后都在棋盤上開始，然后移動(dòng)它們。四皇后問題的幾個(gè)狀態(tài)盡管對(duì)于這個(gè)問題和整個(gè)n皇后問題家族存在11增量形式化如下：狀態(tài)：把0到4個(gè)皇后放棋盤上的任何安排都是一個(gè)狀態(tài)。初始狀態(tài)；棋盤上沒有皇后。后繼函數(shù)；把一個(gè)皇后添加到棋盤上的任何空格。目標(biāo)測(cè)試：4個(gè)皇后都在棋盤上，并且互相攻擊不到。在這個(gè)形式化中，我們需要調(diào)查16X15X14X13個(gè)可能的序列。更好的形式化方法是禁止把一個(gè)皇后放到任何可能被攻擊的格子里：狀態(tài)：擺放n個(gè)皇后(0n4)的安排，要求最左側(cè)n列里每一列一個(gè)皇后，保證沒有一個(gè)皇后能攻擊另一個(gè)。后繼函數(shù)：把一個(gè)皇后添加到最左側(cè)空列的任何格子內(nèi)，只要該格子未被其他皇后攻擊。這樣的形式化把四皇后問題的狀態(tài)空間從4萬多降到3。增量形式化如下：12如果是八皇后呢？在這個(gè)形式化中，需要調(diào)查64X63X…X573X1014個(gè)狀態(tài)狀態(tài)：擺放n個(gè)皇后(0n8)的安排，要求最左側(cè)n列里每一列一個(gè)皇后，保證沒有一個(gè)皇后能攻擊另一個(gè)。后繼函數(shù)：把一個(gè)皇后添加到最左側(cè)空列的任何格子內(nèi)，只要該格子未被其他皇后攻擊。這樣的形式化把四皇后問題的狀態(tài)空間從3X1014降到2057，解就容易找到了。對(duì)于100個(gè)皇后，初始的形式化約有10400個(gè)狀態(tài)，而用改進(jìn)的形式化方法約有1052個(gè)狀態(tài)這是一個(gè)相當(dāng)大的縮減，但是仍然太大。我們以后將給出一個(gè)簡(jiǎn)單算法，可以處理百萬皇后問題。如果是八皇后呢？13現(xiàn)實(shí)世界問題我們已經(jīng)看到尋徑問題是如何根據(jù)特定的位置和沿它們之間的連接進(jìn)行轉(zhuǎn)移而定義的。尋徑問題在實(shí)際中有許多應(yīng)用。諸如計(jì)算機(jī)網(wǎng)絡(luò)的路由、軍事行動(dòng)的規(guī)劃、生產(chǎn)調(diào)度問題、排課問題，以及飛機(jī)航線旅行規(guī)劃系統(tǒng)等等。這些問題都是典型的描述起來復(fù)雜的問題?？紤]一個(gè)飛機(jī)航線旅行問題的簡(jiǎn)化例子，設(shè)定如下：狀態(tài)：每個(gè)狀態(tài)由位置（例如機(jī)場(chǎng)）和當(dāng)前的時(shí)間來表示。初始狀態(tài)：由具體問題而定。后繼函數(shù)：返回的狀態(tài)是下列因素的結(jié)果：乘坐的航班，起飛時(shí)刻距當(dāng)前時(shí)刻的時(shí)間差加上從當(dāng)前機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)所需要的飛行時(shí)間。目標(biāo)測(cè)試：我們是否在某個(gè)預(yù)定的時(shí)刻到達(dá)目的地？路徑耗散：取決于金錢的花費(fèi)、等待的時(shí)間、飛行時(shí)間、過海關(guān)和入境的過程、座位的質(zhì)量、一天中的哪個(gè)時(shí)間段、飛機(jī)類型、飛行?？偷睦锍酞?jiǎng)等?，F(xiàn)實(shí)世界問題我們已經(jīng)看到尋徑問題是如何根據(jù)特定的位置和沿它們14商業(yè)旅行建議系統(tǒng)使用了這種問題形式化的方法，同時(shí)要考慮很多附加的復(fù)雜因素以應(yīng)付航空公司強(qiáng)加的繁復(fù)的收費(fèi)結(jié)構(gòu)。然而，任何經(jīng)常作飛機(jī)的乘客都知道并不是所有的飛行旅行都能夠按計(jì)劃順利進(jìn)行。好的系統(tǒng)應(yīng)該包括應(yīng)急計(jì)劃。旅行問題與尋徑問題有很近的關(guān)系，但是有很重要的不同。例如多個(gè)城市之間的旅行問題，從長(zhǎng)春出發(fā)到其他19個(gè)城市中的每一個(gè)至少一次最后在回到出發(fā)地這樣一個(gè)問題。如尋徑一樣，行動(dòng)還是對(duì)應(yīng)臨近城市之間的旅行。然而，狀態(tài)空間就不一樣了。每個(gè)狀態(tài)不僅必須包括當(dāng)前所在的位置，還必須包括已經(jīng)訪問過的城市。因此初始狀態(tài)可能是“in長(zhǎng)春;visited{長(zhǎng)春}，一個(gè)中間狀態(tài)可能是”in上海；visited{長(zhǎng)春，沈陽、上海}“，而目標(biāo)測(cè)試應(yīng)該是檢測(cè)是否在長(zhǎng)春并且已經(jīng)訪問過所有的20個(gè)城市。其他實(shí)際問題商業(yè)旅行建議系統(tǒng)使用了這種問題形式化的方法，同時(shí)要考慮很多附15解的搜索在對(duì)一些問題形式化之后，我們現(xiàn)在開始考慮如何對(duì)它們求解，這是通過在狀態(tài)空間中的搜索完成的。下面討論的搜索技術(shù)使用顯式的搜索樹，搜索樹是由初始狀態(tài)和后繼函數(shù)共同生成的，同時(shí)也定義了狀態(tài)空間。下圖是一個(gè)簡(jiǎn)化的羅馬尼亞道路圖解的搜索在對(duì)一些問題形式化之后，我們現(xiàn)在開始考慮如何對(duì)它們求16OradeaZerind7175AradTimisoara118111Lugol7075MehadiaDobreta151140Sibiu80Rimnicu120146Craiova99Fagaras97138Pitesti101211Giurgiu90Bucharest85Neamt87lasi92Vastui142Urziceni98Hirsova86Eforic一個(gè)簡(jiǎn)化的羅馬尼亞道路圖OradeaZerind7175AradTimisoara117下圖顯示了為尋找從Arad到Bucharest的路徑對(duì)搜索樹進(jìn)行的某些擴(kuò)展AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea初始狀態(tài)下圖顯示了為尋找從Arad到Bucharest的路徑對(duì)搜索樹18AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea擴(kuò)展Arad之后AradSibiutimisoaraZerindAradFa19AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea擴(kuò)展Sibiu之后AradSibiutimisoaraZerindAradFa20非形式化算法Tree-Search1.根據(jù)問題初始狀態(tài)初始化搜索樹；2.While(不滿足結(jié)束條件時(shí)){2.1If(沒有可擴(kuò)展的結(jié)點(diǎn))返回失敗信息；2.2根據(jù)某種策略選擇一個(gè)可擴(kuò)展葉子結(jié)點(diǎn)；2.3If（當(dāng)前結(jié)點(diǎn)滿足目標(biāo)狀態(tài)）返回解的信息；Else將該結(jié)點(diǎn)（可擴(kuò)展結(jié)點(diǎn)）加入到搜索樹中；｝該算法如何進(jìn)行優(yōu)化？非形式化算法Tree-Search1.根據(jù)問題初始狀態(tài)初始化21搜索樹中節(jié)點(diǎn)的表示有多種方式，不過我們可以假設(shè)節(jié)點(diǎn)是一個(gè)包含五個(gè)要素的數(shù)據(jù)結(jié)構(gòu)：狀態(tài)：狀態(tài)空間中與該方法相對(duì)應(yīng)的格局；父節(jié)點(diǎn)：搜索樹中生成該節(jié)點(diǎn)的節(jié)點(diǎn)；行動(dòng)：由父節(jié)點(diǎn)產(chǎn)生該節(jié)點(diǎn)所采取的操作；路徑耗散（成本）：從初始狀態(tài)到該節(jié)點(diǎn)的路徑耗散，一般記為g(n)，路徑有父指針表示；深度：從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)路徑上的步數(shù)。節(jié)點(diǎn)與狀態(tài)的區(qū)別？搜索樹中節(jié)點(diǎn)的表示有多種方式，不過我們可以假設(shè)節(jié)點(diǎn)是一個(gè)包含2272456831父節(jié)點(diǎn)節(jié)點(diǎn)狀態(tài)行動(dòng)=Right深度=3路徑耗散=3節(jié)點(diǎn)產(chǎn)生構(gòu)造搜索樹的數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都具有父節(jié)點(diǎn)，狀態(tài)和各種記錄域，圖中箭頭是由子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。72456831父節(jié)點(diǎn)節(jié)點(diǎn)狀態(tài)行動(dòng)=Right深度=3路徑耗23度量問題求解的性能完備性：當(dāng)問題有解時(shí)，這個(gè)算法是否能保證找到一個(gè)解？空間復(fù)雜度：執(zhí)行搜索的過程中需要多少內(nèi)存？時(shí)間復(fù)雜度：找到一個(gè)解需要花費(fèi)多少長(zhǎng)時(shí)間？最優(yōu)性：該搜索策略是否能找到最優(yōu)解？度量問題求解的性能完備性：當(dāng)問題有解時(shí)，這個(gè)算法是否能保證找24時(shí)間和空間的復(fù)雜性度量往往要與問題難度的某種度量一起考慮，在理論計(jì)算機(jī)科學(xué)中，一個(gè)典型的度量是狀態(tài)空間的大小。因?yàn)闋顟B(tài)空間圖被視為要輸入到搜索程序的顯示數(shù)據(jù)結(jié)構(gòu)。在AI中，狀態(tài)空間圖是由初始狀態(tài)和后繼函數(shù)隱含地表示的，經(jīng)常是無限的，它的復(fù)雜度根據(jù)下列三個(gè)值來表達(dá)：B，分支因子；d，最淺的目標(biāo)節(jié)點(diǎn)的深度；m，狀態(tài)空間中任何路徑的最大長(zhǎng)度。時(shí)間復(fù)雜度一般根據(jù)搜索過程中產(chǎn)生的節(jié)點(diǎn)數(shù)目來度量，而空間復(fù)雜度則根據(jù)在內(nèi)存中存儲(chǔ)的最大節(jié)點(diǎn)個(gè)數(shù)來度量。時(shí)間和空間的復(fù)雜性度量往往要與問題難度的某種度量一起考慮，在25無信息搜索無信息搜索算法是經(jīng)典計(jì)算機(jī)科學(xué)(Horowitz和Sahni,1978)和運(yùn)籌學(xué)（Dreyfus,1969)的一個(gè)中心話題，1988年Gallo和Pallottino給出了相關(guān)問題的綜述文章。搜索問題回溯策略圖搜索策略無信息圖搜索：廣度優(yōu)先、代價(jià)一致搜索、深度優(yōu)先、深度有限搜索、迭代深入深度優(yōu)先搜索、雙向搜索、無信息搜索策略的比較、避免重復(fù)狀態(tài)。無信息搜索無信息搜索算法是經(jīng)典計(jì)算機(jī)科學(xué)(Horowitz和26人類的思維過程，可以看作是一個(gè)搜索的過程。從小學(xué)到現(xiàn)在，你也許遇到過很多種智力游戲問題，比如說傳教士和野人問題：有3個(gè)傳教士和3個(gè)野人來到河邊準(zhǔn)備過河，河岸有一條船，每次至多可供2人乘坐。問傳教士為安全起見，應(yīng)如何規(guī)劃擺渡方案，使得任何時(shí)候，在船上與河的兩岸野人數(shù)目總是不超過傳教士數(shù)目（但允許在河的某一側(cè)只有野人而沒有傳教士）？如果要做這個(gè)智力游戲，在每一次渡河之后，都會(huì)有幾種渡河方案供你選擇，究竟哪種方案才有利于在滿足題目所規(guī)定的約束條件下順利過河呢？這就是搜索問題。搜索問題人類的思維過程，可以看作是一個(gè)搜索的過程。從小學(xué)到現(xiàn)在，27經(jīng)過反復(fù)努力和試探，你終于找到了一種解決方法。在你高興之余，你可能馬上會(huì)想到，這個(gè)辦法所用的步驟是否最少？也就是說，它是最優(yōu)的嗎？如果不是，如何才能找到最優(yōu)的辦法？你是學(xué)過計(jì)算機(jī)程序設(shè)計(jì)的學(xué)生，你考慮過在計(jì)算機(jī)上又如何實(shí)現(xiàn)這樣的搜索？這些問題就是我們要學(xué)習(xí)的內(nèi)容。經(jīng)過反復(fù)努力和試探，你終于找到了一種解決方法。在你高興28一般而言，很多問題求解過程可以轉(zhuǎn)化為狀態(tài)空間的搜索問題。比如，前面講過的傳教士與野人問題，當(dāng)用在河左岸的傳教士人數(shù)、野人人數(shù)和船的情況表示問題時(shí)，該問題的初始狀態(tài)可以用三元組表示為（3，3，1），結(jié)束狀態(tài)可以表示為（0，0，0），而中間狀態(tài)可以表示為（2，2，0）、（3，2，1）、（3，0，0）…等，每個(gè)三元組對(duì)應(yīng)了三維空間上的一個(gè)點(diǎn)。而問題的解，則是一個(gè)合法狀態(tài)的序列，其中序列的第一個(gè)狀態(tài)是問題的初始狀態(tài)，而最后一個(gè)狀態(tài)則是問題的結(jié)束狀態(tài)，介于它們之間的是中間狀態(tài)。除了第一個(gè)狀態(tài)外，該序列中任何狀態(tài)都可以通過一條規(guī)則由與它相鄰的前一個(gè)狀態(tài)轉(zhuǎn)換得到。下頁(yè)的圖給出了一個(gè)搜索問題的示意圖。含義是如何在一個(gè)比較大的問題空間中，只通過搜索比較小的范圍，就找到問題的解。尋找這樣的序列過程稱為搜索。一般而言，很多問題求解過程可以轉(zhuǎn)化為狀態(tài)空間的搜索問題29人工智能ppt課件搜索問題30搜索方法從搜索方式上來講，搜索可以劃分為兩大類，即盲目搜索和啟發(fā)式搜索。

所謂盲目搜索，就是未利用問題的知識(shí)，采用固定的方式生成狀態(tài)的方法。顯然這種方法的搜索效率是低下的，但方法具有通用性。當(dāng)一時(shí)難以找到求解問題的有效知識(shí)時(shí)，是一種不得不采用的方法。

所謂啟發(fā)式搜索，與盲目搜索正好相反，它利用問題的知識(shí)，縮小問題的搜索范圍，選擇那些最有可能在（最優(yōu)）解路徑上的狀態(tài)優(yōu)先搜索，以盡快地找到問題的（最優(yōu)）解。由于利用了問題的有關(guān)知識(shí)，一般來說，搜索效率會(huì)有所提高。但如何找到對(duì)求解問題有幫助的知識(shí)，以及如何利用這些知識(shí)，是問題的關(guān)鍵所在。

搜索方法從搜索方式上來講，搜索可以劃分為兩大類，即盲目搜索和31到目前為止，在人工智能領(lǐng)域中已提出許多具體的搜索方法，概括起來有：

（1）求任一解路的搜索策略

回溯法（Backtracking）

爬山法（HillClimbing）

寬度優(yōu)先法（Breadth-first）

深度優(yōu)先法（Depth-first）

限定范圍搜索法（BeamSearch）好的優(yōu)先法（Best-first）

（2）求最佳解路的搜索策略

大英博物館法（BritishMuseum）

分枝界限法（BranchandBound）

動(dòng)態(tài)規(guī)劃法（DynamicProgramming）

最佳圖搜索法（A﹡）

（3）求與或關(guān)系解圖的搜索法

一般與或圖搜索法（AO﹡）

極小極大法（Minimax）

α－β剪枝法（Alpha-betaPruning）

啟發(fā)式剪枝法（HeuristicPruning）

今后對(duì)其中幾個(gè)基本搜索策略作進(jìn)一步的討論。

到目前為止，在人工智能領(lǐng)域中已提出許多具體的搜索方法，概括起32無信息的搜索策略這部分無信息搜索（也稱為盲目搜索）主要包括廣度優(yōu)先搜索、代價(jià)一致搜索、深度優(yōu)先搜索、深度有限搜索和迭代深度優(yōu)先搜索和雙向搜索幾種。以下我們分別進(jìn)行講述和對(duì)比。廣度優(yōu)先搜索：它是一種簡(jiǎn)單的搜索策略，首先擴(kuò)展根節(jié)點(diǎn)，接下來擴(kuò)展根節(jié)點(diǎn)的所有后繼，然后再擴(kuò)展它們的后繼，依此類推。一般來講，在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上當(dāng)前層的所有節(jié)點(diǎn)都已經(jīng)擴(kuò)展完。1959年Moore最早使用廣度優(yōu)先搜索形式化并解決迷宮問題。廣度優(yōu)先搜索可以調(diào)用函數(shù)TREE-SEARCH來實(shí)現(xiàn)，該函數(shù)以一個(gè)空的邊緣為參數(shù)，而邊緣是一個(gè)先進(jìn)先出(FIFO)隊(duì)列，保證先訪問的節(jié)點(diǎn)先擴(kuò)展。這意味著淺層的節(jié)點(diǎn)會(huì)在深層節(jié)點(diǎn)之前被擴(kuò)展。無信息的搜索策略這部分無信息搜索（也稱為盲目搜索）主要包括廣33一個(gè)簡(jiǎn)單二叉樹的搜索過程ABFCGEDABFCGEDABFCGEDABFCGED在每一個(gè)階段，下一個(gè)要擴(kuò)展的節(jié)點(diǎn)由箭頭指示出來。一個(gè)簡(jiǎn)單二叉樹的搜索過程ABFCGEDABFCGEDABFC34廣度優(yōu)先搜索算法的評(píng)價(jià)從完備性和最優(yōu)性來看我們很容易知道廣度優(yōu)先搜索是完備的——如果最淺的目標(biāo)節(jié)點(diǎn)處于一個(gè)有限的深度d，廣度優(yōu)先搜索在擴(kuò)展完比它淺的所有節(jié)點(diǎn)（假設(shè)分支因子b是有限的）后最終能找到這個(gè)目標(biāo)節(jié)點(diǎn)。但最淺的目標(biāo)不一定是最優(yōu)的目標(biāo)節(jié)點(diǎn)：從技術(shù)上講，如果路徑耗散是節(jié)點(diǎn)深度的非遞減函數(shù)，廣度優(yōu)先算法才是最優(yōu)的。廣度優(yōu)先搜索算法的評(píng)價(jià)從完備性和最優(yōu)性來看從技術(shù)上講，如果路35從時(shí)間和空間復(fù)雜性來看我們考慮一個(gè)假想的狀態(tài)空間，狀態(tài)空間中每個(gè)狀態(tài)都有b個(gè)后繼。這樣搜索樹的根節(jié)點(diǎn)生成第一層的b個(gè)子節(jié)點(diǎn)，每個(gè)子節(jié)點(diǎn)又生成b個(gè)子節(jié)點(diǎn)，在第二層共有b2個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)中的每一個(gè)又生成b個(gè)子節(jié)點(diǎn)，如此類推，假設(shè)解的深度為d，在最壞情況下，我們將擴(kuò)展d層除了最后一個(gè)節(jié)點(diǎn)外的所有節(jié)點(diǎn)（因?yàn)槟繕?biāo)節(jié)點(diǎn)本身尚未被擴(kuò)展），那么在d+1層會(huì)產(chǎn)生bd+1-b個(gè)節(jié)點(diǎn)，

這時(shí)已經(jīng)生成的節(jié)點(diǎn)數(shù)是多少？b+b2+b3+…+bd+(bd+1-b)=O(bd+1)每個(gè)生成的節(jié)點(diǎn)都必須保存在內(nèi)存中，因?yàn)樗仁沁吘壒?jié)點(diǎn)的一部分又是邊緣節(jié)點(diǎn)的祖先，因此該算法的時(shí)間復(fù)雜度和空間復(fù)雜度相等（再加上一個(gè)根節(jié)點(diǎn)）。從時(shí)間和空間復(fù)雜性來看b+b2+b3+…+bd+(bd+1-36廣度優(yōu)先搜索時(shí)間與空間復(fù)雜度分析深度節(jié)點(diǎn)數(shù)時(shí)間數(shù)內(nèi)存211000.11秒1Mbit下圖是分支因子b=10的時(shí)候廣度優(yōu)先搜索到不同的解深度d所需要的時(shí)間和空間開銷，并假定每秒生成10000個(gè)節(jié)點(diǎn)，并且存儲(chǔ)一個(gè)節(jié)點(diǎn)需要1k字節(jié)。4111,10011秒106M610719分鐘10G810931小時(shí)1T(KG)101011129天101T12101335年10P(KT)1410153523年1E(KP)廣度優(yōu)先搜索時(shí)間與空間復(fù)雜度分析深度節(jié)點(diǎn)數(shù)37從上圖我們可以得到兩個(gè)結(jié)論：第一個(gè)結(jié)論，在廣度優(yōu)先搜索算法中內(nèi)存的需求是比執(zhí)行時(shí)間消耗更大的問題。第二個(gè)結(jié)論，時(shí)間需求仍是個(gè)主要因素。一般來講，除最小的實(shí)例外指數(shù)級(jí)復(fù)雜度的搜索問題不能用無信息的方法解決。從上圖我們可以得到兩個(gè)結(jié)論：38代價(jià)一致搜索當(dāng)所有單步消耗相等時(shí)，廣度優(yōu)先搜索是最優(yōu)的，因?yàn)樗鼈兛偸菙U(kuò)展深度最淺的未擴(kuò)展節(jié)點(diǎn)。但代價(jià)一致搜索擴(kuò)展的是路徑消耗最低的節(jié)點(diǎn)n。

在什么條件下廣度優(yōu)先搜索與代價(jià)一致搜索相同？代價(jià)一致搜索時(shí)對(duì)一條路徑的步數(shù)并不關(guān)心，而只是關(guān)心所經(jīng)步驟總的耗散。因此若擴(kuò)展到一個(gè)具有能返回同一狀態(tài)的零耗散行動(dòng)的節(jié)點(diǎn)時(shí)會(huì)陷入無限循環(huán)，造成不完備性。若每一步的耗散都大于等于某個(gè)最小的正常數(shù)時(shí)，能夠保證其完備性與最優(yōu)性。沿著路徑的耗散總是增加的，因此第一個(gè)被擴(kuò)展的目標(biāo)節(jié)點(diǎn)就是最優(yōu)解（記住，算法只對(duì)被選中擴(kuò)展的節(jié)點(diǎn)進(jìn)行目標(biāo)測(cè)試）。代價(jià)一致搜索當(dāng)所有單步消耗相等時(shí)，廣度優(yōu)先搜索是最優(yōu)的，因?yàn)?9代價(jià)一致算法的度量代價(jià)一致搜索由路徑的耗散引導(dǎo)而不是深度，因此它的復(fù)雜度不能簡(jiǎn)單地使用b和d來刻畫。我們使用C*表示最優(yōu)解的耗散值，并且假定每個(gè)行動(dòng)的耗散至少為。那么算法的時(shí)間和空間復(fù)雜度為，要比bd大得多。為什么？什么條件下一廣度優(yōu)先算法復(fù)雜度一樣？我們學(xué)過代價(jià)一致的搜索嗎？代價(jià)一致算法的度量代價(jià)一致搜索由路徑的耗散引導(dǎo)而不是深度，因40深度優(yōu)先搜索深度優(yōu)先搜索總是擴(kuò)展搜索樹的當(dāng)前邊緣中最深的節(jié)點(diǎn)，搜索直接推進(jìn)到搜索樹的最深層，那里的節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)。當(dāng)那些節(jié)點(diǎn)被擴(kuò)展完之后，它們被從邊緣中去掉，然后搜索算法“向上回到”下一個(gè)還有未擴(kuò)展后繼節(jié)點(diǎn)的稍淺的節(jié)點(diǎn)。

在搜索算法Tree-Search中采用什么策略能夠使搜索過程按照深度優(yōu)先進(jìn)行？深度優(yōu)先搜索深度優(yōu)先搜索總是擴(kuò)展搜索樹的當(dāng)前邊緣中最深的節(jié)點(diǎn)41ABFCGEDHIJKLMNOABFCGEDHIJKLMNOOABFCGEDHIJKLMNABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNO42ABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNO43深度優(yōu)先搜索對(duì)內(nèi)存的需求很少，它只需要存儲(chǔ)一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑，以及該路徑上每個(gè)節(jié)點(diǎn)的所有未被擴(kuò)展的兄弟節(jié)點(diǎn)即可。一旦一個(gè)節(jié)點(diǎn)被擴(kuò)展，當(dāng)它的所有后代都被擴(kuò)展和這個(gè)節(jié)點(diǎn)從內(nèi)存中刪除。因此，對(duì)上面的搜索圖，若分支因子為b，最大深度為m的狀態(tài)空間，深度優(yōu)先搜索只需要存儲(chǔ)bm+1個(gè)節(jié)點(diǎn)。與廣度優(yōu)先相同假設(shè)下，并且假設(shè)與目標(biāo)節(jié)點(diǎn)在同一深度的節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)，我們看到在深度d=12時(shí)深度優(yōu)先搜索只需要118k字節(jié)而不是10P字節(jié)，節(jié)省了大約百億倍的空間。深度優(yōu)先搜索的缺點(diǎn)是它有可能錯(cuò)誤地選擇一條分支并且沿著一條很長(zhǎng)（甚至是無限的）路徑一直走下去，而如果做出不同的選擇則可能引導(dǎo)對(duì)樹根節(jié)點(diǎn)附近的解進(jìn)行搜索。深度優(yōu)先搜索對(duì)內(nèi)存的需求很少，它只需要存儲(chǔ)一條從根節(jié)點(diǎn)到葉節(jié)441初始化。取圖中任意結(jié)點(diǎn)s(G={s})作為初始結(jié)點(diǎn)將其賦值到OPEN表，CLOSED表置空。2循環(huán)執(zhí)行以下語句直至找到解或OPEN表為空2.1n=first(OPEN);2.2IFGOAL(n)return(SUCCESS)；算法結(jié)束；2.3REMOVE(n,OPEN)，ADD(n,CLOSE);2.4EXPAND(n)->{mi};G=ADD(mi,G);2.5ADD(mj,OPEN),并標(biāo)記mj到n的指針；把不在OPEN或CLOSE中的結(jié)點(diǎn)放在OPEN表的最前面，使?jié)舛却蟮慕Y(jié)點(diǎn)可優(yōu)先擴(kuò)展。深度優(yōu)先搜索算法的框架1初始化。取圖中任意結(jié)點(diǎn)s(G={s})作為初始結(jié)點(diǎn)將其賦45深度有限搜索前面我們看到，深度優(yōu)先搜索雖然占用的內(nèi)存比較小，但這種算法不是完備的也不是最優(yōu)的。為此，我們可以通過對(duì)深度優(yōu)先搜索提供一個(gè)預(yù)先設(shè)定的的深度限制l來解決，就是說深度為l的節(jié)點(diǎn)被當(dāng)作沒有后繼的節(jié)點(diǎn)對(duì)待，這種辦法稱為深度有限搜索。對(duì)深度限制解決了無窮路徑問題。但問題是如果我們選擇的l<d，那么它又引入了一種不完備性問題。同樣如果我們選擇的l>d的話，搜索也不是最優(yōu)的，深度優(yōu)先可以看作深度有限的一種特殊情況。那么如何來優(yōu)化這種方法呢？深度有限搜索可以通過對(duì)一般的樹搜索算法或者遞歸深度優(yōu)先搜索算法進(jìn)行簡(jiǎn)單的修改來實(shí)現(xiàn)。即對(duì)深度限制l不斷進(jìn)行迭代更新。深度有限搜索前面我們看到，深度優(yōu)先搜索雖然占用的內(nèi)存比較小，46迭代深入搜索迭代深入搜索（或迭代深入深度優(yōu)先搜索）是一個(gè)用來尋找最合適的深度限制的通用策略，它經(jīng)常與深度優(yōu)先搜索結(jié)合使用。做法是不斷地增大深度限制----首先為0，接著為1，然后是2，依此類推----直到找到目標(biāo)節(jié)點(diǎn)。但深度限制達(dá)到d，即最淺的目標(biāo)節(jié)點(diǎn)的深度時(shí)，就找到目標(biāo)節(jié)點(diǎn)，下面的圖給出了算法的搜索過程，該算法結(jié)合了深度優(yōu)先和廣度優(yōu)先搜索的優(yōu)點(diǎn)，它的空間和深度優(yōu)先搜索需求一樣小，為O(bd)。它和廣度優(yōu)先搜索一樣當(dāng)分支因子有限時(shí)是完備的，當(dāng)路徑耗散是節(jié)點(diǎn)深度的非遞減函數(shù)時(shí)是最優(yōu)的。迭代深入搜索迭代深入搜索（或迭代深入深度優(yōu)先搜索）是一個(gè)用來47AL=0AABCL=1ABCABCABCABFCGEDL=2ABFCGEDABFCGEDAL=0AABCL=1ABCABCABCABFCGEDL=248ABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDAB49ABFCGEDHIJKLMNOL=3ABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDIJKLMNOHABFCGEDJKLMNOHIIABFCGEDJKLMNOHABFCGEDHIJKLMNOL=3ABFCGEDHIJKL50IABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJ51迭代深入搜索也許看起來比較浪費(fèi)，因?yàn)橛行顟B(tài)被多次生成。但實(shí)際上代價(jià)不是很大。原因在于一棵每層的分支因子都相同（或相近）的搜索樹中，底層節(jié)點(diǎn)（深度d)只被生成一次，倒數(shù)第二層的節(jié)點(diǎn)生成兩次。依此類推，一直到根節(jié)點(diǎn)的子節(jié)點(diǎn)，它被生成d次。因此生成的總節(jié)點(diǎn)數(shù)為(d+1)b0+db+(d-1)b2+…+2bd-1+bd，時(shí)間復(fù)雜度是O(bd)。與廣度優(yōu)先生成的節(jié)點(diǎn)數(shù)相比，它沒有生成d+1層的節(jié)點(diǎn)而廣度優(yōu)先可能會(huì)生成一些d+1層的節(jié)點(diǎn)，因此它比廣度優(yōu)先搜索要快。比如b=10,d=5，迭代深入搜索生成50+400+3000+20000+100000=123450個(gè)節(jié)點(diǎn)，而廣度優(yōu)先搜索生成10+100+1000+10000+100000+999990=1111110個(gè)節(jié)點(diǎn)。迭代深入搜索也許看起來比較浪費(fèi)，因?yàn)橛行顟B(tài)被多次生成。但實(shí)52迭代深入搜索的性質(zhì)完備嗎?是時(shí)間復(fù)雜性?

(d+1)b0+db1+(d-1)b2+…+bd=O(bd)空間復(fù)雜性?

O(bd)最優(yōu)性?是,ifstepcost=1迭代深入搜索的性質(zhì)完備嗎?是53雙向搜索雙向搜索的思想是同時(shí)進(jìn)行兩個(gè)方向的搜索，一個(gè)從初始狀態(tài)向目標(biāo)狀態(tài)進(jìn)行，另一個(gè)從目標(biāo)狀態(tài)向初始狀態(tài)搜，動(dòng)機(jī)的產(chǎn)生的節(jié)點(diǎn)是bd/2+bd/2要比bd小得多，即兩個(gè)小圓的面積之和比起點(diǎn)為中心達(dá)到目標(biāo)的大圓面積大得多。雙向搜索最吸引人的地方是時(shí)間復(fù)雜度的降低，但實(shí)際上如何從目標(biāo)向初始狀態(tài)搜并不容易。雙向搜索雙向搜索的思想是同時(shí)進(jìn)行兩個(gè)方向的搜索，一個(gè)從初始狀54幾種算法的比較標(biāo)準(zhǔn)廣度優(yōu)先代價(jià)一致深度優(yōu)先深度限制迭代深入完備性是是否否是時(shí)間

O(bd+1)O(b[C*/])O(bm)O(bl)O(bd)空間

O(bd+1)O(b[C*/])O(bm)O(bl)O(bd)最優(yōu)性是是否否是幾種算法的比較標(biāo)準(zhǔn)廣度優(yōu)先代價(jià)一致55回溯策略回溯策略屬于盲目搜索的一種。所謂回溯策略，簡(jiǎn)單地說是這樣一種策略：首先將規(guī)則給出一個(gè)固定的排序，在搜索時(shí)，對(duì)當(dāng)前狀態(tài)（搜索開始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測(cè)每一條規(guī)則，在當(dāng)前狀態(tài)未使用過的規(guī)則中找到第一條可觸發(fā)規(guī)則，被應(yīng)用于當(dāng)前狀態(tài)，得到的新狀態(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索。如果當(dāng)前狀態(tài)無規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過仍未找到問題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前狀態(tài)。重復(fù)以上搜索，直到找到問題的解，或者試探了所有可能后仍找不到問題的解為止?；厮莶呗曰厮莶呗詫儆诿つ克阉鞯囊环N。所謂回溯策略，簡(jiǎn)單地說是56回溯策略可以有多種實(shí)現(xiàn)的方法，其中用遞歸法實(shí)現(xiàn)也許是最簡(jiǎn)單的方法了，本書中給出的就是這種算法。

對(duì)于初次接觸遞歸程序設(shè)計(jì)或者對(duì)遞歸程序設(shè)計(jì)不熟悉的同學(xué)，對(duì)這段算法也許不容易理解。在這里對(duì)遞歸程序設(shè)計(jì)的思想做一個(gè)通俗易懂的介紹。對(duì)遞歸程序設(shè)計(jì)熟悉的同學(xué)可以略過。

以C語言為例，我們?cè)趯懸粋€(gè)函數(shù)時(shí)，一般是用其他已經(jīng)有的函數(shù)（系統(tǒng)提供的庫(kù)函數(shù)或者自己已經(jīng)定義好的自定義函數(shù)）來定義該函數(shù)。而遞歸程序設(shè)計(jì)則是在定義一個(gè)函數(shù)時(shí)“自己調(diào)用自己”（直接的，或者間接的），比如定義abc這個(gè)函數(shù)，如果寫成這樣的形式：

回溯策略可以有多種實(shí)現(xiàn)的方法，其中用遞歸法實(shí)現(xiàn)也許是最簡(jiǎn)單的57intabc(intn)

{

……

abc(m);

……

}

則abc是一個(gè)遞歸調(diào)用，因?yàn)槲覀冊(cè)诙xabc這個(gè)函數(shù)時(shí)，同時(shí)也用到了abc這個(gè)函數(shù)，這就是所謂的"自己調(diào)用自己"。

intabc(intn)

{

……

abc(m);

……58

其實(shí)我們?cè)缇?遇到"過遞歸了。在大家小的時(shí)候，都聽過那個(gè)"從前有座山……"的故事吧？

"從前有座山，山里有個(gè)廟，廟里有個(gè)和尚正在講故事，講的什么故事呢？講的是從前有座山，山里有個(gè)廟，廟里有個(gè)和尚正在講故事，講的什么故事呢？講的是從前有座山，山里有個(gè)廟，廟里有個(gè)和尚正在講故事，講的什么故事呢？講的是……"

這就是一個(gè)典型的遞歸。不過這個(gè)遞歸永遠(yuǎn)也不會(huì)結(jié)束，是一種"死遞歸"。但是我們大家誰也沒有"永遠(yuǎn)"將這個(gè)故事聽下去。因?yàn)楫?dāng)滿足一定的條件時(shí)，比如講故事的人口干舌燥不想講了，故事也就結(jié)束了。這雖然是一個(gè)一點(diǎn)也不動(dòng)聽的故事，但它確實(shí)是一個(gè)故事。這里的"口干舌燥"就是遞歸的一個(gè)結(jié)束條件，正是由于有了這個(gè)條件，才使得遞歸結(jié)束。

其實(shí)我們?cè)缇?遇到"過遞歸了。在大家小的時(shí)候，都聽過那個(gè)"59考察這個(gè)故事，有兩個(gè)特點(diǎn)，一是有一個(gè)簡(jiǎn)單的結(jié)束條件，如這里的“口干舌燥”；二是每一次遞歸調(diào)用，都使得問題--在這里就是故事--距離結(jié)束近了一些。比如第二次講“從前有座山”時(shí)，就比第一次講“從前有座山”時(shí)距離故事結(jié)束近。正是這兩點(diǎn)，構(gòu)成了遞歸程序設(shè)計(jì)的兩個(gè)要點(diǎn)。考察這個(gè)故事，有兩個(gè)特點(diǎn)，一是有一個(gè)簡(jiǎn)單的結(jié)束條件，如這里的60下面舉一個(gè)簡(jiǎn)單的C＋＋程序例子，在這個(gè)例子中，利用遞歸求解一個(gè)鏈表的長(zhǎng)度。structLIST//定義一個(gè)簡(jiǎn)單的鏈表結(jié)構(gòu){Tdtat;structLIST*pNext;};intListLenght(LIST*pList)

//遞歸定義函數(shù)ListLenght

//函數(shù)的功能是求解給定鏈表的長(zhǎng)度

{

if(pList==NULL)return0;

//遞歸的結(jié)束條件，一個(gè)空的鏈表長(zhǎng)度定義為0

elsereturnListLenght(pList->pNext)+1;

//遞歸調(diào)用

//將求鏈表pList的長(zhǎng)度問題，變換為求解pList->pNext的長(zhǎng)度問題

//pList的長(zhǎng)度等于pList->pNext的長(zhǎng)度+1

}下面舉一個(gè)簡(jiǎn)單的C＋＋程序例子，在這個(gè)例子中，利用遞歸求解一61遞歸過程BACKTRACK（DATA）

①IFTERM（DATA），RETURNNIL；TERM取真即找到目標(biāo)，則過程返回空表NIL。

②IFDEADEND（DATA），RETURNFAIL；DEADEND取真，即該狀態(tài)不合法，則過程返回FAIL，必須回溯。

③RULES：＝APPRULES（DATA）；APPRULES計(jì)算DATA的可應(yīng)用規(guī)則集，依某種原則（任意排列或按啟發(fā)式準(zhǔn)則）排列后賦給RULES。

④LOOP：IFNULL（RULES），RETURNFAIL；NULL取真，即規(guī)則用完未找到目標(biāo)，過程返回FAIL，必須回溯。

⑤R：＝FIRST（RULES）；取頭條可應(yīng)用規(guī)則。

⑥RULES：＝TAIL（RULES）；刪去頭條規(guī)則，減少可應(yīng)用規(guī)則表的長(zhǎng)度。

⑦RDATA：＝GEN（R，DATA）；調(diào)用規(guī)則R作用于當(dāng)前狀態(tài)，生成新狀態(tài)。

⑧PATH：＝BACKTRACK（RDATA）；對(duì)新狀態(tài)遞歸調(diào)用本過程。

⑨IFPATH＝FAIL，GOLOOP；當(dāng)PATH＝FAIL時(shí)，遞歸調(diào)用失敗，則轉(zhuǎn)移調(diào)用另一規(guī)則進(jìn)行測(cè)試。

⑩RETURNCONS（R，PATH）；過程返回解路徑規(guī)則表（或局部解路徑子表）。遞歸過程BACKTRACK（DATA）

①IFTERM（D62下面對(duì)這個(gè)算法作幾點(diǎn)說明。首先解釋一下其中的變量、常量、謂詞、函數(shù)等符號(hào)的意義。變量符號(hào)DATA、RULE