人工智能導(dǎo)論Introductiontoartificialintelligence機械工業(yè)出版社2020第4章搜索算法【導(dǎo)讀案例】AI能替代碼農(nóng)編程嗎？討論：1關(guān)于搜索算法2盲目算法3知情搜索4受到自然啟發(fā)的搜索第1節(jié)4.1關(guān)于搜索算法搜索是大多數(shù)人日常生活中的一部分。我們恐怕都有過找不到鑰匙、找不到電視遙控器的經(jīng)歷，然后翻箱倒柜一番折騰。有時候，搜索可能更多的是在大腦中進行的。你可能會突然不記得自己到訪過的地方的名字、不記得熟人的名字，或者不記得曾經(jīng)諳熟于心的歌詞。4.1關(guān)于搜索算法搜索及其執(zhí)行也是人工智能技術(shù)的重要基礎(chǔ)，是人工智能中經(jīng)常遇到的最重要的問題之一。許多算法專門通過列表進行搜索和排序。當(dāng)然，如果數(shù)據(jù)按照邏輯順序組織，那么搜索就會比較方便一些。想象一下，如果姓名和電話號碼隨機排列，那么搜索相對較大城市的電話簿會有多麻煩。因此，搜索和信息組織在智能系統(tǒng)的設(shè)計中發(fā)揮了重要作用。例如人們認為，性能更好的國際象棋博弈程序比同類型的程序更加智能。所謂搜索算法，就是利用計算機的高性能來有目的地窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。搜索過程實際上是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標狀態(tài)的節(jié)點的過程。4.1關(guān)于搜索算法搜索算法根據(jù)初始條件和擴展規(guī)則構(gòu)造一顆“解答樹”并尋找符合目標狀態(tài)的節(jié)點。從最終的算法實現(xiàn)上來看，所有的搜索算法都可以劃分成兩個部分——控制結(jié)構(gòu)（擴展節(jié)點的方式）和產(chǎn)生系統(tǒng)（擴展節(jié)點），而所有的算法優(yōu)化和改進主要都是通過修改其控制結(jié)構(gòu)來完

成的。其實，在這樣的思考過程中，

我們已經(jīng)不知不覺地將一個具體

的問題抽象成了一個圖論的模型

——樹，即搜索算法的使用第

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

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

圖4-55個城市，假設(shè)了城市之間的空中距離，這些城市彼此之間直接相連4.2.3貪婪算法在步驟1中，貪婪方法從成都行進到西安，因為這兩個城市的距離只有606km，西安是最近的城市。（l）在步驟1中，采用V1到Ⅴ5的路徑，因為西安是離成都最近的城市。（2）只有是先前已經(jīng)訪問過的頂點，我們才可以考慮經(jīng)過該頂點的路徑。在步驟2中，下一個生成的路徑直接從V1到V2，它的代價（距離）是1518km。這條直接的路徑比通過V3的路徑便宜，代價為606km+914km=1520km。4.2.3貪婪算法（3）V1到Ⅴ3便宜的路徑是使用從V1到中間節(jié)點（Vi）以及從Vi到V3的最便宜的路徑構(gòu)成的。此處，I等于V2；V1到V3代價最小的路徑經(jīng)過了V2，其代價為1518km+1061km=2579km。然而，V1到V4的直接路徑代價較低（1539hn）。我們直接去了V4（杭州）。4.2.3貪婪算法（4）步驟4：我們正在搜索從V1開始到任何地方的下一條代價最小路徑。我們己經(jīng)得到了V1到V5的代價最小路徑，其代價為606km。第二條代價最小路徑為V1到V2的直接路徑，代價為1518km。V1到Ⅴ4的直接路徑（1539km）比經(jīng)過V5的路徑（606km+1l50km=1756km）以及經(jīng)過V2的路徑（1518km+1134km=2652km），其代價最低。因此，下一條代價最小路徑是那條經(jīng)過V3的路徑（2579km）。4.2.3貪婪算法這里有幾種可能性：V1到V5（代價=606km），然后V5到V2（代價=914km），即從V1到V2，經(jīng)過V5的代價是1520km。然后，你需要從V2到V3（代價為1061km）。從V1到V3，經(jīng)過V5和V2的路徑，其總代價是1520km+1061km=2581km。V1到V2的代價為15181m，V2到V3的代價為1061km，這條路徑的總代價為2579km。V1到V4的代價為1539km，V4到V3的代價為1822km，這條路徑的總代價為3361km。4.2.3貪婪算法我們采用從V1到V3的路徑，這條路徑首先經(jīng)過V2，總代價為2579km。這個例子采用的特定算法是Dijkstra的最短路徑算法，這個算法是貪婪算法的一個例子。使用貪婪算法求解問題效率很高，但有一些問題不能使用這種范式求解，例如旅行銷售員問題。4.2.4旅行銷售員問題在旅行銷售員問題的加權(quán)圖（即邊具有代價的圖）中，給定n個頂點，你必須找到始于某個頂點Vi，有且只有一次經(jīng)過圖中的每個頂點，然后返回Vi的最短路徑。就用前面5個城市的例子。假設(shè)銷售員住在西安，因此必須按照某種次序依次訪問成都、北京、杭州和哈爾濱，然后回到西安。在尋求代價最小的路徑時，旅行銷售員問題基于貪婪算法的解總是訪問下一個最近的城市。4.2.4旅行銷售員問題貪婪算法訪問成都、北京、哈爾濱、杭州，然后終于回到西安。這個路徑的代價是606km+1518km+1061km+1822km+1050km=6057km。如果銷售人員訪問依次北京、哈爾濱、杭州、成都，然后返回西安，那么總累計代價為914km+1061km+1822km+1539km+606km=5942km。顯然，貪婪算法未能找到最佳路徑。4.2.5深度優(yōu)先搜索盲目搜索是不使用領(lǐng)域知識的不知情搜索算法。這些方法假定不知道狀態(tài)空間的任何信息。3種主要算法是：深度優(yōu)先搜索（DFS）、廣度優(yōu)先搜索（BFS）和迭代加深（DFS-ID）的深度優(yōu)先搜索。這些算法都具有如下兩個性質(zhì)：（1）它們不使用啟發(fā)式估計。如果使用啟發(fā)式估計，那么搜索將沿著最有希望得到解決方案的路徑前進。（2）它們的目標是找出給定問題的某個解。4.2.5深度優(yōu)先搜索深度優(yōu)先搜索（DFS），顧名思義，就是試圖盡可能快地深入樹中。每當(dāng)搜索方法可以做出選擇時，它選擇最左（或最右）的分支（通常選擇最左分支）。可以將圖4-6所示的樹作為DFS的一個例子。圖4-6樹的深度優(yōu)先搜索遍歷4.2.5深度優(yōu)先搜索將按照A、B、D、E、C、F、G的順序訪問節(jié)點樹的遍歷算法將多次“訪問”某個節(jié)點，例如，在圖4-6中，依次訪問A、B、D、B、E、B、A、C、F、C、G。4.2.5深度優(yōu)先搜索深度優(yōu)先搜索的基本思想是：從初始節(jié)點S0開始進行節(jié)點擴展，考察S0擴展的最后1個子節(jié)點是否為目標節(jié)點，若不是目標節(jié)點，則對該節(jié)點進行擴展；然后再對其擴展節(jié)點中的最后1個子節(jié)點進行考察，若又不是目標節(jié)點，則對其進行擴展，一直如此向下擴展。當(dāng)發(fā)現(xiàn)節(jié)點本身不能擴展時，對其1個兄弟節(jié)點進行擴展；如果所有的兄弟節(jié)點都不能夠擴展時，則尋找到它們的父節(jié)點，對父節(jié)點的兄弟節(jié)點進行擴展；依次類推，直到發(fā)現(xiàn)目標狀態(tài)Sg為止。因此，深度優(yōu)先搜索法存在搜索和回溯交替出現(xiàn)的現(xiàn)象。4.2.5深度優(yōu)先搜索DFS采用不同的策略來達到目標：在尋找可替代路徑之前，它追求尋找單一的路徑來實現(xiàn)目標，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可較快地得到問題解。但若目標節(jié)點不在該分支上，且該分支又是一個無窮分支，就不可能得到解。所以，DFS是不完備搜索。DFS內(nèi)存需求合理，但是它可能會因偏離開始位置無限遠而錯過了相對靠近搜索起始位置的解。4.2.6廣度優(yōu)先搜索廣度優(yōu)先搜索（BFS，又稱寬度優(yōu)先搜索）是第二種盲目搜索方法。使用BFS，從樹的頂部到樹的底部，按照從左到右的方式（或從右到左，不過一般來說從左到右），可以逐層訪問節(jié)點。要先訪問層次i的所有節(jié)點，然后才能訪問在i+1層的節(jié)點。圖4-7顯示了BFS的遍歷過程。

按照以下順序訪問節(jié)點：A、B、C、

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

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

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

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

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

必須小于等于實際的從當(dāng)前節(jié)點到達目標節(jié)點的最小耗費h*。（2）f

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

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