人工智能導(dǎo)論課件第4章第1-2節(jié)

1、人工智能導(dǎo)論Introduction to artificial intelligence人工智能導(dǎo)論Introduction to artifici第4章 搜索算法第4章 搜索算法【導(dǎo)讀案例】AI能替代碼農(nóng)編程嗎？討論：【導(dǎo)讀案例】AI能替代碼農(nóng)編程嗎？討論：1關(guān)于搜索算法2盲目算法3知情搜索4受到自然啟發(fā)的搜索1關(guān)于搜索算法2盲目算法3知情搜索4受到自然啟發(fā)的搜索第1節(jié)第1節(jié)4.1 關(guān)于搜索算法搜索是大多數(shù)人日常生活中的一部分。我們恐怕都有過找不到鑰匙、找不到電視遙控器的經(jīng)歷，然后翻箱倒柜一番折騰。有時(shí)候，搜索可能更多的是在大腦中進(jìn)行的。你可能會(huì)突然不記得自己到訪過的地方的名字、不記得熟人

2、的名字，或者不記得曾經(jīng)諳熟于心的歌詞。4.1 關(guān)于搜索算法搜索是大多數(shù)人日常生活中的一部分。我們4.1 關(guān)于搜索算法搜索及其執(zhí)行也是人工智能技術(shù)的重要基礎(chǔ)，是人工智能中經(jīng)常遇到的最重要的問題之一。許多算法專門通過列表進(jìn)行搜索和排序。當(dāng)然，如果數(shù)據(jù)按照邏輯順序組織，那么搜索就會(huì)比較方便一些。想象一下，如果姓名和電話號(hào)碼隨機(jī)排列，那么搜索相對(duì)較大城市的電話簿會(huì)有多麻煩。因此，搜索和信息組織在智能系統(tǒng)的設(shè)計(jì)中發(fā)揮了重要作用。例如人們認(rèn)為，性能更好的國際象棋博弈程序比同類型的程序更加智能。所謂搜索算法，就是利用計(jì)算機(jī)的高性能來有目的地窮舉一個(gè)問題的部分或所有的可能情況，從而求出問題的解的一種方法。搜索

3、過程實(shí)際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過程。4.1 關(guān)于搜索算法搜索及其執(zhí)行也是人工智能技術(shù)的重要基礎(chǔ)4.1 關(guān)于搜索算法搜索算法根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一顆“解答樹”并尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)。從最終的算法實(shí)現(xiàn)上來看，所有的搜索算法都可以劃分成兩個(gè)部分控制結(jié)構(gòu)（擴(kuò)展節(jié)點(diǎn)的方式）和產(chǎn)生系統(tǒng)（擴(kuò)展節(jié)點(diǎn)），而所有的算法優(yōu)化和改進(jìn)主要都是通過修改其控制結(jié)構(gòu)來完成的。其實(shí)，在這樣的思考過程中，我們已經(jīng)不知不 覺地將一個(gè)具體的問題抽象成了一個(gè)圖論的模型樹，即搜索算法的使用第一步在于搜索樹的建立。4.1 關(guān)于搜索算法搜索算法根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一顆4.1 關(guān)于搜索

4、算法由圖4-2可以知道，搜索樹的初始狀態(tài)對(duì)應(yīng)著根結(jié)點(diǎn)，目標(biāo)狀態(tài)對(duì)應(yīng)著目標(biāo)結(jié)點(diǎn)。排在前的結(jié)點(diǎn)叫父結(jié)點(diǎn)，其后的結(jié)點(diǎn)叫子結(jié)點(diǎn)，同一層中的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)，由父結(jié)點(diǎn)產(chǎn)生子結(jié)點(diǎn)叫擴(kuò)展。完成搜索的過程就是找到一條從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑，找出一個(gè)最優(yōu)的解，這種搜索算法的實(shí)現(xiàn)類似于圖或樹的遍歷。4.1 關(guān)于搜索算法由圖4-2可以知道，搜索樹的初始狀態(tài)對(duì)1狀態(tài)空間圖2回溯算法、貪婪算法3旅行銷售員問題4深度優(yōu)先、廣度優(yōu)先搜索第2節(jié)5迭代加深搜索1狀態(tài)空間圖2回溯算法、貪婪算法3旅行銷售員問題4深度優(yōu)先、4.2 盲目搜索我們來學(xué)習(xí)基本的搜索算法，即“盲目搜索”，或者稱為“無信息搜索”，又叫非啟發(fā)式搜索。所謂無信息

5、搜索，意味著該搜索策略沒有超出問題定義提供的狀態(tài)之外的附加信息，所能做的就是生成后繼節(jié)點(diǎn)并且區(qū)分一個(gè)目標(biāo)狀態(tài)或一個(gè)非目標(biāo)狀態(tài)。所有的搜索策略是由節(jié)點(diǎn)擴(kuò)展的順序加以區(qū)分。這些算法不依賴任何問題領(lǐng)域的特定知識(shí)，一般只適用于求解比較簡單的問題，且通常需要占用大量的空間和時(shí)間。例如，假設(shè)你正在迷宮中找出路，在盲目搜索中，你可能總是選擇最左邊的路線，而不考慮任何其他可替代的選擇。4.2 盲目搜索我們來學(xué)習(xí)基本的搜索算法，即“盲目搜索”，4.2 盲目搜索盲目搜索通常是按預(yù)定的搜索策略進(jìn)行搜索，而不會(huì)考慮到問題本身的特性。常用的盲目搜索有廣度優(yōu)先搜索（Breadth First Search, BFS）和深

6、度優(yōu)先搜索（Depth First search, DFS）兩種。4.2 盲目搜索盲目搜索通常是按預(yù)定的搜索策略進(jìn)行搜索，而4.2.1 狀態(tài)空間圖狀態(tài)空間圖（statc-space graph）是一個(gè)有助于形式化搜索過程的數(shù)學(xué)結(jié)構(gòu)，是對(duì)一個(gè)問題的表示，通過問題表示，人們可以探索和分析通往解的可能的可替代路徑。特定問題的解將對(duì)應(yīng)狀態(tài)空間圖中的一條路徑。有時(shí)候，我們要搜索一個(gè)問題的任意解；而有時(shí)候，我們希望得到一個(gè)最短（最優(yōu)）的解。在計(jì)算機(jī)科學(xué)領(lǐng)域里，有一個(gè)著名的假幣問題。有12枚硬幣，己知其中一枚是假的或是偽造的，但是還不知道假幣是比其他真幣更輕還是更重。普通的秤可以用于確定任何兩組硬幣的質(zhì)量，

7、即一組硬幣比另一組硬幣更輕或更重。為了解決這個(gè)問題，你應(yīng)該創(chuàng)建一個(gè)程序，通過稱量三組硬幣的組合，來識(shí)別假幣。4.2.1 狀態(tài)空間圖狀態(tài)空間圖（statc-space 4.2.1 狀態(tài)空間圖下面，我們就來解決一個(gè)相對(duì)簡單的問題實(shí)例，假設(shè)只涉及到6枚硬幣；與上述的原始問題一樣，它也需要比較三組硬幣，由于在這種情況下，任何一組的硬幣枚數(shù)相對(duì)較少，我們稱之為最小假幣問題。我們使用符號(hào)Ci1Ci2Cir : Cj1Cj2Cjr來指示r枚硬幣，比較Ci1Ci2Cir與另r枚硬幣Cj1Cj2Cjr的質(zhì)量大小。結(jié)果是，要么這兩組硬幣同樣重，要么不一樣重。我們不需要進(jìn)一步知道左邊盤子的硬幣是否比右邊盤子的硬幣更

8、重或是更輕（如果要解決這個(gè)問題的12枚硬幣的版本，就需要知道其他知識(shí)）。最后，我們采用記號(hào) Ck1Ck2Ckm 來指示具有m枚硬幣的子集是所知道的包含了假幣的最小硬幣集合。圖4-3給出了這個(gè)最小假幣問題的一個(gè)解。4.2.1 狀態(tài)空間圖下面，我們就來解決一個(gè)相對(duì)簡單的問題4.2.1 狀態(tài)空間圖如圖4-3所示，狀態(tài)空間樹由節(jié)點(diǎn)和分支組成。一個(gè)橢圓是一個(gè)節(jié)點(diǎn)，代表問題的一個(gè)狀態(tài)。節(jié)點(diǎn)之間的弧表示將狀態(tài)空間樹移動(dòng)到新節(jié)點(diǎn)的算符（或所應(yīng)用的算符）。請(qǐng)參考圖4-3中標(biāo)有（*）的節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn) C1C2C3C4 表示假幣可能是C1、C2、C3或C4中的任何一個(gè)。我們決定對(duì)C1和C2以及C5、C6之間的質(zhì)量大

9、?。☉?yīng)用算符）進(jìn)行比較。如果結(jié)果是這兩個(gè)集合中的硬幣質(zhì)量相等，那么就知道假幣必然是C3或C4中的一個(gè)；如果這兩個(gè)集合中的硬幣質(zhì)量不相等，那么可以確定C1或C2是假幣。為什么呢？狀態(tài)空間樹中有兩種特殊類型的節(jié)點(diǎn)。第一個(gè)是表示問題起始狀態(tài)的起始節(jié)點(diǎn)。4.2.1 狀態(tài)空間圖如圖4-3所示，狀態(tài)空間樹由節(jié)點(diǎn)和分4.2.1 狀態(tài)空間圖在圖4-3中，起始節(jié)點(diǎn)是 C1C2C3C4C5C6，這表明起始狀態(tài)時(shí)，假幣可以是6枚硬幣中的任何一個(gè)。另一種特殊類型的節(jié)點(diǎn)對(duì)應(yīng)于問題的終點(diǎn)或最終狀態(tài)。圖4-3中的狀態(tài)空間樹有6個(gè)終端節(jié)點(diǎn)，每個(gè)標(biāo)記為 Ci (i=1, , 6)，其中i的值指定了哪枚是假幣。問題的狀態(tài)空間樹包

10、含了問題可能出現(xiàn)的所有狀態(tài)以及這些狀態(tài)之間所有可能的轉(zhuǎn)換。事實(shí)上，由于回路經(jīng)常出現(xiàn)，這樣的結(jié)構(gòu)通常稱為狀態(tài)空間圖。問題的解通常需要在這個(gè)結(jié)構(gòu)中搜索（無論它是樹還是圖），這個(gè)結(jié)構(gòu)始于起始節(jié)點(diǎn)，終于終點(diǎn)或最終狀態(tài)。有時(shí)候，我們關(guān)心的是找到一個(gè)解（不論代價(jià)）；但有時(shí)候，我們可能希望找到最低代價(jià)的解。4.2.1 狀態(tài)空間圖在圖4-3中，起始節(jié)點(diǎn)是 C1C24.2.1 狀態(tài)空間圖圖4-3 最小假幣問題的解4.2.1 狀態(tài)空間圖4.2.1 狀態(tài)空間圖說到解的代價(jià)，我們指的是到達(dá)目標(biāo)狀態(tài)所需的算符的數(shù)量，而不是實(shí)際找到此解所需的工作量。相比計(jì)算機(jī)科學(xué)，解的代價(jià)等同于運(yùn)行時(shí)間，而不是軟件開發(fā)時(shí)間。到目前為止，

11、我們不加區(qū)別地使用了節(jié)點(diǎn)和狀態(tài)這兩個(gè)術(shù)語。但是，這是兩個(gè)不同的概念。通常情況下，狀態(tài)空間圖可以包含代表相同問題狀態(tài)的多個(gè)節(jié)點(diǎn)（見圖4-4）?；仡欁钚〖賻艈栴}可知，通過對(duì)兩個(gè)不同集合的硬幣進(jìn)行稱重，可以到達(dá)表示相同狀態(tài)的不同節(jié)點(diǎn)。4.2.1 狀態(tài)空間圖說到解的代價(jià)，我們指的是到達(dá)目標(biāo)狀態(tài)4.2.1 狀態(tài)空間圖圖4-4 狀態(tài)空間圖中的不同節(jié)點(diǎn)可以表示相同的狀態(tài)4.2.1 狀態(tài)空間圖4.2.1 狀態(tài)空間圖在求解過程中，可以有意忽略系統(tǒng)的某些細(xì)節(jié)，這樣就可以允許在合理的層面與系統(tǒng)進(jìn)行交互，這就是抽象。例如，如果你想玩棒球，那么抽象就可以更好地讓你練習(xí)如何打弧線球，而不是讓你花6年時(shí)間成為研究物體如何移

12、動(dòng)的力學(xué)方面的博士。4.2.1 狀態(tài)空間圖在求解過程中，可以有意忽略系統(tǒng)的某些4.2.2 回溯算法回溯算法是所有搜索算法中最為基本的一種算法，它采用一種“走不通就掉頭”思想作為其控制結(jié)構(gòu)，相當(dāng)于采用了先根遍歷的方法來構(gòu)造解答樹，可用于找解或所有解以及最優(yōu)解。例如，在一個(gè)MM的棋盤上某一點(diǎn)上有一個(gè)馬，要求尋找一條從這一點(diǎn)出發(fā)不重復(fù)的跳完棋盤上所有的點(diǎn)的路線?；厮輰⑺阉鞣殖扇舾刹襟E，在每個(gè)步驟中按照規(guī)定的方式做出選擇。如果問題的約束條件得到了滿足，那么搜索將進(jìn)行到下一步；如果沒有選項(xiàng)可以得到有用的部分解，那么搜索將回溯到前一個(gè)步驟，撤銷前一個(gè)步驟的選擇，繼續(xù)下一個(gè)可能的選擇。4.2.2 回溯算法回

13、溯算法是所有搜索算法中最為基本的一種4.2.2 回溯算法回溯算法對(duì)空間的消耗較少，當(dāng)其與分支定界法一起使用時(shí)，對(duì)于所求解在解答樹中層次較深的問題有較好的效果。但應(yīng)避免在后繼節(jié)點(diǎn)可能與前繼節(jié)點(diǎn)相同的問題中使用，以免產(chǎn)生循環(huán)。4.2.2 回溯算法回溯算法對(duì)空間的消耗較少，當(dāng)其與分支定4.2.3 貪婪算法貪婪算法也是先將一個(gè)問題分成幾個(gè)步驟進(jìn)行操作。貪婪算法總是包含了一個(gè)已優(yōu)化的目標(biāo)函數(shù)（例如，最大化或最小化）。典型的目標(biāo)函數(shù)可以是行駛的距離、消耗的成本或流逝的時(shí)間。4.2.3 貪婪算法貪婪算法也是先將一個(gè)問題分成幾個(gè)步驟進(jìn)4.2.3 貪婪算法圖4-5代表了中國幾個(gè)城市的地理位置。假設(shè)銷售人員從成都

14、開始，想找到去哈爾濱的一條最短路徑，這條路徑只經(jīng)過成都（V1）、北京（V2）、哈爾濱（V3）、杭州（V4）和西安（V5）。這5個(gè)城市之間的距離以千米表示。 圖4-5 5個(gè)城市，假設(shè)了城市之間的空中距離，這些城市彼此之間直接相連4.2.3 貪婪算法圖4-5代表了中國幾個(gè)城市的地理位置。4.2.3 貪婪算法在步驟1中，貪婪方法從成都行進(jìn)到西安，因?yàn)檫@兩個(gè)城市的距離只有606km，西安是最近的城市。（l）在步驟1中，采用V1到5的路徑，因?yàn)槲靼彩请x成都最近的城市。（2）只有是先前已經(jīng)訪問過的頂點(diǎn)，我們才可以考慮經(jīng)過該頂點(diǎn)的路徑。在步驟2中，下一個(gè)生成的路徑直接從V1到V2，它的代價(jià)（距離）是1518

15、km。這條直接的路徑比通過V3的路徑便宜，代價(jià)為606km+914km=1520km。4.2.3 貪婪算法在步驟1中，貪婪方法從成都行進(jìn)到西安，4.2.3 貪婪算法（3）V1到3便宜的路徑是使用從V1到中間節(jié)點(diǎn)（Vi）以及從Vi到V3的最便宜的路徑構(gòu)成的。此處，I等于V2；V1到V3代價(jià)最小的路徑經(jīng)過了V2，其代價(jià)為1518km+1061km=2579km。然而，V1到V4的直接路徑代價(jià)較低（1539hn）。我們直接去了V4（杭州）。4.2.3 貪婪算法（3）V1到3便宜的路徑是使用從V14.2.3 貪婪算法（4）步驟4：我們正在搜索從V1開始到任何地方的下一條代價(jià)最小路徑。我們己經(jīng)得到了V1

16、到V5的代價(jià)最小路徑，其代價(jià)為606km。第二條代價(jià)最小路徑為V1到V2的直接路徑，代價(jià)為1518km。V1到4的直接路徑（1539km）比經(jīng)過V5的路徑（606km+1l50km=1756km）以及經(jīng)過V2的路徑（1518km+1134km=2652km），其代價(jià)最低。因此，下一條代價(jià)最小路徑是那條經(jīng)過V3的路徑（2579km）。4.2.3 貪婪算法（4）步驟4：我們正在搜索從V1開始到4.2.3 貪婪算法這里有幾種可能性：V1到V5（代價(jià)=606km），然后V5到V2（代價(jià)=914km），即從V1到V2，經(jīng)過V5的代價(jià)是1520km。然后，你需要從V2到V3（代價(jià)為1061km）。從V1到

17、V3，經(jīng)過V5和V2的路徑，其總代價(jià)是1520km+1061km=2581km。V1到V2的代價(jià)為15181m，V2到V3的代價(jià)為1061km，這條路徑的總代價(jià)為2579km。V1到V4的代價(jià)為1539km，V4到V3的代價(jià)為1822km，這條路徑的總代價(jià)為3361km。4.2.3 貪婪算法這里有幾種可能性：4.2.3 貪婪算法我們采用從V1到V3的路徑，這條路徑首先經(jīng)過V2，總代價(jià)為2579km。這個(gè)例子采用的特定算法是Dijkstra的最短路徑算法，這個(gè)算法是貪婪算法的一個(gè)例子。使用貪婪算法求解問題效率很高，但有一些問題不能使用這種范式求解，例如旅行銷售員問題。4.2.3 貪婪算法我們采用

18、從V1到V3的路徑，這條路徑首4.2.4 旅行銷售員問題在旅行銷售員問題的加權(quán)圖（即邊具有代價(jià)的圖）中，給定n個(gè)頂點(diǎn)，你必須找到始于某個(gè)頂點(diǎn)Vi，有且只有一次經(jīng)過圖中的每個(gè)頂點(diǎn)，然后返回Vi的最短路徑。就用前面5個(gè)城市的例子。假設(shè)銷售員住在西安，因此必須按照某種次序依次訪問成都、北京、杭州和哈爾濱，然后回到西安。在尋求代價(jià)最小的路徑時(shí)，旅行銷售員問題基于貪婪算法的解總是訪問下一個(gè)最近的城市。4.2.4 旅行銷售員問題在旅行銷售員問題的加權(quán)圖（即邊具4.2.4 旅行銷售員問題貪婪算法訪問成都、北京、哈爾濱、杭州，然后終于回到西安。這個(gè)路徑的代價(jià)是606km + 1518km + 1061km +

19、 1822km + 1050km = 6057km。如果銷售人員訪問依次北京、哈爾濱、杭州、成都，然后返回西安，那么總累計(jì)代價(jià)為914km + 1061km + 1822km + 1539km + 606km = 5942km。顯然，貪婪算法未能找到最佳路徑。4.2.4 旅行銷售員問題貪婪算法訪問成都、北京、哈爾濱、4.2.5 深度優(yōu)先搜索盲目搜索是不使用領(lǐng)域知識(shí)的不知情搜索算法。這些方法假定不知道狀態(tài)空間的任何信息。3種主要算法是：深度優(yōu)先搜索（DFS）、廣度優(yōu)先搜索（BFS）和迭代加深（DFS-ID）的深度優(yōu)先搜索。這些算法都具有如下兩個(gè)性質(zhì)：（1）它們不使用啟發(fā)式估計(jì)。如果使用啟發(fā)式估計(jì)

20、，那么搜索將沿著最有希望得到解決方案的路徑前進(jìn)。（2）它們的目標(biāo)是找出給定問題的某個(gè)解。4.2.5 深度優(yōu)先搜索盲目搜索是不使用領(lǐng)域知識(shí)的不知情搜4.2.5 深度優(yōu)先搜索深度優(yōu)先搜索（DFS），顧名思義，就是試圖盡可能快地深入樹中。每當(dāng)搜索方法可以做出選擇時(shí)，它選擇最左（或最右）的分支（通常選擇最左分支）?？梢詫D4-6所示的樹作為DFS的一個(gè)例子。圖4-6 樹的深度優(yōu)先搜索遍歷4.2.5 深度優(yōu)先搜索深度優(yōu)先搜索（DFS），顧名思義，4.2.5 深度優(yōu)先搜索將按照A、B、D、E、C、F、G的順序訪問節(jié)點(diǎn)樹的遍歷算法將多次“訪問”某個(gè)節(jié)點(diǎn)，例如，在圖4-6中，依次訪問A、B、D、B、E、B、A

21、、C、F、C、G。4.2.5 深度優(yōu)先搜索將按照A、B、D、E、C、F、G的4.2.5 深度優(yōu)先搜索深度優(yōu)先搜索的基本思想是：從初始節(jié)點(diǎn)S0開始進(jìn)行節(jié)點(diǎn)擴(kuò)展，考察S0擴(kuò)展的最后1個(gè)子節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若不是目標(biāo)節(jié)點(diǎn)，則對(duì)該節(jié)點(diǎn)進(jìn)行擴(kuò)展；然后再對(duì)其擴(kuò)展節(jié)點(diǎn)中的最后1個(gè)子節(jié)點(diǎn)進(jìn)行考察，若又不是目標(biāo)節(jié)點(diǎn)，則對(duì)其進(jìn)行擴(kuò)展，一直如此向下擴(kuò)展。當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)本身不能擴(kuò)展時(shí)，對(duì)其1個(gè)兄弟節(jié)點(diǎn)進(jìn)行擴(kuò)展；如果所有的兄弟節(jié)點(diǎn)都不能夠擴(kuò)展時(shí)，則尋找到它們的父節(jié)點(diǎn)，對(duì)父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)進(jìn)行擴(kuò)展；依次類推，直到發(fā)現(xiàn)目標(biāo)狀態(tài)Sg為止。因此，深度優(yōu)先搜索法存在搜索和回溯交替出現(xiàn)的現(xiàn)象。4.2.5 深度優(yōu)先搜索深度優(yōu)先搜索的基本

22、思想是：從初始節(jié)4.2.5 深度優(yōu)先搜索DFS采用不同的策略來達(dá)到目標(biāo)：在尋找可替代路徑之前，它追求尋找單一的路徑來實(shí)現(xiàn)目標(biāo)，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到問題解。但若目標(biāo)節(jié)點(diǎn)不在該分支上，且該分支又是一個(gè)無窮分支，就不可能得到解。所以，DFS是不完備搜索。DFS內(nèi)存需求合理，但是它可能會(huì)因偏離開始位置無限遠(yuǎn)而錯(cuò)過了相對(duì)靠近搜索起始位置的解。4.2.5 深度優(yōu)先搜索DFS采用不同的策略來達(dá)到目標(biāo)：在4.2.6 廣度優(yōu)先搜索廣度優(yōu)先搜索（BFS，又稱寬度優(yōu)先搜索）是第二種盲目搜索方法。使用BFS，從樹的頂部到樹的底部，按照從左到右的方

23、式（或從右到左，不過一般來說從左到右），可以逐層訪問節(jié)點(diǎn)。要先訪問層次i的所有節(jié)點(diǎn)，然后才能訪問在i+1層的節(jié)點(diǎn)。圖4-7顯示了BFS的遍歷過程。按照以下順序訪問節(jié)點(diǎn)：A、B、C、D、E、F、G。圖4-7 樹的廣度優(yōu)先遍歷4.2.6 廣度優(yōu)先搜索廣度優(yōu)先搜索（BFS，又稱寬度優(yōu)先4.2.6 廣度優(yōu)先搜索廣度優(yōu)先搜索的基本思想是：從初始節(jié)點(diǎn)S0開始進(jìn)行節(jié)點(diǎn)擴(kuò)展，考察S0的第1個(gè)子節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若不是目標(biāo)節(jié)點(diǎn)，則對(duì)該節(jié)點(diǎn)進(jìn)行擴(kuò)展；再考察S0的第2個(gè)子節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若不是目標(biāo)節(jié)點(diǎn)，則對(duì)其進(jìn)行擴(kuò)展；對(duì)S0的所有子節(jié)點(diǎn)全部考察并擴(kuò)展以后，再分別對(duì)S0的所有子節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行考察并擴(kuò)展，如此向

24、下搜索，直到發(fā)現(xiàn)目標(biāo)狀態(tài)Sg為止。因此，廣度優(yōu)先搜索在對(duì)第n層的節(jié)點(diǎn)沒有全部考察并擴(kuò)展之前，不對(duì)第n+1層的節(jié)點(diǎn)進(jìn)行考察和擴(kuò)展。4.2.6 廣度優(yōu)先搜索廣度優(yōu)先搜索的基本思想是：從初始節(jié)4.2.6 廣度優(yōu)先搜索在繼續(xù)前進(jìn)之前，BFS在離開始位置的指定距離處仔細(xì)查看所有替代選項(xiàng)。BFS的優(yōu)點(diǎn)是，如果一個(gè)問題存在解，那么BFS總是可以得到解，而且得到的解是路徑最短的，所以它是完備的搜索。但是，如果在每個(gè)節(jié)點(diǎn)的可替代選項(xiàng)很多，那么BFS可能會(huì)因需要消耗太多的內(nèi)存而變得不切實(shí)際。BFS的盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，會(huì)產(chǎn)生許多無用節(jié)點(diǎn)，搜索效率低。4.2.6 廣度優(yōu)先搜索在繼續(xù)前進(jìn)之前，BFS在離開始位置4.2.7 迭代加深搜索深