機(jī)械工業(yè)出版社2020《人工智能導(dǎo)論》課程同步PPT課件第4章 搜索算法

人工智能導(dǎo)論Introductiontoartificialintelligence機(jī)械工業(yè)出版社2020第4章搜索算法【導(dǎo)讀案例】AI能替代碼農(nóng)編程嗎？討論：1關(guān)于搜索算法2盲目算法3知情搜索4受到自然啟發(fā)的搜索第1節(jié)4.1關(guān)于搜索算法搜索是大多數(shù)人日常生活中的一部分。我們恐怕都有過找不到鑰匙、找不到電視遙控器的經(jīng)歷，然后翻箱倒柜一番折騰。有時(shí)候，搜索可能更多的是在大腦中進(jìn)行的。你可能會(huì)突然不記得自己到訪過的地方的名字、不記得熟人的名字，或者不記得曾經(jīng)諳熟于心的歌詞。4.1關(guān)于搜索算法搜索及其執(zhí)行也是人工智能技術(shù)的重要基礎(chǔ)，是人工智能中經(jīng)常遇到的最重要的問題之一。許多算法專門通過列表進(jìn)行搜索和排序。當(dāng)然，如果數(shù)據(jù)按照邏輯順序組織，那么搜索就會(huì)比較方便一些。想象一下，如果姓名和電話號(hào)碼隨機(jī)排列，那么搜索相對較大城市的電話簿會(huì)有多麻煩。因此，搜索和信息組織在智能系統(tǒng)的設(shè)計(jì)中發(fā)揮了重要作用。例如人們認(rèn)為，性能更好的國際象棋博弈程序比同類型的程序更加智能。所謂搜索算法，就是利用計(jì)算機(jī)的高性能來有目的地窮舉一個(gè)問題的部分或所有的可能情況，從而求出問題的解的一種方法。搜索過程實(shí)際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過程。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)于搜索算法由圖4-2可以知道，搜索樹的初始狀態(tài)對應(yīng)著根結(jié)點(diǎn)，目標(biāo)狀態(tài)對應(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)類似于圖或樹的遍歷。1狀態(tài)空間圖2回溯算法、貪婪算法3旅行銷售員問題4深度優(yōu)先、廣度優(yōu)先搜索第2節(jié)5迭代加深搜索4.2盲目搜索我們來學(xué)習(xí)基本的搜索算法，即“盲目搜索”，或者稱為“無信息搜索”，又叫非啟發(fā)式搜索。所謂無信息搜索，意味著該搜索策略沒有超出問題定義提供的狀態(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盲目搜索盲目搜索通常是按預(yù)定的搜索策略進(jìn)行搜索，而不會(huì)考慮到問題本身的特性。常用的盲目搜索有廣度優(yōu)先搜索（BreadthFirstSearch,BFS）和深度優(yōu)先搜索（DepthFirstsearch,DFS）兩種。4.2.1狀態(tài)空間圖狀態(tài)空間圖（statc-spacegraph）是一個(gè)有助于形式化搜索過程的數(shù)學(xué)結(jié)構(gòu)，是對一個(gè)問題的表示，通過問題表示，人們可以探索和分析通往解的可能的可替代路徑。特定問題的解將對應(yīng)狀態(tài)空間圖中的一條路徑。有時(shí)候，我們要搜索一個(gè)問題的任意解；而有時(shí)候，我們希望得到一個(gè)最短（最優(yōu)）的解。在計(jì)算機(jī)科學(xué)領(lǐng)域里，有一個(gè)著名的假幣問題。有12枚硬幣，己知其中一枚是假的或是偽造的，但是還不知道假幣是比其他真幣更輕還是更重。普通的秤可以用于確定任何兩組硬幣的質(zhì)量，即一組硬幣比另一組硬幣更輕或更重。為了解決這個(gè)問題，你應(yīng)該創(chuàng)建一個(gè)程序，通過稱量三組硬幣的組合，來識(shí)別假幣。4.2.1狀態(tài)空間圖下面，我們就來解決一個(gè)相對簡單的問題實(shí)例，假設(shè)只涉及到6枚硬幣；與上述的原始問題一樣，它也需要比較三組硬幣，由于在這種情況下，任何一組的硬幣枚數(shù)相對較少，我們稱之為最小假幣問題。我們使用符號(hào)Ci1Ci2…Cir:Cj1Cj2…Cjr來指示r枚硬幣，比較Ci1Ci2…Cir與另r枚硬幣Cj1Cj2…Cjr的質(zhì)量大小。結(jié)果是，要么這兩組硬幣同樣重，要么不一樣重。我們不需要進(jìn)一步知道左邊盤子的硬幣是否比右邊盤子的硬幣更重或是更輕（如果要解決這個(gè)問題的12枚硬幣的版本，就需要知道其他知識(shí)）。最后，我們采用記號(hào)[Ck1Ck2…Ckm]來指示具有m枚硬幣的子集是所知道的包含了假幣的最小硬幣集合。圖4-3給出了這個(gè)最小假幣問題的一個(gè)解。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)用的算符）。請參考圖4-3中標(biāo)有（*）的節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)[C1C2C3C4]表示假幣可能是C1、C2、C3或C4中的任何一個(gè)。我們決定對C1和C2以及C5、C6之間的質(zhì)量大?。☉?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中，起始節(jié)點(diǎn)是[C1C2C3C4C5C6]，這表明起始狀態(tài)時(shí)，假幣可以是6枚硬幣中的任何一個(gè)。另一種特殊類型的節(jié)點(diǎn)對應(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)空間樹包含了問題可能出現(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最小假幣問題的解4.2.1狀態(tài)空間圖說到解的代價(jià)，我們指的是到達(dá)目標(biāo)狀態(tài)所需的算符的數(shù)量，而不是實(shí)際找到此解所需的工作量。相比計(jì)算機(jī)科學(xué)，解的代價(jià)等同于運(yùn)行時(shí)間，而不是軟件開發(fā)時(shí)間。到目前為止，我們不加區(qū)別地使用了節(jié)點(diǎn)和狀態(tài)這兩個(gè)術(shù)語。但是，這是兩個(gè)不同的概念。通常情況下，狀態(tài)空間圖可以包含代表相同問題狀態(tài)的多個(gè)節(jié)點(diǎn)（見圖4-4）?；仡欁钚〖賻艈栴}可知，通過對兩個(gè)不同集合的硬幣進(jìn)行稱重，可以到達(dá)表示相同狀態(tài)的不同節(jié)點(diǎn)。4.2.1狀態(tài)空間圖圖4-4狀態(tài)空間圖中的不同節(jié)點(diǎn)可以表示相同的狀態(tài)4.2.1狀態(tài)空間圖在求解過程中，可以有意忽略系統(tǒng)的某些細(xì)節(jié)，這樣就可以允許在合理的層面與系統(tǒng)進(jìn)行交互，這就是抽象。例如，如果你想玩棒球，那么抽象就可以更好地讓你練習(xí)如何打弧線球，而不是讓你花6年時(shí)間成為研究物體如何移動(dòng)的力學(xué)方面的博士。4.2.2回溯算法回溯算法是所有搜索算法中最為基本的一種算法，它采用一種“走不通就掉頭”思想作為其控制結(jié)構(gòu)，相當(dāng)于采用了先根遍歷的方法來構(gòu)造解答樹，可用于找解或所有解以及最優(yōu)解。例如，在一個(gè)M×M的棋盤上某一點(diǎn)上有一個(gè)馬，要求尋找一條從這一點(diǎn)出發(fā)不重復(fù)的跳完棋盤上所有的點(diǎn)的路線?；厮輰⑺阉鞣殖扇舾刹襟E，在每個(gè)步驟中按照規(guī)定的方式做出選擇。如果問題的約束條件得到了滿足，那么搜索將進(jìn)行到下一步；如果沒有選項(xiàng)可以得到有用的部分解，那么搜索將回溯到前一個(gè)步驟，撤銷前一個(gè)步驟的選擇，繼續(xù)下一個(gè)可能的選擇。4.2.2回溯算法回溯算法對空間的消耗較少，當(dāng)其與分支定界法一起使用時(shí)，對于所求解在解答樹中層次較深的問題有較好的效果。但應(yīng)避免在后繼節(jié)點(diǎn)可能與前繼節(jié)點(diǎn)相同的問題中使用，以免產(chǎn)生循環(huán)。4.2.3貪婪算法貪婪算法也是先將一個(gè)問題分成幾個(gè)步驟進(jìn)行操作。貪婪算法總是包含了一個(gè)已優(yōu)化的目標(biāo)函數(shù)（例如，最大化或最小化）。典型的目標(biāo)函數(shù)可以是行駛的距離、消耗的成本或流逝的時(shí)間。4.2.3貪婪算法圖4-5代表了中國幾個(gè)城市的地理位置。假設(shè)銷售人員從成都開始，想找到去哈爾濱的一條最短路徑，這條路徑只經(jīng)過成都（V1）、北京（V2）、哈爾濱（V3）、杭州（V4）和西安（V5）。

這5個(gè)城市之間的距離以千米表示。

圖4-55個(gè)城市，假設(shè)了城市之間的空中距離，這些城市彼此之間直接相連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à)（距離）是1518km。這條直接的路徑比通過V3的路徑便宜，代價(jià)為606km+914km=1520km。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貪婪算法（4）步驟4：我們正在搜索從V1開始到任何地方的下一條代價(jià)最小路徑。我們己經(jīng)得到了V1到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貪婪算法這里有幾種可能性：V1到V5（代價(jià)=606km），然后V5到V2（代價(jià)=914km），即從V1到V2，經(jīng)過V5的代價(jià)是1520km。然后，你需要從V2到V3（代價(jià)為1061km）。從V1到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貪婪算法我們采用從V1到V3的路徑，這條路徑首先經(jīng)過V2，總代價(jià)為2579km。這個(gè)例子采用的特定算法是Dijkstra的最短路徑算法，這個(gè)算法是貪婪算法的一個(gè)例子。使用貪婪算法求解問題效率很高，但有一些問題不能使用這種范式求解，例如旅行銷售員問題。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旅行銷售員問題貪婪算法訪問成都、北京、哈爾濱、杭州，然后終于回到西安。這個(gè)路徑的代價(jià)是606km+1518km+1061km+1822km+1050km=6057km。如果銷售人員訪問依次北京、哈爾濱、杭州、成都，然后返回西安，那么總累計(jì)代價(jià)為914km+1061km+1822km+1539km+606km=5942km。顯然，貪婪算法未能找到最佳路徑。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ì)，那么搜索將沿著最有希望得到解決方案的路徑前進(jìn)。（2）它們的目標(biāo)是找出給定問題的某個(gè)解。4.2.5深度優(yōu)先搜索深度優(yōu)先搜索（DFS），顧名思義，就是試圖盡可能快地深入樹中。每當(dāng)搜索方法可以做出選擇時(shí)，它選擇最左（或最右）的分支（通常選擇最左分支）?？梢詫D4-6所示的樹作為DFS的一個(gè)例子。圖4-6樹的深度優(yōu)先搜索遍歷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、C、F、C、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)，則對該節(jié)點(diǎn)進(jìn)行擴(kuò)展；然后再對其擴(kuò)展節(jié)點(diǎn)中的最后1個(gè)子節(jié)點(diǎn)進(jìn)行考察，若又不是目標(biāo)節(jié)點(diǎn)，則對其進(jìn)行擴(kuò)展，一直如此向下擴(kuò)展。當(dāng)發(fā)現(xiàn)節(jié)點(diǎn)本身不能擴(kuò)展時(shí)，對其1個(gè)兄弟節(jié)點(diǎn)進(jìn)行擴(kuò)展；如果所有的兄弟節(jié)點(diǎn)都不能夠擴(kuò)展時(shí)，則尋找到它們的父節(jié)點(diǎn)，對父節(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)先搜索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ò)過了相對靠近搜索起始位置的解。4.2.6廣度優(yōu)先搜索廣度優(yōu)先搜索（BFS，又稱寬度優(yōu)先搜索）是第二種盲目搜索方法。使用BFS，從樹的頂部到樹的底部，按照從左到右的方式（或從右到左，不過一般來說從左到右），可以逐層訪問節(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)先搜索的基本思想是：從初始節(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)，則對該節(jié)點(diǎn)進(jìn)行擴(kuò)展；再考察S0的第2個(gè)子節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若不是目標(biāo)節(jié)點(diǎn)，則對其進(jìn)行擴(kuò)展；對S0的所有子節(jié)點(diǎn)全部考察并擴(kuò)展以后，再分別對S0的所有子節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行考察并擴(kuò)展，如此向下搜索，直到發(fā)現(xiàn)目標(biāo)狀態(tài)Sg為止。因此，廣度優(yōu)先搜索在對第n層的節(jié)點(diǎn)沒有全部考察并擴(kuò)展之前，不對第n+1層的節(jié)點(diǎn)進(jìn)行考察和擴(kuò)展。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.7迭代加深搜索深度優(yōu)先搜索深入探索一棵樹，而廣度優(yōu)先搜索在進(jìn)一步深入探索之前先檢查靠近根的節(jié)點(diǎn)。一方面，因?yàn)樯疃葍?yōu)先（DFS）會(huì)堅(jiān)定地沿長路徑搜索，結(jié)果錯(cuò)過了靠近根的目標(biāo)節(jié)點(diǎn)；另一方面，廣度優(yōu)先（BFS）的存儲(chǔ)空間需求過高，很容易就被中等大小的分支因子給壓垮了。這兩種算法都表現(xiàn)出了指數(shù)級(jí)的最壞情況時(shí)間復(fù)雜度。為克服深度優(yōu)先搜索陷入無窮分支死循環(huán)的問題，提出了有界深度優(yōu)先搜索方法。有界深度搜索的基本思想是：預(yù)先設(shè)定搜索深度的界限，當(dāng)搜索深度到達(dá)了深度界限而尚未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜索。4.2.7迭代加深搜索在有界深度搜索策略中，深度限制d是一個(gè)很重要的參數(shù)。當(dāng)問題有解，且解的路徑長度小于或等于d時(shí)，則搜索過程一定能找到解。但是，這不能保證最先找到的是最優(yōu)解，此時(shí)深度搜索是完備而非最優(yōu)的。如d取得太小，解的路徑長度大于d，則在搜索過程中就找不到解，此時(shí)搜索過程不完備。但是，深度限制d不能太大，否則會(huì)產(chǎn)生過多的無用節(jié)點(diǎn)。為了解決深度限制d的設(shè)置，可以采用這樣的方法：先任意給定一個(gè)較小的深度限制，然后按有界深度搜索，如在此深度找到解，則結(jié)束；否則，增大深度限制，繼續(xù)搜索。此種搜索方法稱為迭代加深搜索。4.2.7迭代加深搜索具有迭代加深的DFS是介于BFS和DFS之間的折中方案，它將DFS中等空間需求與BFS提供能找到解的確定性結(jié)合到了一起，結(jié)合了兩種算法的有利特征——DFS的中等空間需求與BFS的完備性。但是，即使迭代加深的DFS，在最壞情況下也具有指數(shù)級(jí)別的時(shí)間復(fù)雜度。1啟發(fā)法、爬山法2最陡爬坡法、最佳優(yōu)先搜索3分支定界法——找到最佳解4A*算法第3節(jié)4.3知情搜索由人工智能處理的大型問題通常不適合通過以固定方式搜索空間的盲目搜索算法來求解。這一節(jié)我們學(xué)習(xí)知情搜索的方法——用啟發(fā)法，通過限定搜索深度或是限定搜索寬度來縮小問題空間，常利用領(lǐng)域知識(shí)來避開沒有結(jié)果的搜索路徑。作為經(jīng)驗(yàn)法則的啟發(fā)法在問題求解中通常是很有用的工具。4.3知情搜索爬山法是貪婪且原始的，但是有時(shí)候這種方法也能夠“幸運(yùn)”地找到在最陡爬坡法中找到的最佳方法。更常見的是，爬山法可能會(huì)受到3個(gè)常見問題的困擾：山麓問題、高原問題和山脊問題。比較智能、優(yōu)選的搜索方法是最佳優(yōu)先搜索，使用這個(gè)方法，在評估給定路徑如何接近解時(shí)，要保持開放節(jié)點(diǎn)列表，接受反饋。集束搜索提供了更集中的視域，通過這個(gè)視野，可以尋找到一條狹窄路徑通往解。4.3知情搜索爬山、最佳優(yōu)先搜索和集束搜索這些算法“從不回頭”。在狀態(tài)空間中，它們的路徑完全由到目標(biāo)的剩余距離的啟發(fā)式評估（近似）引導(dǎo)。假設(shè)某人從紐約市搭車到威斯康星州的麥迪遜。一路上，關(guān)于應(yīng)該選擇哪條高速公路出現(xiàn)了許多選擇。這類搜索也許會(huì)采用到目標(biāo)的最小直線距離的啟發(fā)法（例如麥迪遜）。求解問題通常涉及求解子問題。在某些情況下，必須解決所有的子問題，但有時(shí)解決一個(gè)子問題就足夠了。例如，如果一個(gè)人在洗衣服，則需要洗滌和干燥衣服。但是，干燥衣服可以將濕衣服放入機(jī)器中或?qū)⑵鋺覓煸诹酪吕K上來實(shí)現(xiàn)。4.3.1啟發(fā)法啟發(fā)法是解決問題的經(jīng)驗(yàn)法則。換句話說，啟發(fā)法是用于解決問題的一組常用指南。與算法相比，算法是規(guī)定的用于解決問題的一組規(guī)則，其輸出是完全可預(yù)測的，例如排序算法（包括冒泡排序和快速排序）以及搜索算法（包括順序搜索和二分查找）。而使用啟發(fā)法，我們可以得到一個(gè)很有利但不能保證的結(jié)果。4.3.1啟發(fā)法“啟發(fā)式之父”喬治·波利亞所描述的啟發(fā)法是，當(dāng)面對一個(gè)困難的問題時(shí)，首先嘗試解決一個(gè)相對簡單但相關(guān)的問題。這通常提供了有用見解，以幫助找到原始問題的解決方法。波利亞的工作側(cè)重于問題的求解、思考和學(xué)習(xí)，他建立了啟發(fā)式原語的“啟發(fā)式字典”，運(yùn)用形式化觀察和實(shí)驗(yàn)的方法來尋求創(chuàng)立和獲得人類問題求解過程的見解。博爾克和西斯基說，啟發(fā)式研究方法在特定的問題領(lǐng)域?qū)で蟾问交?、更?yán)格的類似算法的解，而不是發(fā)展可以從特定的問題中選擇并應(yīng)用到特定問題中的更一般化方法。4.3.1啟發(fā)法啟發(fā)式搜索方法的目的是在考慮到要達(dá)到目標(biāo)狀態(tài)情況下極大地減少節(jié)點(diǎn)數(shù)目。它們非常適合組合復(fù)雜度快速增長的問題。通過知識(shí)、信息、規(guī)則、見解、類比和簡化，再加上一堆其他的技術(shù)，啟發(fā)式搜索方法旨在減少必須檢查的對象數(shù)目。好的啟發(fā)式方法不能保證獲得解，但是它們經(jīng)常有助于引導(dǎo)人們到達(dá)解路徑。Pearl聲明，使用啟發(fā)式方法可以修改策略，顯著降低成本，達(dá)到一個(gè)準(zhǔn)最優(yōu)（而不是最優(yōu)）解。博弈，特別是二人零和博弈，具有完全的信息，如國際象棋和跳棋。實(shí)踐證明，二人零和博弈是進(jìn)行啟發(fā)法的研究和測試一個(gè)非常有前景的領(lǐng)域。4.3.1啟發(fā)法“啟發(fā)式”作為通過智能猜測而不是遵循一些預(yù)先確定的公式來獲得知識(shí)或一些期望結(jié)果的過程相關(guān)。這個(gè)術(shù)語有兩種用法：（1）描述一種學(xué)習(xí)方法，這種方法不一定用一個(gè)有組織的假設(shè)或方式來證明結(jié)果，而是通過嘗試來證明結(jié)果，這個(gè)結(jié)果可能證明了假設(shè)或反駁了假設(shè)。也就是說，這是“憑經(jīng)驗(yàn)”或“試錯(cuò)法”的學(xué)習(xí)方式。（2）根據(jù)經(jīng)驗(yàn)，有時(shí)候表達(dá)為“使用經(jīng)驗(yàn)法則”獲得一般的知識(shí)（但是，啟發(fā)式知識(shí)可以應(yīng)用于簡單或者復(fù)雜的日常問題。人類棋手即使用啟發(fā)式方法）。4.3.1啟發(fā)法下面是啟發(fā)式搜索的幾個(gè)定義?！皢l(fā)”作為一個(gè)名詞，是特定的經(jīng)驗(yàn)法則或從經(jīng)驗(yàn)衍生出來的論據(jù)。相關(guān)問題的啟發(fā)式知識(shí)的應(yīng)用有時(shí)候稱為啟發(fā)法。它是一個(gè)提高復(fù)雜問題解決效率的實(shí)用策略。它引導(dǎo)程序沿著一條最可能的路徑到達(dá)解，忽略最沒有希望的路徑。它應(yīng)該能夠避免去檢查死角，只使用己收集的數(shù)據(jù)。4.3.1啟發(fā)法啟發(fā)式信息可以添加到搜索中。決定接下來要擴(kuò)展的節(jié)點(diǎn)，而不是嚴(yán)格按照廣度優(yōu)先或深度優(yōu)先的方式進(jìn)行擴(kuò)展。在生成節(jié)點(diǎn)過程中，決定哪個(gè)是后繼節(jié)點(diǎn)，以及待生成的后繼節(jié)點(diǎn)，而不是一次性生成所有可能的后繼節(jié)點(diǎn)。確定某些節(jié)點(diǎn)應(yīng)該從搜索樹中丟棄（或裁剪掉）。4.3.1啟發(fā)法Bolc和Cytowski補(bǔ)充說：“……在構(gòu)建解過程中，使用啟發(fā)式方法增加了獲得結(jié)果的不確定性……由于非正式知識(shí)的使用（規(guī)則、規(guī)律、直覺等），這些知識(shí)的有用性從未得到充分證明。因此，在算法給出不滿意的結(jié)果或不能保證給出任何結(jié)果的情況下采用啟發(fā)式方法。在求解非常復(fù)雜的問題時(shí)，特別是在語音和圖像識(shí)別、機(jī)器人和博弈策略問題中，它們特別重要（精確的算法失敗了）?！?.3.1啟發(fā)法讓我們再考慮幾個(gè)啟發(fā)法的例子。例如，人們可以根據(jù)季節(jié)選擇車輛的機(jī)油。冬天，由于溫度低，液體容易凍結(jié)，因此應(yīng)使用較低黏度（稀?。┑陌l(fā)動(dòng)機(jī)油；而在夏季，由于溫度較高，因此選擇具有較高黏度的油是明智的。類似地，冬天，氣體冷縮了，應(yīng)在汽車輪胎內(nèi)充入更多的空氣；反之，夏天，當(dāng)氣體膨脹時(shí)，應(yīng)減少輪胎內(nèi)的空氣。4.3.1啟發(fā)法啟發(fā)式應(yīng)用與純計(jì)算算法的問題求解比較的一個(gè)常見示例是大城市的交通。許多學(xué)生使用啟發(fā)法，在上午7:00到9:00從不開車到學(xué)校，而在下午4:00到6:00從不開車回家，因?yàn)樵诖蟛糠值某鞘兄?，這是高峰時(shí)間，正常情況下45分鐘的行程很容易需要一到兩個(gè)小時(shí)完成。如果在這些時(shí)間必須開車，那么這則是例外情況。4.3.1啟發(fā)法現(xiàn)在，使用如谷歌地圖、高德地圖等程序來獲取兩個(gè)位置之間建議的行車路線，這是很常見的。你想知道這些程序是否具有內(nèi)置AI，采用啟發(fā)法使它們能夠智能地執(zhí)行任務(wù)？如果它們采用了啟發(fā)法，那么這些啟發(fā)法是什么？例如，程序是否考慮道路是國道、省道、高速公路還是林蔭大道？是否考慮駕駛條件？這將如何影響在特定道路上駕駛的平均速度和難度，以及它們選擇某種方式到特定目的地？當(dāng)使用任何行車指南或地圖時(shí)，最好檢查并確保道路仍然存在，注意是否為施工地段，并遵守所有交通安全預(yù)防措施。這些地圖和指南僅用作交通規(guī)劃的輔助工具。4.3.1啟發(fā)法谷歌地圖、高德地圖這樣的程序正在不斷變得“更智能”，以滿足應(yīng)用的需要，并且它們可以包括最短時(shí)間、最短距離、避免高速公路（可能存在駕駛員希望避開高速公路的情況）、收費(fèi)站、季節(jié)性關(guān)閉等信息。4.3.2爬山法接下來，介紹三種為找到任何解的知情搜索的特定搜索算法，它們使用啟發(fā)法指導(dǎo)智能搜索過程。最基本的是爬山法，更聰明一點(diǎn)的是最陡爬坡法，還有一種算法在效率上可算得上最優(yōu)算法――最佳優(yōu)先搜索算法。爬山法背后的概念是，在爬山過程中，即使你可能更接近頂部的目標(biāo)節(jié)點(diǎn)，但是你可能無法從當(dāng)前位置到達(dá)目標(biāo)/目的地。換句話說，你可能接近了一個(gè)目標(biāo)狀態(tài)，但是無法到達(dá)它。傳統(tǒng)上，爬山法是所討論的第一個(gè)知情搜索算法。它最簡單的形式是一種貪婪算法，在這個(gè)意義上說來，這種算法不存儲(chǔ)歷史記錄，也沒有能力從錯(cuò)誤中或錯(cuò)誤路徑中恢復(fù)。它使用一種測度（最大化這種測度，或是最小化這種測度）來指導(dǎo)它到達(dá)目標(biāo)，來指導(dǎo)下一個(gè)“移動(dòng)”選擇。4.3.2爬山法假設(shè)有一位試圖到達(dá)山頂?shù)呐郎秸?。她唯一的裝備是一個(gè)高度計(jì)，以指示她所在的山有多高，但是這種測度不能保證她會(huì)到達(dá)山頂。爬山者在任何一點(diǎn)都要做出一個(gè)選擇，即總是向所標(biāo)識(shí)的最高海拔方向前進(jìn)，但是除了給定的海拔，她不確定自己是否在正確的路徑上。顯然，這種簡單的爬山方法的缺點(diǎn)是，做出決策的過程（啟發(fā)式測度）太過樸素簡單，以致登山者沒有真正足夠的信息確定自己在正確的路徑上。爬山只會(huì)估計(jì)剩余距離，而忽略了實(shí)際走過的距離。在圖4-8中，在A和B中做出的爬山?jīng)Q定，由于A估計(jì)的剩余距離小于B，因此選擇了A，而“忘記”了節(jié)點(diǎn)B。然后，爬山從A的搜索空間看去，在節(jié)點(diǎn)C和D之間考慮，很明顯我們選擇了C，接下來是H。4.3.3最陡爬坡法最陡爬坡法知道你將能夠接近某個(gè)目標(biāo)狀態(tài)，能夠在給定的狀態(tài)下做出決策，并且從多個(gè)可能的選項(xiàng)中做出最好的決定。從本質(zhì)上講，相比于上述簡單的爬山法，這解釋了最陡爬坡法的優(yōu)勢。這個(gè)優(yōu)勢是，從多個(gè)比當(dāng)前狀態(tài)可能“更好的節(jié)點(diǎn)”中做出一個(gè)選擇。而不僅僅是選擇向當(dāng)前狀態(tài)“更好”（更高）的目標(biāo)移動(dòng)，這種方法從給定的可能節(jié)點(diǎn)集合中選擇了“最好”的移動(dòng)（在這個(gè)情況下是最高的分?jǐn)?shù)）。4.3.3最陡爬坡法圖4-8爬山示例注意：在這個(gè)示例中，節(jié)點(diǎn)中的數(shù)字是到目標(biāo)狀態(tài)估計(jì)的距離，頂點(diǎn)的數(shù)字僅僅指示爬過的距離，沒有添加任何重要的信息4.3.3最陡爬坡法圖4-9說明了最陡爬坡法。如果程序按字母順序選擇節(jié)點(diǎn)，則從節(jié)點(diǎn)A（-30）開始，我們可以得出結(jié)論：下一個(gè)最好的狀態(tài)是節(jié)點(diǎn)B，具有（-15）的分?jǐn)?shù)。但是這比當(dāng)前的狀態(tài)（0）更差，因此最終它將移動(dòng)到節(jié)點(diǎn)C（50）。從節(jié)點(diǎn)C，我們將考慮節(jié)點(diǎn)D、E或F。但是，由于節(jié)點(diǎn)D處于比當(dāng)前狀態(tài)更糟的狀態(tài)，因此不選擇節(jié)點(diǎn)D。在節(jié)點(diǎn)E（90）改進(jìn)了當(dāng)前的狀態(tài)（50），因此我們選擇節(jié)點(diǎn)E。如果使用這里的描述，標(biāo)準(zhǔn)爬山法將永遠(yuǎn)不會(huì)檢查可以返回比節(jié)點(diǎn)E更高分?jǐn)?shù)的節(jié)點(diǎn)F，即100。與標(biāo)準(zhǔn)爬山法相反，最陡爬坡法將評估所有的3個(gè)節(jié)點(diǎn)D、E和F，并總結(jié)出F（100）是從節(jié)點(diǎn)C出發(fā)選擇的最好節(jié)點(diǎn)。4.3.3最陡爬坡法圖4-9最陡爬坡法：這里有一位登山者，我們按照字母表順序?qū)⒐?jié)點(diǎn)呈現(xiàn)給他。從節(jié)點(diǎn)C（50），爬山算法選擇了節(jié)點(diǎn)E（90），最陡爬坡法選擇了F（100）4.3.4最佳優(yōu)先搜索爬山法是一種短視的貪婪算法。由于最陡爬坡法在做出決定之前，比較了可能的后繼節(jié)點(diǎn)，因此最陡爬坡法的角度比爬山法更開闊、然而這依然存在著與爬山相關(guān)的（山麓、高原和山脊）問題。如果考慮可能的補(bǔ)救措施并將其形式化，那么我們會(huì)得到最佳優(yōu)先搜索。4.3.4最佳優(yōu)先搜索最佳優(yōu)先搜索是我們討論的第一個(gè)智能搜索算法，為了達(dá)到目標(biāo)節(jié)點(diǎn)，它會(huì)做出探索哪個(gè)節(jié)點(diǎn)和探索多少個(gè)節(jié)點(diǎn)的決定。最佳優(yōu)先搜索維持著開放節(jié)點(diǎn)和封閉節(jié)點(diǎn)的列表，就像深度優(yōu)先搜索和廣度優(yōu)先搜索一樣。開放節(jié)點(diǎn)是搜索邊緣上的節(jié)點(diǎn)，以后可能要進(jìn)一步探索到。封閉節(jié)點(diǎn)是不再探索的節(jié)點(diǎn)，將形成解的基礎(chǔ)。在開放列表中，節(jié)點(diǎn)是按照它們接近目標(biāo)狀態(tài)的啟發(fā)式估計(jì)值順序排列的。因此，每次迭代搜索，考慮在開放列表上最有希望的節(jié)點(diǎn)，從而將最好的狀態(tài)放在開放列表前端。重復(fù)狀態(tài)（例如，可以通過多條路徑到達(dá)的狀態(tài)，但是具有不同的代價(jià)）是不會(huì)被保留的。相反，花費(fèi)最少代價(jià)、最有希望以及在啟發(fā)法下最接近目標(biāo)狀態(tài)的重復(fù)節(jié)點(diǎn)被保留了。4.3.4最佳優(yōu)先搜索從以上討論可以看出，在爬山法中，最佳優(yōu)先搜索的最顯著優(yōu)勢是它可以通過回溯到開放列表的節(jié)點(diǎn)，從錯(cuò)誤、假線索、死胡同中恢復(fù)。如果要尋找可替代的解，它可以重新考慮在開放列表中的子節(jié)點(diǎn)。如果按照相反的順序追蹤封閉節(jié)點(diǎn)列表，忽略到達(dá)死胡同的狀態(tài)，就可以用來表示所找到的最佳解。如上所述，最佳優(yōu)先搜索維持開放節(jié)點(diǎn)列表的優(yōu)先級(jí)隊(duì)列?；叵胍幌?，優(yōu)先級(jí)隊(duì)列具有的特征：可以插入的元素、可以刪除最大節(jié)點(diǎn)（或最小節(jié)點(diǎn)）。圖4-10說明了最佳優(yōu)先搜索的工作原理。注意，最佳優(yōu)先搜索的效率取決于所使用的啟發(fā)式測度的有效性。4.3.4最佳優(yōu)先搜索圖4-10最佳優(yōu)先搜索4.3.4最佳優(yōu)先搜索開放列表保存了每一層中到達(dá)自標(biāo)節(jié)點(diǎn)最低估計(jì)代價(jià)節(jié)點(diǎn)。保存在開放節(jié)點(diǎn)列表中相對較早的節(jié)點(diǎn)稍后會(huì)較早被探索?！矮@勝”路徑是A→C→F→H。如果存在這條路徑，搜索總是會(huì)找到這條路徑。好的啟發(fā)式測度將會(huì)很快找到一個(gè)解，甚至找到可能的最佳解。糟糕的啟發(fā)式測度有時(shí)會(huì)找到解，但即使找到了，這些解通常也不是最佳的。4.3.5分支定界法——找到最佳解前面的搜索算法系列有一個(gè)共同的屬性：為了指導(dǎo)前進(jìn)，每個(gè)算法都使用到目標(biāo)剩余距離的啟發(fā)式估計(jì)值?，F(xiàn)在，我們將注意力轉(zhuǎn)向向后看的搜索算法集合，從這個(gè)意義上來說，向后就是到初始節(jié)點(diǎn)的距離（例如g(n)，這既不是整條路徑的估值，也不是一個(gè)大的分量。通過將g(n)包含在內(nèi)，作為總估值路徑代價(jià)f(n)的一部分，就不太可能搜索到到達(dá)目標(biāo)的次優(yōu)路徑。4.3.5分支定界法——找到最佳解我們將第一個(gè)算法稱為“普通”分支定界法。這種算法在文獻(xiàn)中通常稱為統(tǒng)一代價(jià)搜索。按照遞增的代價(jià)——更精確地說，按照非遞減代價(jià)制訂路徑。路徑的估計(jì)代價(jià)很簡單：f(n)=g(n)，不采用剩余距離的啟發(fā)式搜索；或等價(jià)地說，估計(jì)h(n)處處都為0。這種方法與廣度優(yōu)先搜索的相似性顯而易見，即首先訪問最靠近起始節(jié)點(diǎn)的節(jié)點(diǎn)。但是，使用分支定界法，代價(jià)值可以假設(shè)為任何正實(shí)數(shù)值。這兩個(gè)搜索之間的主要區(qū)別是，BFS努力找到通往目標(biāo)的某一路徑，然而分支定界法努力找到一條最優(yōu)路徑。4.3.5分支定界法——找到最佳解使用分支定界法時(shí)，一旦找到了一條通往目標(biāo)的路徑，這條路徑很可能是最優(yōu)的。為了確保這條找到的路徑確實(shí)是最優(yōu)的，分支定界法繼續(xù)生成部分路徑，直到每條路徑的代價(jià)大于或等于所找到的路徑的代價(jià)。圖4-11是用來說明搜索算法的樹。因?yàn)榉种Фń绶?/p>

不采用啟發(fā)式估計(jì)值，所以這些啟發(fā)式估計(jì)值

不包括在圖中。圖4-11沒有啟發(fā)式估計(jì)值的搜索樹4.3.5分支定界法——找到最佳解遵循分支定界法，尋求一條到達(dá)目標(biāo)的最佳路徑的圖4-12（a）~圖4-12（g）。我們觀察到，節(jié)點(diǎn)按照遞增的路徑長度擴(kuò)展。搜索在圖4-12（f）和圖4-12（g）中繼續(xù)，直到任何部分的路徑的代價(jià)大于或等于到達(dá)目標(biāo)的最短路徑21。如圖4-12（g）所示，請觀察分支定界的其余部分。

圖4-12分支定界法4.3.5分支定界法——找到最佳解4.3.5分支定界法——找到最佳解分支定界算法接下來的4個(gè)步驟如下。步驟1：到節(jié)點(diǎn)N的路徑不能被延長。步驟2：下一條最短路徑，A→B→E被延長了；當(dāng)前，它的代價(jià)超過了21。步驟3：到節(jié)點(diǎn)M和N的路徑不能被延長步驟4：最小部分路徑，具有的代價(jià)≤21被延長了。當(dāng)前，代價(jià)是29，超過了開始到目標(biāo)最短路徑。在圖4-12（g）中，分支定界法發(fā)現(xiàn)到達(dá)目標(biāo)的最短路徑是A到C到H到G2，代價(jià)為21。4.3.5分支定界法——找到最佳解a）從根節(jié)點(diǎn)A開始。生成從根開始的路徑b）因?yàn)锽具有最小代價(jià)，所以它被擴(kuò)展了c）在3個(gè)選擇中，C具有最小代價(jià)，因此它被擴(kuò)展了d）節(jié)點(diǎn)H具有最低代價(jià)，因此它被擴(kuò)展了e）發(fā)現(xiàn)了到目標(biāo)G2的路徑，但是為了查看是否有一條路徑到目標(biāo)的距離更小，需要擴(kuò)展到其他分支f）F和N的節(jié)點(diǎn)都具有15的代價(jià)；最右邊的節(jié)點(diǎn)首先擴(kuò)展g）分支定界法的其余部分4.3.5分支定界法——找到最佳解分支定界實(shí)際上是A*算法的一種雛形，其對于每個(gè)擴(kuò)展出來的節(jié)點(diǎn)給出一個(gè)預(yù)期值，如果這個(gè)預(yù)期值不如當(dāng)前已經(jīng)搜索出來的結(jié)果好的話，則將這個(gè)節(jié)點(diǎn)（包括其子節(jié)點(diǎn)）從解答樹中刪去，從而達(dá)到加快搜索速度的目的。4.3.6A*算法A*

算法中更一般的引入了一個(gè)估價(jià)函數(shù)f，其定義為f=g+h。其中g(shù)為到達(dá)當(dāng)前節(jié)點(diǎn)的耗費(fèi)，而h表示對從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的耗費(fèi)的估計(jì)。其必須滿足兩個(gè)條件：（1）h

必須小于等于實(shí)際的從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小耗費(fèi)h*。（2）f

必須保持單調(diào)遞增。4.3.6A*算法A*

算法的控制結(jié)構(gòu)與廣度搜索的十分類似，只是每次擴(kuò)展的都是當(dāng)前待擴(kuò)展節(jié)點(diǎn)中f值最小的一個(gè)，如果擴(kuò)展出來的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)重復(fù)，則刪去這個(gè)節(jié)點(diǎn)。如果與待擴(kuò)展節(jié)點(diǎn)重復(fù)，如果這個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)值較小，則用其代替原待擴(kuò)展節(jié)點(diǎn)。當(dāng)A*算法出現(xiàn)數(shù)據(jù)溢出時(shí)，從待擴(kuò)展節(jié)點(diǎn)中取出若干個(gè)估價(jià)函數(shù)值較小的節(jié)點(diǎn)，然后放棄其余的待擴(kuò)展節(jié)點(diǎn)，從而可以使搜索進(jìn)一步的進(jìn)行下去。1遺傳規(guī)劃2螞蟻聚居地優(yōu)化3模擬退火4粒子群第4節(jié)5禁忌搜索4.4受到自然啟發(fā)的搜索完全搜索整個(gè)狀態(tài)空間可能是一個(gè)艱巨的挑戰(zhàn)。這一節(jié)中的搜索算法，靈感來自于自然系統(tǒng)——包括生物系統(tǒng)和非生物系統(tǒng)。遺傳、蟻群、模擬退火和粒子群這四種典型算法在圖像邊緣檢測、圖像分割、圖像識(shí)別、圖像匹配、圖像分類等領(lǐng)域有廣泛應(yīng)用。目前大多數(shù)人工智能算法還不是特別成熟，隨著科學(xué)的發(fā)展還會(huì)有更多的智能算法被發(fā)現(xiàn)，在圖像處理方面的應(yīng)用也在不斷深化，將多種智能算法進(jìn)行融合將是未來一個(gè)重要的發(fā)展方向。4.4.1遺傳規(guī)劃查爾斯·達(dá)爾文在其1859年出版的巨著《物種起源》中，通過一個(gè)稱為自然選擇的過程，提出了生物種群數(shù)量是如何演化的理論。個(gè)體交配后，它們的后代顯示出來自父母雙方的性狀。具有有利于生存性狀的后代更有可能繁殖。隨著時(shí)間的推移，這些有利的特征可能會(huì)以更大的頻率發(fā)生。一個(gè)很好的例子就是英國的吉普賽蛾。19世紀(jì)初期，大多數(shù)吉普賽蛾是淺灰色的，因?yàn)檫@種顏色是它們的偽裝色，可以迷惑捕食者。但是，此時(shí)工業(yè)革命正進(jìn)行得如火如荼，大量的污染物被排放到工業(yè)化國家的環(huán)境中。原本干凈淺色的樹木蒙上了煙灰，變黑了