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

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

我們已經不知不覺地將一個具體

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

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

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

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

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

按照以下順序訪問節點：A、B、C、

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

不采用啟發式估計值，所以這些啟發式估計值

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

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

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

必須小于等于實際的從當前節點到達目標節點的最小耗費h*。（2）f

必須保持單調遞增。4.3.6A*算法A*

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