2023人工智能問(wèn)題算法

PAGEPAGE250人工智能問(wèn)題算法目錄TOC\o"1-2"\h\u11066第1章通過(guò)搜索進(jìn)行問(wèn)題求解 3108551.1問(wèn)題求解智能體 5234431.2問(wèn)題示例 1097621.3搜索算法 17116981.4無(wú)信息搜索策略 2674241.5有信息（啟發(fā)式）搜索策略 40189541.6啟發(fā)式函數(shù) 6127455第2章復(fù)雜環(huán)境中的搜索 737932.1局部搜索和最優(yōu)化問(wèn)題 74112152.2連續(xù)空間中的局部搜索 88309262.3使用非確定性動(dòng)作的搜索 92134722.4部分可觀測(cè)環(huán)境中的搜索 99287152.5在線搜索智能體和未知環(huán)境 11110803第3章對(duì)抗搜索和博弈 12118707第4章約束滿足問(wèn)題 165第1章通過(guò)搜索進(jìn)行問(wèn)題求解在本章中，我們討論一個(gè)智能體是如何向前搜索，找到一個(gè)動(dòng)作序列來(lái)實(shí)現(xiàn)它的最終目標(biāo)。當(dāng)要采取的正確動(dòng)作不是很明顯時(shí)，智能體可能需要提前規(guī)劃：考慮一個(gè)形成通往目標(biāo)狀態(tài)路徑的動(dòng)作序列。這樣的智能體被稱為問(wèn)題求解智能體（problem-solvingagent），它所進(jìn)行的計(jì)算過(guò)程被稱為搜索（search）。如2.4.7節(jié)所述，問(wèn)題求解智能體使用原子（atomic）表示，也就是說(shuō)，世界狀態(tài)被視為一個(gè)整體，其內(nèi)部結(jié)構(gòu)對(duì)問(wèn)題求解算法來(lái)說(shuō)是不可見的。使用狀態(tài)的因子化（factored）表示或結(jié)構(gòu)化（structured）表示的智能體稱為規(guī)劃智能體（planning agent），第7章和第11章中將會(huì)論。我們將在本書中介紹若干搜索算法。在本章中，我們將只考慮最簡(jiǎn)單的環(huán)境，即回合式的、單智能體的、完全可觀測(cè)的、確定性的、靜態(tài)的、離散的和已知的環(huán)境，并對(duì)有信息（informed）算法和無(wú)信息（uninformed）算法進(jìn)行區(qū)分。在有信息算法中，智能體可以估計(jì)自己到目標(biāo)的距離，而在無(wú)信息算法中不能進(jìn)行這樣的估計(jì)。第4章會(huì)討論更一般的環(huán)境中的問(wèn)題，第5章則考慮了多智能體的情形。本章使用了漸近復(fù)雜性的概念（即O(n)表示法）。不熟悉這些概念的讀者可以參閱附錄A。問(wèn)題求解智能體想象一下，一個(gè)智能體正在羅馬尼亞度假。它想?yún)⒂^景點(diǎn)，想學(xué)習(xí)羅馬尼亞語(yǔ)，想享受羅馬尼亞的夜生活但又不想宿醉，等等。這一決策問(wèn)題是復(fù)雜的?，F(xiàn)在，假設(shè)智能體目前位于Arad，并且買了一張第二天從Bucharest起飛且不能退款的機(jī)票。智能體觀察路牌后發(fā)現(xiàn)，從Arad出發(fā)有3條路：一條通往Sibiu，一條通往Timisoara，還有一條通往Zerind。但這都不是它的目的地，所以除非智能體熟悉羅馬尼亞的地理環(huán)境，不然它不知道該走哪條路。[1]如果智能體沒(méi)有額外信息，也就是說(shuō)，如果環(huán)境是未知的（unknown），那么智能體只能隨機(jī)執(zhí)行一個(gè)動(dòng)作。這種情況將在第4章討論。在本章中，我們假設(shè)智能體總是能夠訪問(wèn)與世界相關(guān)的信息，例如圖3-1中的地圖。有了這些信息，智能體可以執(zhí)行以下4個(gè)階段的問(wèn)題求解過(guò)程。目標(biāo)形式化（goal formulation）：智能體的目標(biāo)為到Bucharest。目標(biāo)通過(guò)限制智能體的目的和需要考慮的動(dòng)作來(lái)組織其行為。圖3-1 羅馬尼亞部分地區(qū)的簡(jiǎn)化道路圖，道路距離單位為英里（1英里=1.61千米）問(wèn)題形式化（problemformulation）：智能體刻畫實(shí)現(xiàn)目標(biāo)所必需的狀態(tài)和動(dòng)作——進(jìn)而得到這個(gè)世界中與實(shí)現(xiàn)目標(biāo)相關(guān)的部分所構(gòu)成的抽象模型。對(duì)智能體來(lái)說(shuō)，一個(gè)好的模型應(yīng)該考慮從一個(gè)城市到其相鄰城市的動(dòng)作，這時(shí)，狀態(tài)中只有“當(dāng)前所在城市”會(huì)由于動(dòng)作而改變。搜索（search）：其模型中模擬一系列動(dòng)作，并進(jìn)行搜索，直到找到一個(gè)能到達(dá)目標(biāo)的動(dòng)作序列。這樣的序列稱為解（solution）。智能體可能不得不模擬多個(gè)無(wú)法到達(dá)目標(biāo)的序列，但最終它要么找到一個(gè)解（例如從Arad到Sibiu到Fagaras再到Bucharest），要么發(fā)現(xiàn)問(wèn)題是無(wú)解的。執(zhí)行（execution）：一個(gè)動(dòng)作。一個(gè)重要的性質(zhì)是，在一個(gè)完全可觀測(cè)的、確定性的、已知的環(huán)境中，任何問(wèn)題的解都是一個(gè)固定的動(dòng)作序列：開車到Sibiu，然后到Fagaras，最后到達(dá)Bucharest。如果模型是正確的，那么一旦智能體找到了一個(gè)解，它就可以在執(zhí)行動(dòng)作時(shí)忽略它的感知（“閉上眼睛”），因?yàn)榻庖欢〞?huì)到達(dá)目標(biāo)?？刂评碚摷曳Q之為開環(huán)（open-loop）系統(tǒng)，因?yàn)楹雎愿兄蚱屏酥悄荏w和環(huán)境之間的環(huán)路。如果模型有可能是不正確的，或者環(huán)境是非確定性的，那么監(jiān)控感知的閉環(huán)（closed-loop）方法會(huì)更安全（見4.4節(jié)）。在部分可觀測(cè)或非確定性環(huán)境中，問(wèn)題的解將是一個(gè)根據(jù)感知推薦不同的未來(lái)動(dòng)作的分支策略。例如，智能體可能規(guī)劃從Arad開車到Sibiu，但還需要一個(gè)應(yīng)變規(guī)劃，以防它不小心到了Zerind或者發(fā)現(xiàn)了“Drum?nchis”（道路封閉）的標(biāo)志。搜索問(wèn)題和解搜索問(wèn)題（problem）的形式化定義如下?？赡艿沫h(huán)境狀態(tài)（state）的集合，我們稱之為狀態(tài)空間（statespace）。智能體啟動(dòng)時(shí)的初始狀態(tài)（initialstate），例如Arad。一個(gè)或多個(gè)目標(biāo)狀態(tài)（goalstate）的集合。有時(shí)問(wèn)題只有一個(gè)目標(biāo)狀態(tài)（如Bucharest），有時(shí)存在若干個(gè)可供選擇的目標(biāo)狀態(tài)，也有時(shí)目標(biāo)是由一個(gè)適用于許多狀態(tài)（可能是無(wú)限多個(gè)狀態(tài)）的屬性所定義的。例如，在一個(gè)真空吸塵器世界里，目標(biāo)可能是讓任何位置都沒(méi)有灰塵，而無(wú)論該狀態(tài)的其他情況如何。我們通過(guò)給問(wèn)題指定一個(gè)方法來(lái)將這3種可能性都考慮在內(nèi)。在本章中，為了簡(jiǎn)單起見，我們有時(shí)會(huì)直接用“目標(biāo)”一詞，它表示“任一可能的目標(biāo)狀態(tài)”。智能體可以采取的行動(dòng)（on）。給定一個(gè)狀態(tài)，將返回在s中可以執(zhí)行的有限[2]動(dòng)作集合。我們稱集合中的任一動(dòng)作在s中都是適用的（applicable）。例如：對(duì)于具有無(wú)限多個(gè)動(dòng)作的問(wèn)題，我們需要本章之外的其他技巧。轉(zhuǎn)移模型（transitionmodel）用于描述每個(gè)動(dòng)作所起到的作用。,a將返回在狀態(tài)中執(zhí)行動(dòng)作a所產(chǎn)生的狀態(tài)。例如：動(dòng)作代價(jià)函數(shù)（onotunon），在編程中記作,a,s')，在數(shù)學(xué)運(yùn)算中記作c(s,a,s')。它給出了在狀態(tài)s中執(zhí)行動(dòng)作a從而轉(zhuǎn)移到狀態(tài)s'的數(shù)值代價(jià)。問(wèn)題求解智能體應(yīng)該使用反映其自身性能指標(biāo)的代價(jià)函數(shù)；例如，對(duì)于尋徑智能體，動(dòng)作代價(jià)可能是以英里為單位的長(zhǎng)度（如圖3-1所示），也可能是完成動(dòng)作所花費(fèi)的時(shí)間。一個(gè)動(dòng)作序列形成一條路徑（path），而解（solution）是一條從初始狀態(tài)到某個(gè)目標(biāo)狀態(tài)的路徑。我們假設(shè)動(dòng)作代價(jià)是可累加的；也就是說(shuō)，一條路徑的總代價(jià)是各個(gè)動(dòng)作代價(jià)的總和。最優(yōu)解（optimalsolution）是所有解中路徑代價(jià)最小的解。在本章中，我們假設(shè)所有的動(dòng)作代價(jià)都為正，以減少?gòu)?fù)雜性。[3]，Bellman-Ford算法和Floyd-Warshall算法（本章暫未涉及）可以處理負(fù)代價(jià)動(dòng)作。只要連續(xù)狀態(tài)空間可以用圖（graph）來(lái)表示，圖中的頂點(diǎn)表示狀態(tài)，頂點(diǎn)之間的有向邊表示動(dòng)作。圖3-1所示的羅馬尼亞地圖就是這樣一個(gè)圖，每條道路表示兩種動(dòng)作，即兩個(gè)方向各表示一種。問(wèn)題形式化我們將前文中去往Bucharest的問(wèn)題形式化為一個(gè)模型（model）——一種抽象的數(shù)學(xué)描述，而不是真實(shí)存在的實(shí)物。與簡(jiǎn)單的原子狀態(tài)描述Arad相比，實(shí)際的旅行的世界狀態(tài)包括很多內(nèi)容：旅行伙伴、當(dāng)時(shí)的廣播節(jié)目、窗外的風(fēng)景、附近是否有執(zhí)法人員、到下一個(gè)休息站的距離、道路狀況、天氣、交通等。所有這些因素都被排除在我們的模型之外，因?yàn)樗鼈兣c尋找前往Bucharest的路線問(wèn)題無(wú)關(guān)。從表示中剔除細(xì)節(jié)的過(guò)程稱為抽象（abstraction）。一個(gè)良好的問(wèn)題形式化應(yīng)該具有適度的細(xì)節(jié)層次。如果智能體的動(dòng)作細(xì)化到“右腳向前移動(dòng)1厘米”或“方向盤向左轉(zhuǎn)動(dòng)1度”的層次上，那它可能永遠(yuǎn)都找不到走出停車場(chǎng)的路，更不用說(shuō)去Bucharest了。我們能更精確地定義合適的抽象層級(jí)（levelofabstraction）嗎？我們所選擇的抽象狀態(tài)和動(dòng)作對(duì)應(yīng)于大量具體的世界狀態(tài)和動(dòng)作序列?，F(xiàn)在考慮抽象問(wèn)題的解，例如，從Arad到Sibiu，到Rimnicu Vilcea，到Pitesti，再到Bucharest的路徑。這個(gè)抽象解對(duì)應(yīng)于大量更詳細(xì)的路徑。例如，從Sibiu開往Rimnicu Vilcea的途中，我們可以打開收音機(jī)，而在其他的旅程中關(guān)掉收音機(jī)。如果我們能夠?qū)⑷魏纬橄蠼饧?xì)化為更詳細(xì)的世界中的解，那么這種抽象就是合理的；一個(gè)充分條件是，對(duì)于“inArad”的每個(gè)詳細(xì)狀態(tài)，都有一條到達(dá)“inSibiu”狀態(tài)的詳細(xì)路徑，以此類推。[4]個(gè)動(dòng)作都比原始問(wèn)題更容易，那么抽象是有用的；在我們的示例中，“從Arad開車到Sibiu”的動(dòng)作，任何一個(gè)一般水平的司機(jī)都可以在不進(jìn)一步搜索或規(guī)劃的情況下完成。因此，選擇一個(gè)好的抽象需要?jiǎng)h除盡可能多的細(xì)節(jié)，同時(shí)保留合理性，并確保抽象動(dòng)作易于執(zhí)行。如果沒(méi)有構(gòu)造有用的抽象的能力，智能體將被真實(shí)世界完全淹沒(méi)。參見11.4節(jié)。問(wèn)題示例問(wèn)題求解的方法已被應(yīng)用于大量任務(wù)環(huán)境中。我們?cè)谶@里列出一些典型問(wèn)題，區(qū)分為標(biāo)準(zhǔn)化問(wèn)題和真實(shí)世界問(wèn)題。標(biāo)準(zhǔn)化問(wèn)題（standardizedproblem）常用于說(shuō)明或訓(xùn)練各種問(wèn)題求解方法。它具有簡(jiǎn)潔、準(zhǔn)確的描述，因此適合作為研究人員比較算法性能的基準(zhǔn)。真實(shí)世界問(wèn)題（real-worldproblem），如機(jī)器人導(dǎo)航，則意味著這一問(wèn)題的解是人們實(shí)際使用的，且問(wèn)題的形式化是獨(dú)特的而非標(biāo)準(zhǔn)化的，因?yàn)槔缭跈C(jī)器人導(dǎo)航問(wèn)題中，每個(gè)機(jī)器人具有不同的傳感器，產(chǎn)生不同的數(shù)據(jù)。標(biāo)準(zhǔn)化問(wèn)題網(wǎng)格世界（grid world）問(wèn)題是一個(gè)由正方形單元格組成的二維形陣列，在這個(gè)陣列中，智能體可以從一個(gè)單元格移動(dòng)到另一個(gè)單元格。一般來(lái)說(shuō)，智能體可以水平或垂直地移動(dòng)到任何無(wú)障礙的相鄰單元格，在某些問(wèn)題中還可以沿對(duì)角線移動(dòng)。單元格中可以包含智能體能拿起、推開或施加其他動(dòng)作的物體，也可以存在阻止智能體進(jìn)入單元格內(nèi)的墻壁或其他不可逾越的障礙。2.1節(jié)中的真空吸塵器世界（vacuumworld）可以表示為一個(gè)網(wǎng)格世界問(wèn)題。狀態(tài)：就是智能體和灰塵。對(duì)于只有兩個(gè)單元格的簡(jiǎn)單情形，智能體可以位于這兩個(gè)單元格中的任何一個(gè)，每個(gè)單元格都可能存在灰塵，所以共有2×2×2=8個(gè)狀態(tài)（見圖3-2）。一般來(lái)說(shuō)，存在n環(huán)境有n×2n個(gè)狀態(tài)。初始狀態(tài)：任一狀態(tài)都可以被指定為初始狀態(tài)。動(dòng)作：在只有兩個(gè)單元格的情形中，我們可以定義3吸塵（Suck）、向左（Left）移動(dòng)和向右（Right）移動(dòng)。在二維多單元格世界中，我們則需要更多種移動(dòng)動(dòng)作。我們可以增加向上（Upward）和向下（Downward）的動(dòng)作，從而得到4種絕對(duì)的（absolute）移動(dòng)動(dòng)作，或者可以將其轉(zhuǎn)換為以自我為中心的動(dòng)作，即從相對(duì)于智能體的角度來(lái)定義，例如，向前（Forward）、向后（Backward）、右轉(zhuǎn)（TurnRight）和左轉(zhuǎn)（TurnLeft）。轉(zhuǎn)移模型：Suck將去除單元格內(nèi)的任何灰塵；Forward將智能體朝它所面對(duì)的方向向前移動(dòng)一個(gè)單元格，除非它撞到墻（在這種情況下，這個(gè)行動(dòng)不起作用）。Backward讓智能體朝相反的方向移動(dòng)一個(gè)單元格，而TurnRight和TurnLeft則將智能體的朝向旋轉(zhuǎn)90°。每個(gè)單元格都保持干凈的狀態(tài)。每個(gè)動(dòng)作的代價(jià)都是1。圖3-2 兩個(gè)單元格的真空吸塵器世界的狀態(tài)空間圖。共有8個(gè)狀態(tài)，每個(gè)狀態(tài)有3種動(dòng)作：L=Left（向左）、R=Right（向右）、S=Suck（吸塵）另一種類型的網(wǎng)格世界是推箱子問(wèn)題（sokobanpuzzle），在這個(gè)問(wèn)題中，智能體的目標(biāo)是將一些散落在網(wǎng)格中的箱子推到指定的存儲(chǔ)位置。每個(gè)單元格最多容納一個(gè)箱子。當(dāng)智能體向前移動(dòng)到放有一個(gè)箱子的單元格，而箱子另一側(cè)的單元格為空時(shí)，箱子和智能體都向前移動(dòng)一格。智能體不能把一個(gè)箱子推到另一個(gè)箱子上或墻上。對(duì)于存在n個(gè)無(wú)障礙單元格和b個(gè)箱子的世界，共有個(gè)狀態(tài)；例如，一個(gè)存在12個(gè)箱子的8×8網(wǎng)格中，有超過(guò)200萬(wàn)億個(gè)狀態(tài)。在滑塊問(wèn)題（sliding-tile puzzle）中，若干滑塊（有時(shí)稱為塊片）排列在一個(gè)有若干空白區(qū)域的網(wǎng)格中，其中滑塊可以滑進(jìn)空白區(qū)域。它的一個(gè)變體是汽車華容道問(wèn)題（Rush Hour puzzle），在這個(gè)題中，我們需要在6×6的網(wǎng)格中滑動(dòng)汽車和卡車，目標(biāo)是將一輛汽車從交通堵塞中解救出來(lái)?；瑝K問(wèn)題中最著名的變體是8數(shù)碼問(wèn)題（8-puzzle）（見圖3-3），它由一個(gè)3×3的網(wǎng)格、8個(gè)帶編號(hào)的滑塊和一個(gè)空格組成，目標(biāo)是達(dá)到指定的狀態(tài)，如圖3-3中右側(cè)所示。類似的還有由4×4的網(wǎng)格組成的15數(shù)碼問(wèn)題（15-puzzle）。對(duì)8數(shù)碼問(wèn)題做如下形式化處理。狀態(tài)：指定每個(gè)滑塊位置的狀態(tài)描述。初始狀態(tài)：奇偶性劃分狀態(tài)空間——任何給定目標(biāo)都可以從恰好一半的可能初始狀態(tài)到達(dá)（3.PART）。動(dòng)作：法是假設(shè)空格執(zhí)行Left、Right、Up或Down動(dòng)作。如果空格位于邊緣或角落，則不是所有的動(dòng)作都可用。轉(zhuǎn)移模型：將狀態(tài)和動(dòng)作映射為一個(gè)結(jié)果狀態(tài)；例如，圖中，對(duì)于初始狀態(tài)，我們采取Left動(dòng)作，那么結(jié)果狀態(tài)中滑塊5和空格將交換位置。目標(biāo)狀態(tài)：序編號(hào)指定目標(biāo)狀態(tài)，如圖3-3所示。動(dòng)作代價(jià)：每個(gè)動(dòng)作的代價(jià)都為1。注意，每個(gè)問(wèn)題的形式化都涉及抽象。8數(shù)碼問(wèn)題中的動(dòng)作被抽象為它們的開始狀態(tài)和結(jié)束狀態(tài)，忽略滑塊滑動(dòng)的中間位置。我們已經(jīng)通過(guò)抽象除去了一些動(dòng)作，例如，當(dāng)滑塊被卡住時(shí)需要晃動(dòng)木板，并排除了用刀取出滑塊然后再放回去的可能性。最終只剩下對(duì)規(guī)則的描述，避免了實(shí)際操作的所有細(xì)節(jié)。圖3-3 8數(shù)碼問(wèn)題的一個(gè)典型實(shí)例我們介紹的最后一個(gè)標(biāo)準(zhǔn)化問(wèn)題是由高德納（Knuth, 1964）設(shè)的，它說(shuō)明了無(wú)限狀態(tài)空間是如何產(chǎn)生的。高德納推測(cè)，通過(guò)只由平方根、向下取整和階乘操作組成的序列可以從數(shù)字4得到任何正整數(shù)。例如，我們可以這樣從4得到5：?jiǎn)栴}定義很簡(jiǎn)單，如下所述。狀態(tài)：正實(shí)數(shù)。初始狀態(tài)：4。動(dòng)作：應(yīng)用平方根、向下取整或階乘操作（階乘僅用于整數(shù)）。轉(zhuǎn)移模型：根據(jù)運(yùn)算的數(shù)學(xué)定義給出。目標(biāo)狀態(tài)：所求的正整數(shù)。動(dòng)作代價(jià)：每個(gè)動(dòng)作的代價(jià)都是1。這一問(wèn)題的狀態(tài)空間是無(wú)限的：對(duì)于任意大于2的整數(shù)，階乘操作總是產(chǎn)生一個(gè)更大的整數(shù)。這個(gè)問(wèn)題很有趣，因?yàn)樗剿髁朔浅４蟮臄?shù)字：從4到5的最短路徑生成了數(shù)字(4!)!=620448401733239439360000。無(wú)限狀態(tài)空間經(jīng)常出現(xiàn)在涉及數(shù)學(xué)表達(dá)式生成、電路、證明、程序和其他遞歸定義對(duì)象的任務(wù)中。真實(shí)世界問(wèn)題我們已經(jīng)了解了如何根據(jù)指定的位置和沿著它們之間的邊進(jìn)行的位置轉(zhuǎn)移來(lái)定義尋徑問(wèn)題（route-findingproblem）。尋徑算法有許多應(yīng)用場(chǎng)景。其中一些是上文中羅馬尼亞例子的直接擴(kuò)展，例如提供導(dǎo)航的網(wǎng)站和車載系統(tǒng)等。（需要考慮的主要復(fù)雜因素是因與交通相關(guān)的延遲而導(dǎo)致的代價(jià)變化，以及因道路封閉而導(dǎo)致的路線變更。）另一些例如計(jì)算機(jī)網(wǎng)絡(luò)中的視頻流路由、軍事行動(dòng)規(guī)劃和飛機(jī)航線規(guī)劃系統(tǒng)等，則更加復(fù)雜。下面介紹旅行規(guī)劃網(wǎng)站必須解決的航空旅行問(wèn)題。狀態(tài)：每個(gè)狀態(tài)顯然包括當(dāng)前位置（例如，某個(gè)機(jī)場(chǎng)）間。此外，由于每個(gè)動(dòng)作（一個(gè)航段）的代價(jià)可能依賴于之前的航段、票價(jià)基礎(chǔ)以及它們是國(guó)內(nèi)航班還是國(guó)際航班，狀態(tài)必須記錄這些額外的“歷史”信息。初始狀態(tài)：用戶家所在的機(jī)場(chǎng)。動(dòng)作：飛，如果需要，還要留出足夠的時(shí)間在機(jī)場(chǎng)中轉(zhuǎn)。轉(zhuǎn)移模型：前位置，將航班的到達(dá)時(shí)間作為新的當(dāng)前時(shí)間。目標(biāo)狀態(tài)：目的地城市。有時(shí)目標(biāo)可能更復(fù)雜一點(diǎn)，例如“直達(dá)航班到達(dá)目的地”。動(dòng)作代價(jià)：艙位質(zhì)量、當(dāng)日時(shí)間、飛機(jī)類型、常旅客獎(jiǎng)勵(lì)積分等的組合。商業(yè)旅行咨詢系統(tǒng)使用的就是上述問(wèn)題的形式化。不過(guò)，在處理航空公司錯(cuò)綜復(fù)雜的票價(jià)結(jié)構(gòu)時(shí)，還會(huì)有許多額外的復(fù)雜因素。例如，任何有經(jīng)驗(yàn)的旅行者都知道，并不是所有的航空旅行都能按計(jì)劃進(jìn)行。因此，一個(gè)真正好的系統(tǒng)應(yīng)該包括應(yīng)變規(guī)劃——如航班延誤或者錯(cuò)過(guò)轉(zhuǎn)機(jī)時(shí)的應(yīng)對(duì)方案。旅行問(wèn)題（touring problem）描述的是一組必須訪問(wèn)的地點(diǎn)，而單一目的地。旅行商問(wèn)題（travelingsalespersonproblem，TSP），就是一個(gè)旅行問(wèn)題，即地圖上每個(gè)城市都必須被訪問(wèn)。其目標(biāo)是找到代價(jià)小于C的旅行路線（在優(yōu)化版本中，目標(biāo)是找到代價(jià)最低的旅行路線）。為了提高TSP算法的性能，科研人員付出了大量的努力。該算法也可以擴(kuò)展到處理車隊(duì)問(wèn)題。例如，規(guī)劃波士頓校車路線的搜索優(yōu)化算法為人們節(jié)約了500萬(wàn)美元，減少了交通擁堵和空氣污染，同時(shí)還為司機(jī)和學(xué)生節(jié)省了時(shí)間（Bertsimasetal.,2019）。除了規(guī)劃行程，搜索算法還被用于規(guī)劃自動(dòng)電路板鉆孔機(jī)鉆頭的運(yùn)動(dòng)和裝料機(jī)在車間內(nèi)的移動(dòng)等任務(wù)。超大規(guī)模集成電路布圖（VLSIlayout）問(wèn)題需要在一個(gè)芯片上定位數(shù)百萬(wàn)個(gè)元件和連接點(diǎn)，以最小化芯片面積、電路延遲和雜散電容，并最大化成品率。布圖問(wèn)題在邏輯設(shè)計(jì)階段之后，通常分為兩個(gè)部分：?jiǎn)卧紙D（celllayout）和通道布線（channelrouting）。在單元布圖中，電路的基本元件分組為若干單元，每個(gè)單元執(zhí)行一些特定功能。每個(gè)單元都有固定的占用區(qū)域（大小和形狀），并且需要與其他每個(gè)單元建立一定數(shù)量的連接。單元布圖的目的是將單元彼此不重疊地放置在芯片上，并且單元之間有足夠的空間布置連線。通道布線的目的則是通過(guò)單元之間的間隙為每條導(dǎo)線尋找特定的路線。這些搜索問(wèn)題極其復(fù)雜，但絕對(duì)值得研究。機(jī)器人導(dǎo)航（robotnavigation）是尋徑問(wèn)題的一個(gè)推廣。機(jī)器人不必沿著明確的路徑（如羅馬尼亞的道路）行走，而是可以四處游走，實(shí)際上是自己走自己的路。對(duì)于在平面上移動(dòng)的圓形機(jī)器人，空間本質(zhì)上是二維的。當(dāng)機(jī)器人的手臂和腿也必須受到控制時(shí)，搜索空間就變成了多維的——每個(gè)關(guān)節(jié)角都是一個(gè)維度。為了使基本上連續(xù)的搜索空間變成有限空間，需要一些更先進(jìn)的技術(shù)（見第26章）。除了問(wèn)題的復(fù)雜性外，真正的機(jī)器人還必須處理傳感器讀取錯(cuò)誤、電動(dòng)機(jī)控制中的錯(cuò)誤、部分可觀測(cè)性以及可能改變環(huán)境的其他智能體等問(wèn)題。自20世紀(jì)70年代以來(lái)，由機(jī)器人對(duì)復(fù)雜物體（例如電動(dòng)機(jī)）進(jìn)行自動(dòng)裝配排序（automaticassemblysequencing）已成為標(biāo)準(zhǔn)的工業(yè)實(shí)踐。算法首先找到一個(gè)可行的裝配序列，然后對(duì)裝配過(guò)程進(jìn)行優(yōu)化。將裝配線上的人工勞動(dòng)減少到最低限度可以節(jié)省大量時(shí)間和成本。裝配問(wèn)題的目標(biāo)是找到某個(gè)對(duì)象的各個(gè)零件的組裝順序。如果順序錯(cuò)誤，那么只能撤消某些已完成的工序，否則無(wú)法在序列的后面添加其他部分。檢查序列中動(dòng)作的可行性是與機(jī)器人導(dǎo)航問(wèn)題密切相關(guān)的幾何搜索難題。因此，合法動(dòng)作的生成是裝配排序問(wèn)題中代價(jià)較高的部分。任何實(shí)用算法都必須盡量避免探索全部的狀態(tài)空間，而應(yīng)只探索狀態(tài)空間中的很小一部分。一類重要的裝配問(wèn)題是蛋白質(zhì)設(shè)計(jì)（proteindesign），其目的是找到一種氨基酸序列，該序列能夠折疊成具有正確特性的三維蛋白質(zhì)結(jié)構(gòu)，以治療某些疾病。搜索算法搜索算法（searchalgorithm）將搜索問(wèn)題作為輸入并返回問(wèn)題的解或報(bào)告failure（當(dāng)解不存在時(shí)）。在本章中，我們考慮在狀態(tài)空間圖上疊加一棵搜索樹（search tree）的算法，該算法從初始狀態(tài)形成各條徑，并試圖找到一條可以達(dá)到某個(gè)目標(biāo)狀態(tài)的路徑。搜索樹中的每個(gè)節(jié)點(diǎn)（node）對(duì)應(yīng)于狀態(tài)空間中的一個(gè)狀態(tài)，搜索樹中的邊對(duì)應(yīng)于動(dòng)作。樹的根對(duì)應(yīng)于問(wèn)題的初始狀態(tài)。理解狀態(tài)空間和搜索樹之間的區(qū)別非常重要。狀態(tài)空間描述了世界的（可能無(wú)限的）狀態(tài)集，以及允許從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的動(dòng)作。搜索樹描述了這些狀態(tài)之間通向目標(biāo)的路徑。搜索樹可以有多條路徑（因此可以有多個(gè)節(jié)點(diǎn)）到達(dá)任何給定狀態(tài)，但樹中的每個(gè)節(jié)點(diǎn)都只有唯一一條返回根的路徑（與所有樹一樣）。圖3-4展示了尋找從Arad到Bucharest的路徑的前幾步。搜索樹的根節(jié)點(diǎn)位于初始狀態(tài)，Arad。我們可以按如下方式擴(kuò)展（expand）節(jié)點(diǎn)：考慮該狀態(tài)的可用動(dòng)作，使用函數(shù)查看這些動(dòng)作指向何處，并為每個(gè)結(jié)果狀態(tài)生成（generating）一個(gè)新節(jié)點(diǎn)，稱為子節(jié)點(diǎn)（childnode）或后繼節(jié)點(diǎn)（successor node）。每個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)（parentnode）都是Arad。圖3-4 3棵部分搜索樹，用于尋找從Arad到Bucharest的路線。已擴(kuò)展節(jié)點(diǎn)用淡紫色和粗體字母表示；邊界上已生成但未被擴(kuò)展的節(jié)點(diǎn)用綠色表示；對(duì)應(yīng)于這兩種類型節(jié)點(diǎn)的狀態(tài)集被稱為達(dá)。接下來(lái)可能生成的節(jié)點(diǎn)用虛線表示。注意，在最下面的樹中，有一個(gè)從Arad到Sibiu再到Arad的環(huán)，這不可能是最優(yōu)路徑，因此搜索不應(yīng)該從那里繼續(xù)現(xiàn)在我們必須從這3個(gè)子節(jié)點(diǎn)中選擇一個(gè)考慮下一步擴(kuò)展。這就是搜索的本質(zhì)——先跟蹤一個(gè)選項(xiàng)，之后再考慮其他選項(xiàng)。假定我們選擇先擴(kuò)展Sibiu。結(jié)果如圖3-4中最下面的搜索樹所示，我們得到了6個(gè)未被擴(kuò)展的節(jié)點(diǎn)（以綠色節(jié)點(diǎn)顯示）。我們稱之為搜索樹的邊界（frontier）。任何已經(jīng)生成過(guò)節(jié)點(diǎn)的狀態(tài)都稱為已達(dá)（reached）狀態(tài)（無(wú)論該節(jié)點(diǎn)是否被擴(kuò)展）。[5]圖3-5為疊加在狀態(tài)空間圖上的搜索樹。一些作者將邊界稱為開節(jié)點(diǎn)表閉節(jié)點(diǎn)表一詞來(lái)指代之前已擴(kuò)展的節(jié)點(diǎn)的集合，在我們的術(shù)語(yǔ)中，這些節(jié)點(diǎn)為已達(dá)節(jié)點(diǎn)去掉邊界節(jié)點(diǎn)后的剩余節(jié)點(diǎn)。圖3-5 由圖3-1中的羅馬尼亞問(wèn)題的圖搜索生成的搜索樹序列。在每一階段，我們擴(kuò)展邊界上的每個(gè)節(jié)點(diǎn)，使用所有不指向已達(dá)狀態(tài)的可用動(dòng)作延伸每條路徑。需要注意的是，在第三階段，最高位置的城市（Oradea）有兩個(gè)后繼城市，這兩個(gè)城市都已經(jīng)有其他路徑到達(dá)，所以有路徑可以從Oradea延伸注意，邊界分離（separate）了狀態(tài)空間圖的兩個(gè)區(qū)域，即內(nèi)部區(qū)域（其中每個(gè)狀態(tài)都已被擴(kuò)展）和外部區(qū)域（尚未到達(dá)的狀態(tài)）。該屬性如圖3-6所示。圖3-6 以矩形網(wǎng)格問(wèn)題為例說(shuō)明圖搜索的分離性質(zhì)。邊界（綠色）分離了內(nèi)部（淡紫色）和部（虛線）。邊界是已達(dá)但尚未擴(kuò)展的節(jié)點(diǎn)（及相應(yīng)的狀態(tài)）的集合；內(nèi)部是已被擴(kuò)展的節(jié)點(diǎn)（及相應(yīng)的狀態(tài)）的集合；外部是尚未到達(dá)的狀態(tài)的集合。在（a）中，只有根節(jié)點(diǎn)被擴(kuò)展。在中，上面的邊界節(jié)點(diǎn)被擴(kuò)展。在（c）中，按順時(shí)針順序擴(kuò)展根節(jié)點(diǎn)的其他后繼節(jié)點(diǎn)最佳優(yōu)先搜索我們?nèi)绾螞Q定下一步從邊界擴(kuò)展哪個(gè)節(jié)點(diǎn)？最佳優(yōu)先搜索（best-first search）是一種非常通用的方法，在這種方法中，我們選擇使得某個(gè)評(píng)價(jià)函數(shù)（evaluationfunction）f(n)的值最小的節(jié)點(diǎn)n。算法如圖3-7所示。在每次迭代中，選擇邊界上具有最小f(n)值的一個(gè)節(jié)點(diǎn)，如果它的狀態(tài)是目標(biāo)狀態(tài)，則返回這個(gè)節(jié)點(diǎn)，否則調(diào)用生成子節(jié)點(diǎn)。對(duì)于每個(gè)子節(jié)點(diǎn)，如果之前未到達(dá)過(guò)該子節(jié)點(diǎn)，則將其添加到邊界；如果到達(dá)該子節(jié)點(diǎn)的當(dāng)前路徑的代價(jià)比之前任何路徑都要小，則將其重新添加到邊界。該算法要么返回failure，要么返回一個(gè)節(jié)點(diǎn)（表示一條通往目標(biāo)的路徑）。通過(guò)使用不同的f(n)函數(shù)，可以得到不同的具體算法，本章將介紹這些算法。圖3-7 最佳優(yōu)先搜索算法以及擴(kuò)展節(jié)點(diǎn)的函數(shù)。這里使用的數(shù)據(jù)結(jié)構(gòu)將在3.3.2節(jié)中介紹。的說(shuō)明見附錄B搜索數(shù)據(jù)結(jié)構(gòu)搜索算法需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)跟蹤搜索樹。樹中的節(jié)點(diǎn)（node）由一個(gè)包含4個(gè)組成部分的數(shù)據(jù)結(jié)構(gòu)表示。nod.：節(jié)點(diǎn)對(duì)應(yīng)的狀態(tài)。nod.：父節(jié)點(diǎn)，即樹中生成該節(jié)點(diǎn)的節(jié)點(diǎn)。nod.：父節(jié)點(diǎn)生成該節(jié)點(diǎn)時(shí)采取的動(dòng)作。nod.：從初始狀態(tài)到此節(jié)點(diǎn)的路徑總代價(jià)。在數(shù)學(xué)公式中，一般使用gnod表示。通過(guò)從一個(gè)節(jié)點(diǎn)返回的PARENT指針，我們可以復(fù)原到達(dá)該節(jié)點(diǎn)的路徑上的狀態(tài)和動(dòng)作。從一個(gè)目標(biāo)節(jié)點(diǎn)開始復(fù)原，我們就可以得到問(wèn)題的解。我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)邊界。一個(gè)恰當(dāng)?shù)倪x擇是某種隊(duì)列（queue），因?yàn)檫吔缟系牟僮饔幸韵聨讉€(gè)。on：返回u當(dāng)且僅當(dāng)邊界中沒(méi)有節(jié)點(diǎn)。on：返回邊界中的第一個(gè)節(jié)點(diǎn)并將它從邊界中刪除。on：返回（但不刪除）邊界中的第一個(gè)節(jié)點(diǎn)。nod,on：將節(jié)點(diǎn)插入隊(duì)列中的適當(dāng)位置。搜索算法使用了3種不同類型的隊(duì)列。優(yōu)先隊(duì)列（priorityqueue）首先彈出根據(jù)評(píng)價(jià)函數(shù)f計(jì)算得到的代價(jià)最小的節(jié)點(diǎn)。它被用于最佳優(yōu)先搜索。FIFO隊(duì)列（FIFO 即先進(jìn)先出隊(duì)列（first-in-first-outqueue），首先彈出最先添加到隊(duì)列中的節(jié)點(diǎn)；它被用于廣度優(yōu)先搜索。LIFO隊(duì)列（LIFO 即后進(jìn)先出隊(duì)列（last-in-first-outqueue），也稱為棧（stack），首先彈出最近添加的節(jié)點(diǎn)；它被用于深度優(yōu)先搜索。已達(dá)狀態(tài)可以存儲(chǔ)為一個(gè)查找表（例如，哈希表），其中每個(gè)鍵是一個(gè)狀態(tài)，對(duì)應(yīng)的值是該狀態(tài)的節(jié)點(diǎn)。冗余路徑圖3-4（最下面一排）所示的搜索樹包含了一條從Arad到Sibiu再回到Arad的路徑。這時(shí)我們稱Arad為搜索樹中的一個(gè)重復(fù)狀態(tài)（repeatedstate），在本例中該重復(fù)狀態(tài)是由循環(huán)（cycle）［也稱為環(huán)路（loopypath）］生成的。因此，即使?fàn)顟B(tài)空間只有20種狀態(tài)，完整的搜索樹也是無(wú)限的，因?yàn)楸闅v循環(huán)的頻率沒(méi)有限制。循環(huán)是冗余路徑（redundantpath）的一種特殊情況。例如，我們可以通過(guò)路徑Arad—Sibiu（總長(zhǎng)140英里）或路徑Arad—Zerind—Oradea—Sibiu（總長(zhǎng)297英里）到達(dá)Sibiu。第二條路徑是冗余的——是到達(dá)相同狀態(tài)的一種比較差的方式——在我們尋找最優(yōu)路徑時(shí)不需要考慮它?？紤]一個(gè)10×10網(wǎng)格世界中的智能體，它能夠移動(dòng)到8個(gè)相鄰方格中的任何一個(gè)。如果沒(méi)有障礙，智能體可以在9步或更少的移動(dòng)內(nèi)到達(dá)100個(gè)方格中的任何一個(gè)。但是長(zhǎng)度為9的路徑的數(shù)量幾乎是89（由于網(wǎng)格邊緣的存在，路徑數(shù)稍微少了一點(diǎn)），超過(guò)了1億條。也就是說(shuō)，平均意義下，有超過(guò)100萬(wàn)條長(zhǎng)度為9的冗余路徑到達(dá)同一個(gè)單元格，如果我們消除了冗余路徑，搜索完成的速度可以快大約100萬(wàn)倍。俗話說(shuō)，不記得歷史的算法注定要重復(fù)歷史。有3種方法可以解決這一問(wèn)題。第一，我們可以記住之前到達(dá)的所有狀態(tài)（就像最佳優(yōu)先搜索一樣），時(shí)，它是首選方法。第二，我們不必?fù)?dān)心對(duì)過(guò)去的重復(fù)。在一些問(wèn)題形式化中，很少或不可能出現(xiàn)兩條路徑到達(dá)相同狀態(tài)。以裝配問(wèn)題為例，每個(gè)動(dòng)作都會(huì)將一個(gè)零件添加到一個(gè)不斷發(fā)展的裝配中，零件是有序的，因此可以先添加A，然后再添加B，但不能先添加B，然后再添加A。對(duì)于這些問(wèn)題,果我們不記錄已達(dá)狀態(tài)也不檢查冗余路徑，則可以節(jié)省內(nèi)存空間。如果搜索算法會(huì)檢查冗余路徑，我們稱之為圖搜索（graphsearch）；否則，稱之為樹狀搜索（keh）6。圖37中的算法是一種圖搜索算法；如果刪除所有對(duì)reached的引用，即為樹狀搜索，它使用更少的內(nèi)存，但會(huì)出現(xiàn)到達(dá)相同狀態(tài)的冗余路徑，因此運(yùn)行速度會(huì)更慢。我們稱之為“樹狀搜索”第三，我們可以選擇折中方法，檢查循環(huán)，但通常不檢查冗余路了所有循環(huán)。另一些算法實(shí)現(xiàn)僅跟蹤少數(shù)幾個(gè)鏈接（祖父節(jié)點(diǎn)和曾祖父節(jié)點(diǎn)），循環(huán)（并依靠其他機(jī)制來(lái)處理長(zhǎng)循環(huán)）。問(wèn)題求解性能評(píng)估在開始設(shè)計(jì)各種搜索算法之前，需要考慮在這些算法中進(jìn)行選擇時(shí)所使用的標(biāo)準(zhǔn)。我們可以從以下4個(gè)方面評(píng)價(jià)算法的性能。完備性（completeness）：當(dāng)存在解時(shí)，算法是否能保證找到解，當(dāng)不存在解時(shí)，是否能保證報(bào)告失敗？代價(jià)最優(yōu)性（costoptimality）：它是否找到了所有解中路徑代價(jià)最小的解？[7]一些作者使用“可容許性”這一術(shù)語(yǔ)表示尋找最小代價(jià)解的性質(zhì)，還有一些作者僅使用“”，但這可能與其他類型的最優(yōu)性相混淆。時(shí)間復(fù)雜性（timecomplexity）：找到解需要多長(zhǎng)時(shí)間？可以用秒數(shù)來(lái)衡量，或者更抽象地用狀態(tài)和動(dòng)作的數(shù)量來(lái)衡量?？臻g復(fù)雜性（spacecomplexity）：執(zhí)行搜索需要多少內(nèi)存？為了理解完備性，考慮一個(gè)具有單一目標(biāo)的搜索問(wèn)題。這個(gè)目標(biāo)可能是狀態(tài)空間的任何地方；因此，一個(gè)完備的算法必須能夠系統(tǒng)地探索從初始狀態(tài)可以到達(dá)的每一個(gè)狀態(tài)。在有限狀態(tài)空間中，這是很容易實(shí)現(xiàn)的：只要我們跟蹤路徑并切斷循環(huán)（例如，Arad到Sibiu再到Arad），最終我們將到達(dá)每一個(gè)可到達(dá)的狀態(tài)。在無(wú)限狀態(tài)空間中，則需要更加小心。例如，在高德納的“4”問(wèn)題中反復(fù)應(yīng)用“階乘”操作的算法將沿著從4到4!到(4!)!……的無(wú)限路徑行進(jìn)。同樣地，在一個(gè)沒(méi)有障礙的無(wú)限網(wǎng)格上，沿著直線不停前進(jìn)也會(huì)形成由新狀態(tài)組成的無(wú)限路徑。在這兩種情況下，算法永遠(yuǎn)不會(huì)返回它之前到達(dá)的狀態(tài)，但它是不完備的，因?yàn)闋顟B(tài)空間中的大部分狀態(tài)永遠(yuǎn)都不會(huì)到達(dá)。完備的搜索算法探索無(wú)限狀態(tài)空間的方式必須是系統(tǒng)的（systematic），以確保它最終能夠到達(dá)與初始狀態(tài)相關(guān)的任何狀態(tài)。例如，在無(wú)限網(wǎng)格上，一種系統(tǒng)搜索方法是螺旋路徑，它覆蓋了距離原點(diǎn)s步遠(yuǎn)的所有單元格，然后移動(dòng)到s + 1步遠(yuǎn)的單元格。遺憾的是，一個(gè)不存在解的無(wú)限狀態(tài)空間中，一個(gè)合理的算法會(huì)一直搜索，它不會(huì)終止，因?yàn)樗恢老乱粋€(gè)狀態(tài)是否是目標(biāo)狀態(tài)。時(shí)間復(fù)雜性和空間復(fù)雜性與問(wèn)題的困難程度相關(guān)。在理論計(jì)算機(jī)科學(xué)中，一種典型的度量方式是狀態(tài)空間圖的大小，，其中是圖中頂點(diǎn)（狀態(tài)節(jié)點(diǎn)）的數(shù)量，是邊（不同的狀態(tài)/動(dòng)作對(duì)）的數(shù)量。狀態(tài)空間圖是顯式的數(shù)據(jù)結(jié)構(gòu)（如羅馬尼亞地圖）時(shí)，這種度量是合適的。但在許多人工智能問(wèn)題中，狀態(tài)空間圖只是由初始狀態(tài)、動(dòng)作和轉(zhuǎn)移模型隱式地表示。對(duì)于隱式的狀態(tài)空間，復(fù)雜性可以用3個(gè)量來(lái)衡量：d，最優(yōu)解的深度（depth）或動(dòng)作數(shù)；m，任意路徑的最大動(dòng)作數(shù)；b，需要考慮的節(jié)點(diǎn)的分支因子（branchingfactor）或后繼節(jié)點(diǎn)數(shù)。無(wú)信息搜索策略無(wú)信息搜索算法不提供有關(guān)某個(gè)狀態(tài)與目標(biāo)狀態(tài)的接近程度的任何線索。例如，考慮一個(gè)位于Arad且目標(biāo)為Bucharest的智能體。一個(gè)對(duì)羅馬尼亞地理一無(wú)所知的無(wú)信息智能體無(wú)法判斷第一步應(yīng)該前往Zerind還是Sibiu。相比之下，了解每個(gè)城市位置的有信息智能體（3.5節(jié)）則知道Sibiu距離Bucharest更近，因此Sibiu更有可能在最短路線上。廣度優(yōu)先搜索當(dāng)所有動(dòng)作的代價(jià)相同時(shí)，正確的策略是采用廣度優(yōu)先搜索（breadth-first search），節(jié)點(diǎn)，再擴(kuò)展后繼節(jié)點(diǎn)的后繼，以此類推。這是一種系統(tǒng)的搜索策略，因此即使在無(wú)限狀態(tài)空間上也是完備的。我們可以通過(guò)調(diào)用-實(shí)現(xiàn)廣度優(yōu)先搜索，其中評(píng)價(jià)函數(shù)n是節(jié)點(diǎn)的深度，即到達(dá)該節(jié)點(diǎn)所需的動(dòng)作數(shù)。然而，我們可以通過(guò)一些技巧來(lái)提高算法效率。先進(jìn)先出隊(duì)列比優(yōu)先隊(duì)列速度更快，并且能提供正確的節(jié)點(diǎn)順序：新節(jié)點(diǎn)（總是比其父節(jié)點(diǎn)更深）進(jìn)入隊(duì)列的隊(duì)尾，而舊節(jié)點(diǎn)，即比新節(jié)點(diǎn)淺的節(jié)點(diǎn)，首先被擴(kuò)展。此外，reached可以是一組狀態(tài)，而不是狀態(tài)到節(jié)點(diǎn)的映射，因?yàn)橐坏┑竭_(dá)某個(gè)狀態(tài)，我們就再也找不到到達(dá)該狀態(tài)的更好路徑了。這也意味著我們可以進(jìn)行早期目標(biāo)測(cè)試（earlygoaltest），即在生成節(jié)點(diǎn)后立即檢查該節(jié)點(diǎn)是否為一個(gè)解，而不是像最佳優(yōu)先搜索使用的后期目標(biāo)測(cè)試（lategoaltest）那樣，等節(jié)點(diǎn)彈出隊(duì)列后再檢查該節(jié)點(diǎn)是否為一個(gè)解。圖3-8展示了在二叉樹上進(jìn)行廣度優(yōu)先搜索的過(guò)程，圖3-9展示了使用早期目標(biāo)測(cè)試來(lái)提高效率的算法。圖3-8 簡(jiǎn)單二叉樹上的廣度優(yōu)先搜索。每個(gè)階段接下來(lái)要擴(kuò)展的節(jié)點(diǎn)用三角形標(biāo)記表示圖3-9 廣度優(yōu)先搜索和一致代價(jià)搜索算法廣度優(yōu)先搜索總是能找到一個(gè)動(dòng)作最少的解，因?yàn)楫?dāng)它生成深度為d的節(jié)點(diǎn)時(shí)，說(shuō)明它已經(jīng)生成了深度為d - 1的所有節(jié)點(diǎn)，如果其中個(gè)節(jié)點(diǎn)是解，它應(yīng)該已經(jīng)被找到了。這意味著，對(duì)于所有動(dòng)作都具有相同代價(jià)的問(wèn)題，它是代價(jià)最優(yōu)的，但對(duì)于不具有該特性的問(wèn)題，則不一定是最優(yōu)的。這兩種情況都是完備的。在時(shí)間和空間方面，想象我們?cè)谒阉饕豢镁鈽洌渲忻總€(gè)狀態(tài)都有b個(gè)后繼。搜索樹的根生成b個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)又生成b個(gè)節(jié)點(diǎn)，第二層總共是b2個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)又生成b個(gè)節(jié)點(diǎn)，從而在第三層產(chǎn)生b3個(gè)節(jié)點(diǎn)，以此類推?，F(xiàn)在假設(shè)解的深度為d，那么生成的節(jié)點(diǎn)總數(shù)為所有節(jié)點(diǎn)都存儲(chǔ)在內(nèi)存中，所以時(shí)間復(fù)雜性和空間復(fù)雜性都是O(bd)。這樣的指數(shù)級(jí)上界是可怕的。舉一個(gè)典型的真實(shí)世界中的例子，考慮一個(gè)分支因子b=10、處理速度為每秒1001KB/節(jié)點(diǎn)的問(wèn)題。深度d=10的搜索將花費(fèi)不到310 TB的內(nèi)存。重的問(wèn)題。但時(shí)間仍然是一個(gè)重要因素。深度d=14存，搜索也需要3.5年。一般來(lái)說(shuō)，除了最小的問(wèn)題實(shí)例，指數(shù)級(jí)復(fù)雜性的搜索問(wèn)題無(wú)法通過(guò)無(wú)信息搜索求解。Dijkstra算法或一致代價(jià)搜索當(dāng)動(dòng)作具有不同的代價(jià)時(shí)，一個(gè)顯而易見的選擇是使用最佳優(yōu)先搜索，評(píng)價(jià)函數(shù)為從根到當(dāng)前節(jié)點(diǎn)的路徑的代價(jià)。理論計(jì)算機(jī)科學(xué)界稱之為Dijkstra算法，人工智能界則稱之為一致代價(jià)搜索（uniform-costsearch）。不同于廣度優(yōu)先搜索在深度一致的波（首先是深度1，然后是深度2，以此類推）中展開，一致代價(jià)搜索算法的思想是在路徑代價(jià)一致的波中展開。該算法可以通過(guò)調(diào)用BEST-FIRST-SEARCH實(shí)現(xiàn)，評(píng)價(jià)函數(shù)為PATH-，如圖39所示?？紤]圖3-10，問(wèn)題是從Sibiu到達(dá)Bucharest。Sibiu的后繼是RimnicuVilcea和Fagaras，代價(jià)分別為80和99。然后擴(kuò)展代價(jià)最小的節(jié)點(diǎn)RimnicuVilcea，加入節(jié)點(diǎn)Pitesti，其代價(jià)為80+97=177。此時(shí)代價(jià)最小的節(jié)點(diǎn)是Fagaras，所以接著擴(kuò)展Fagaras，加入節(jié)點(diǎn)Bucharest，代價(jià)為99+211=310。目標(biāo)節(jié)點(diǎn)是Bucharest，但算法只在擴(kuò)展節(jié)點(diǎn)時(shí)測(cè)試其是否為目標(biāo)節(jié)點(diǎn)，而不是在生成節(jié)點(diǎn)時(shí)測(cè)試，因此它還沒(méi)有檢測(cè)到這是一條通往目標(biāo)的路徑。圖3-10 羅馬尼亞問(wèn)題狀態(tài)空間的一部分，選擇這部分來(lái)說(shuō)明一致代價(jià)搜索算法繼續(xù)進(jìn)行，接下來(lái)選擇Pitesti進(jìn)行擴(kuò)展，添加到Bucharest的第二條路徑，代價(jià)為80+97+101=278。它的代價(jià)更低，因此用它取代reached中之前的路徑，并添加到frontier中。結(jié)果證明，這個(gè)節(jié)點(diǎn)目前具有最小代價(jià)，因此它被認(rèn)為是下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，此時(shí)我們發(fā)現(xiàn)它是一個(gè)目標(biāo)節(jié)點(diǎn)，從而返回該節(jié)點(diǎn)。注意，如果我們?cè)谏晒?jié)點(diǎn)時(shí)檢查目標(biāo)，而不是在擴(kuò)展代價(jià)最小的節(jié)點(diǎn)時(shí)檢查，那么我們將返回一個(gè)代價(jià)更高的路徑（即經(jīng)過(guò)Fagaras的路徑）。一致代價(jià)搜索的復(fù)雜性用C*C*是最優(yōu)解的代價(jià)[8]復(fù)雜性是，比bd大得多。這是因?yàn)橐恢麓鷥r(jià)搜索在探索包含一個(gè)可能有用的高代價(jià)動(dòng)作的路徑之前，可能會(huì)先探索具有低代價(jià)動(dòng)作的大型樹。當(dāng)所有動(dòng)作代價(jià)相同時(shí)，等于bd+1，這時(shí)一致代價(jià)搜索類似于廣度優(yōu)先搜索。在這里，以及整本書中，C*中的“*”表示C的最優(yōu)值。徑探索的困境（假設(shè)所有動(dòng)作的代價(jià)）。深度優(yōu)先搜索與內(nèi)存問(wèn)題深度優(yōu)先搜索（depth-first search）總是優(yōu)先擴(kuò)展邊界中最深的點(diǎn)。它可以通過(guò)調(diào)用來(lái)實(shí)現(xiàn)，其中評(píng)價(jià)函數(shù)為深度的負(fù)數(shù)。然而，它通常不是以圖搜索的形式實(shí)現(xiàn)而是以樹狀搜索（不維護(hù)已達(dá)狀態(tài)表）的形式實(shí)現(xiàn)。搜索的過(guò)程如圖3-11所示，搜索先直接到達(dá)搜索樹的最深層，這里的節(jié)點(diǎn)不存在后繼節(jié)點(diǎn)。然后，搜索將“回退”到下一個(gè)仍存在未擴(kuò)展后繼節(jié)點(diǎn)的最深的節(jié)點(diǎn)。深度優(yōu)先搜索不是代價(jià)最優(yōu)的，它會(huì)返回它找到的第一個(gè)解，即使這個(gè)解不是路徑代價(jià)最小的。圖3-11二叉樹的深度優(yōu)先搜索過(guò)程中，從開始狀態(tài)A到目標(biāo)M，共12步（從左到右，從上到下）未來(lái)節(jié)點(diǎn)用模糊的虛線表示。邊界中沒(méi)有后繼的已擴(kuò)展節(jié)點(diǎn)（用非常模糊的線表示）對(duì)于樹型的有限狀態(tài)空間，算法是有效且完備的。對(duì)于無(wú)環(huán)狀態(tài)空間，算法可能會(huì)通過(guò)不同路徑多次擴(kuò)展同一狀態(tài)，但是（最終）將系統(tǒng)地探索整個(gè)空間。在有環(huán)狀態(tài)空間中，深度優(yōu)先搜索算法可能陷入無(wú)限循環(huán)；因此，一些深度優(yōu)先搜索算法的實(shí)現(xiàn)會(huì)檢查每個(gè)新節(jié)點(diǎn)是否存在循環(huán)。在無(wú)限狀態(tài)空間中，深度優(yōu)先搜索不是系統(tǒng)性的：即使沒(méi)有循環(huán)，它也可能陷入無(wú)限路徑。因此，深度優(yōu)先搜索是不完備的。那么，為什么還會(huì)有人選擇使用深度優(yōu)先搜索而不是廣度優(yōu)先搜索或最佳優(yōu)先搜索呢？答案是，對(duì)于使用樹狀搜索可以處理的問(wèn)題，深度優(yōu)先搜索對(duì)內(nèi)存的需求要小得多。深度優(yōu)先搜索根本不保留reached表，并且邊界集很?。喝绻麑V度優(yōu)先搜索中的邊界集視為不斷擴(kuò)展的球體的表面，那么深度優(yōu)先搜索中的邊界集只是球體的半徑。對(duì)于圖3-11所示的有限樹狀狀態(tài)空間，深度優(yōu)先的樹狀搜索所花費(fèi)的時(shí)間與狀態(tài)數(shù)成正比，其空間復(fù)雜性僅為O(bm)，其中b是分支因子，m是樹的最大深度。有些問(wèn)題在廣度優(yōu)先搜索時(shí)需要EB量級(jí)的內(nèi)存，而在深度優(yōu)先搜索時(shí)僅需要KB量級(jí)。由于其對(duì)內(nèi)存的節(jié)約使用，滿足（第6章）、命題可滿足性（第7章）和邏輯編程（第9章）?；厮菟阉鳎╞acktrackingsearch）是深度優(yōu)先搜索的一種變體，它使用的內(nèi)存更少。（詳見第6章。）在回溯搜索中，一次只生成一個(gè)后繼，而不是所有后繼節(jié)點(diǎn)；每個(gè)部分?jǐn)U展的節(jié)點(diǎn)會(huì)記住下一個(gè)要生成的后繼節(jié)點(diǎn)。此外，回溯通過(guò)直接修改當(dāng)前狀態(tài)描述而不是為一個(gè)全新的狀態(tài)分配內(nèi)存來(lái)生成后繼狀態(tài)。這將內(nèi)存需求減少到只有一個(gè)狀態(tài)描述和一條具有O(m)個(gè)動(dòng)作的路徑；與深度優(yōu)先搜索的O(bm)個(gè)狀態(tài)相比，節(jié)省了大量資源。通過(guò)回溯，我們還可以為當(dāng)前路徑上的狀態(tài)維護(hù)一個(gè)有效的集合數(shù)據(jù)結(jié)構(gòu)，從而使檢查循環(huán)的時(shí)間從O(m)減少到O(1)。為了使回溯起作用，我們必須能夠在回溯時(shí)撤銷每個(gè)動(dòng)作?；厮輰?duì)許多具有大型狀態(tài)描述的問(wèn)題（例如機(jī)器人組裝）的成功求解至關(guān)重要。深度受限和迭代加深搜索為了避免深度優(yōu)先搜索陷入無(wú)限路徑，我們可以使用深度受限搜索（depth-limitedsearch）。這是一個(gè)深度優(yōu)先搜索的改進(jìn)版本，在深度受限搜索中，我們?cè)O(shè)置深度界限，將深度上的所有節(jié)點(diǎn)視為其不存在后繼節(jié)點(diǎn)（見圖3-12）。深度受限搜索算法的時(shí)間復(fù)雜性為O(b)，空間復(fù)雜性為O(b)解，成為不完備的算法。由于深度優(yōu)先搜索是一種樹狀搜索，通常無(wú)法避免在冗余路徑上浪費(fèi)時(shí)間，但我們可以以一定的計(jì)算時(shí)間為代價(jià)來(lái)消除循環(huán)。沿著父節(jié)點(diǎn)向上查看幾個(gè)節(jié)點(diǎn)，就能檢測(cè)出大多數(shù)循環(huán)；更長(zhǎng)的循環(huán)則由深度界限處理。有時(shí)可以根據(jù)對(duì)問(wèn)題的了解選擇一個(gè)較好的深度界限。例如，羅馬尼亞地圖上有20個(gè)城市。因此，=19是一個(gè)有效的界限。但是如果細(xì)研究地圖，我們會(huì)發(fā)現(xiàn)，從任何一個(gè)城市到達(dá)另一個(gè)城市最多需要9步。這個(gè)數(shù)值稱為狀態(tài)空間圖的直徑（diameter），它為我們提供了更好的深度界限，從而可以更有效地進(jìn)行深度受限搜索。然而，對(duì)于大多數(shù)問(wèn)題，在求解問(wèn)題之前，我們無(wú)法知道什么深度界限是好的。迭代加深搜索（iterativedeepeningsearch）解決了如何選擇一個(gè)合適的的問(wèn)題，方法是嘗試所有值：首先是0，然后是1，然后是2，依次類推——直到找到一個(gè)解，或者深度受限搜索返回failure值（而不是cutoff值）。算法如圖3-12所示。迭代加深搜索結(jié)合了深度優(yōu)先和廣度優(yōu)先搜索的許多優(yōu)點(diǎn)。和深度優(yōu)先搜索一樣，它對(duì)內(nèi)存的需求也不大：當(dāng)問(wèn)題存在解時(shí)，是O(bd)，在不存在解的有限狀態(tài)空間上，是O(bm)。與廣度優(yōu)先搜索一樣，迭代加深搜索對(duì)于所有動(dòng)作都具有相同代價(jià)的問(wèn)題是最優(yōu)的，并且在有限無(wú)環(huán)狀態(tài)空間上是完備的，或者說(shuō)在任何有限狀態(tài)空間上，當(dāng)我們檢查路徑節(jié)點(diǎn)上所有的循環(huán)時(shí)，它都是完備的。圖3-12 迭代加深和深度受限樹狀搜索。迭代加深搜索反復(fù)調(diào)用界限遞增的深度受限搜索。它返回以下3種類型的值中的一種：一個(gè)解節(jié)點(diǎn)；當(dāng)它搜索了所有節(jié)點(diǎn)，證明在任何深度都不存解時(shí)，返回failure；當(dāng)在比更深的層上可能存在解時(shí)，返回cutoff。這是一種樹狀搜索算法，它不記錄reached狀態(tài)，因此比最佳優(yōu)先搜索使用的內(nèi)存要少得多，但存在通過(guò)不同路徑多次訪問(wèn)相同狀態(tài)的風(fēng)險(xiǎn)。另外，如果IS-CYCLE檢驗(yàn)函數(shù)不檢查所有環(huán)，那么算法可能會(huì)陷入一個(gè)無(wú)限循環(huán)存在解時(shí)，時(shí)間復(fù)雜性為O(bd)，不存在解時(shí)，時(shí)間復(fù)雜性為O(bm)。與廣度優(yōu)先搜索相同，迭代加深搜索的每次迭代也會(huì)生成一個(gè)新層級(jí)，但是廣度優(yōu)先搜索將所有節(jié)點(diǎn)都存儲(chǔ)在內(nèi)存中，而迭代加深搜索則會(huì)重復(fù)之前的層級(jí)，從而以花費(fèi)更多的時(shí)間為代價(jià)節(jié)省了內(nèi)存。圖3-13展示了二叉搜索樹上的迭代加深搜索的4次迭代，在第4次迭代時(shí)找到了解。迭代加深搜索可能看起來(lái)很浪費(fèi)，因?yàn)樗阉鳂漤敹烁浇臓顟B(tài)被多次重復(fù)生成。但是對(duì)于許多狀態(tài)空間，大多數(shù)節(jié)點(diǎn)位于底層，所以上層是否重復(fù)并不重要。在迭代加深搜索中，底層（深度d）的節(jié)點(diǎn)被生成一次，倒數(shù)第二層的節(jié)點(diǎn)被生成兩次，以此類推，直到根節(jié)點(diǎn)的子節(jié)點(diǎn)（生成d次）。所以在最壞情況下生成的節(jié)點(diǎn)總數(shù)是時(shí)間復(fù)雜性為O(bd)——與廣度優(yōu)先搜索相近。例如，當(dāng)b=10、d=5時(shí)，生成的節(jié)點(diǎn)數(shù)分別為如果你確實(shí)很在意重復(fù)的問(wèn)題，可以使用一種混合方法，即先運(yùn)行廣度優(yōu)先搜索，直到幾乎消耗掉所有可用內(nèi)存，然后對(duì)邊界集中的所有節(jié)點(diǎn)應(yīng)用迭代加深搜索。通常，當(dāng)搜索狀態(tài)空間大于內(nèi)存容量而且解的深度未知時(shí)，迭代加深搜索是首選的無(wú)信息搜索方法。圖3-13 二叉搜索樹上的迭代加深搜索的4次迭代（目標(biāo)為M），深度界限從0到3。注意，內(nèi)節(jié)點(diǎn)形成了一條路徑。三角形標(biāo)記下一步要擴(kuò)展的節(jié)點(diǎn)，邊界為加粗輪廓的綠色節(jié)點(diǎn)，非常模糊的節(jié)點(diǎn)可被證明不可能是這種深度界限下的解的一部分雙向搜索到目前為止，我們介紹的算法都是從一個(gè)初始狀態(tài)開始，最終到達(dá)多個(gè)可能目標(biāo)狀態(tài)中的任意一個(gè)。另一種稱為雙向搜索（bidirectionalsearch）的方法則同時(shí)從初始狀態(tài)正向搜索和從目標(biāo)狀態(tài)反向搜索，直到這兩個(gè)搜索相遇。算法的動(dòng)機(jī)是，要比bd小得多（例如，當(dāng)=d=10時(shí)，復(fù)雜性不到之前算法的五萬(wàn)分之一）。為此，我們需要維護(hù)兩個(gè)邊界集和兩個(gè)已達(dá)狀態(tài)表，并且要能反向推理：如果狀態(tài)s'是s的正向后繼，那么我們需要知道s是s'的反向后繼。當(dāng)兩個(gè)邊界觸碰到一起時(shí)，我們就找到了一個(gè)解。[9]在我們的實(shí)現(xiàn)中，reached數(shù)據(jù)結(jié)構(gòu)支持查詢給定狀態(tài)是否為其成員，而邊界數(shù)據(jù)結(jié)構(gòu)（一個(gè)優(yōu)先隊(duì)列）不支持，因此我們使用reached在這一節(jié)中，我們將介紹雙向最佳優(yōu)先搜索。盡管存在兩個(gè)獨(dú)立的邊界，但接下來(lái)要擴(kuò)展的節(jié)點(diǎn)始終是兩個(gè)邊界中的評(píng)價(jià)函數(shù)值最小的節(jié)的節(jié)點(diǎn)。這將使得速度大大提高。一般的最佳優(yōu)先雙向搜索算法如圖3-14所示。我們傳入問(wèn)題和評(píng)價(jià)函數(shù)的兩個(gè)版本，一個(gè)是正向的（下標(biāo)F），另一個(gè)是反向的（下標(biāo)B）。當(dāng)評(píng)價(jià)函數(shù)是路徑代價(jià)時(shí)，找到的第一個(gè)解將是最優(yōu)解，但是對(duì)于不同的評(píng)價(jià)函數(shù)，這一結(jié)論不一定是正確的。因此，我們會(huì)記錄迄今為止找到的最優(yōu)解，并且可能不得不多次更新最優(yōu)解，直到TERMINATED測(cè)試證明不可能再有更好的解。圖3-14 雙向最佳優(yōu)先搜索維護(hù)兩個(gè)邊界集和兩個(gè)已達(dá)狀態(tài)表。當(dāng)一個(gè)邊界中的路徑到達(dá)另半搜索已達(dá)狀態(tài)時(shí)，這兩條路徑（通過(guò)JOIN-NODES函數(shù)）被連起來(lái)構(gòu)成一個(gè)解。我們得到的第一個(gè)解不一定是最優(yōu)的；函數(shù)TERMINATED決定了什么時(shí)候停止尋找新的解無(wú)信息搜索算法對(duì)比圖3-15根據(jù)3.3.4節(jié)中列出的4個(gè)評(píng)價(jià)標(biāo)準(zhǔn)對(duì)無(wú)信息搜索算法進(jìn)行了備的，并且空間復(fù)雜性和時(shí)間復(fù)雜性受到狀態(tài)空間大小（量，）的限制。圖3-15 搜索算法比較。b是分支因子；m是搜索樹的最大深度；d是最淺層解的深度，當(dāng)不存解時(shí)為m；是深度界限有信息（啟發(fā)式）搜索策略本節(jié)將展示有信息搜索（informedsearch）策略——使用關(guān)于目標(biāo)位置的特定領(lǐng)域線索——如何比無(wú)信息搜索策略更有效地找到解。線索以啟發(fā)式函數(shù)（heuristicfunction）的形式出現(xiàn)，記為h(n)：[10]這看起來(lái)可能很奇怪，啟發(fā)式函數(shù)真正需要的只是節(jié)點(diǎn)的狀態(tài)，但作用對(duì)象卻是節(jié)點(diǎn)。h(n)而不是h(s)，是為了與評(píng)價(jià)函數(shù)(n)和路徑代價(jià)g(n)保持一致。h(n)=從節(jié)點(diǎn)n的狀態(tài)到目標(biāo)狀態(tài)的最小代價(jià)路徑的代價(jià)估計(jì)值例如，在尋徑問(wèn)題中，我們可以通過(guò)計(jì)算地圖上兩點(diǎn)之間的直線距離來(lái)估計(jì)從當(dāng)前狀態(tài)到目標(biāo)的距離。我們將在3.6節(jié)中詳細(xì)研究啟發(fā)式函數(shù)及其來(lái)源。貪心最佳優(yōu)先搜索貪心最佳優(yōu)先搜索（greedybest-firstsearch）是最佳優(yōu)先搜索的一種形式，它首先擴(kuò)展h(n)值最小的節(jié)點(diǎn)——看起來(lái)最接近目標(biāo)的節(jié)點(diǎn)——因?yàn)檫@樣可能可以更快找到解。因此，評(píng)價(jià)函數(shù)f(n)=h(n)。讓我們看看這種算法如何求解羅馬尼亞尋徑問(wèn)題；我們使用直線距離（straight-line distance）作為啟發(fā)式函數(shù)，記為hSLD。如果目標(biāo)是Bucharest，我們需要知道到Bucharest的直線距離，如圖3-16所示。例如，hSad) = 366。注意，無(wú)法從問(wèn)題描述本身（即和函數(shù)）來(lái)計(jì)算hSLD的值。此外，根據(jù)經(jīng)驗(yàn)可知，hSLD與實(shí)際道路距離相關(guān)，因此是一個(gè)有用的啟發(fā)式函數(shù)。圖3-17展示了使用hSLD搜索從Arad到Bucharest的路徑的貪心最佳優(yōu)先搜索的過(guò)程。從Arad擴(kuò)展的第一個(gè)節(jié)點(diǎn)是Sibiu，因?yàn)閱l(fā)式函數(shù)認(rèn)為它比Zerind或Timisoara更接近Bucharest。下一個(gè)要擴(kuò)展的節(jié)點(diǎn)是Fagaras，因?yàn)楦鶕?jù)啟發(fā)式函數(shù)，它現(xiàn)在最接近Bucharest。Fagaras接著生成了Bucharest，即目標(biāo)節(jié)點(diǎn)。對(duì)于這一特定問(wèn)題，使用hSLD的貪心最佳優(yōu)先搜索無(wú)須擴(kuò)展不在解路徑上的節(jié)點(diǎn)就找到了解。但是，它找到的解并不是代價(jià)最優(yōu)的：經(jīng)由Sibiu和Fagaras到達(dá)Bucharest的路徑比經(jīng)過(guò)RimnicuVilcea和Pitesti的路徑長(zhǎng)32英里。這就是為什么這種算法會(huì)被稱為“貪心的”——在每次迭代中，它都會(huì)做出在當(dāng)前看來(lái)最優(yōu)的（即可以最接近目標(biāo)的）選擇，但這也會(huì)導(dǎo)致貪心法在全局意義上可能產(chǎn)生比謹(jǐn)慎的算法更糟糕的結(jié)果。圖3-16 hSLD（到Bucharest的直線距離）的值圖3-17 基于直線距離啟發(fā)式函數(shù)hSLD的貪心最佳優(yōu)先樹狀搜索的各個(gè)階段（目標(biāo)為Bucharest）。節(jié)點(diǎn)上標(biāo)有h值間中是不完備的。最壞情況下的時(shí)間復(fù)雜性和空間復(fù)雜性是。然以達(dá)到O(bm)。A*搜索最常見的有信息搜索算法是A*搜索（A* 讀為“A星搜索”），這是一種最佳優(yōu)先搜索，評(píng)價(jià)函數(shù)為其中g(shù)(n)是從初始狀態(tài)到節(jié)點(diǎn)n的路徑代價(jià)，h(n)是從節(jié)點(diǎn)n到一個(gè)目標(biāo)狀態(tài)的最短路徑的代價(jià)估計(jì)值，因此我們有f(n)=經(jīng)過(guò)n到一個(gè)目標(biāo)狀態(tài)的最優(yōu)路徑的代價(jià)估計(jì)值在圖3-18中，我們展示了目標(biāo)為Bucharest的A*搜索過(guò)程。g的值由圖3-1中的動(dòng)作代價(jià)計(jì)算得到，hSLD的值在圖3-16中給出。注意，Bucharest首先出現(xiàn)在圖3-18的步驟e的邊界中，但算法并沒(méi)有選擇它來(lái)進(jìn)行擴(kuò)展（因此它沒(méi)有被檢測(cè)為一個(gè)解），因?yàn)榇藭r(shí)它不是邊界中代價(jià)最小的節(jié)點(diǎn)（f=450）——代價(jià)最小的節(jié)點(diǎn)是Pitesti（f=417）。換句話說(shuō)，可能存在一個(gè)經(jīng)過(guò)Pitesti的解，代價(jià)低至417，所以算法不會(huì)滿足于一個(gè)代價(jià)為450的解。在圖3-18的步驟f中，另一條到Bucharest的路徑此時(shí)代價(jià)最?。╢=418），因此它被選中并被檢測(cè)為最優(yōu)解。A*搜索是完備的。[11]它是否是代價(jià)最優(yōu)則取決于啟發(fā)式函數(shù)的某些性質(zhì)。一個(gè)關(guān)鍵性質(zhì)是可容許性（admissibility）：一個(gè)可容許的啟發(fā)式（admissible heuristic）函數(shù)永遠(yuǎn)不會(huì)高估到達(dá)某個(gè)目標(biāo)的代價(jià)（因此，一個(gè)可容許的啟發(fā)式函數(shù)是樂(lè)觀的。）再?gòu)?qiáng)調(diào)一次，假設(shè)所有動(dòng)作的代價(jià)都 ，狀態(tài)空間要么有解，要么有限。對(duì)于可容許的啟發(fā)式函數(shù)，A*是代價(jià)最優(yōu)的，我們可以通過(guò)反證法來(lái)證明這一點(diǎn)。假設(shè)最優(yōu)路徑的代價(jià)為C*，但是該算法返回的路徑代價(jià)為CC*，那么最優(yōu)路徑上一定存在某個(gè)未擴(kuò)展的節(jié)點(diǎn)n（因?yàn)槿绻顑?yōu)路徑上的所有節(jié)點(diǎn)都已被擴(kuò)展，那么算法返回的將是這個(gè)最優(yōu)解）。因此，使用符號(hào)g*(n)表示從起點(diǎn)到n的最優(yōu)路徑的代價(jià)，h*(n)表示從n到最近目標(biāo)的最優(yōu)路徑的代價(jià)，我們將得到第一行和最后一行矛盾，所以“算法可能返回次優(yōu)路徑”的假設(shè)一定是錯(cuò)誤的——A*一定只返回代價(jià)最優(yōu)路徑。另一個(gè)稍強(qiáng)的性質(zhì)為一致性（consistency）。如果對(duì)于每個(gè)節(jié)點(diǎn)n以及由動(dòng)作a生成的n的每個(gè)后繼節(jié)點(diǎn)n' 有以下條件，則啟發(fā)式函數(shù)是一致的：這是三角不等式（triangle inequality）的一種形式，它規(guī)定三角的一條邊不能大于其他兩條邊之和（見圖3-19）。一致的啟發(fā)式函數(shù)的一個(gè)實(shí)例是上文中的直線距離hSLD。圖3-18 A*搜索的各個(gè)階段（目標(biāo)為Bucharest）。節(jié)點(diǎn)上標(biāo)有f=g+h，h值為圖3-16中得到的到Bucharest的直線距離圖3-19 三角不等式：如果啟發(fā)式函數(shù)h是一致的，那么單個(gè)數(shù)值h(n)小于從n到n'的動(dòng)作代值c(n,a,n')加上啟發(fā)式函數(shù)的估計(jì)值h(n')的和一致的啟發(fā)式函數(shù)都是可容許的（反過(guò)來(lái)不成立），因此，使用一發(fā)式函數(shù)的A*搜索都是代價(jià)最優(yōu)的。此外，如果使用一致的啟發(fā)式函數(shù)，算法第一次到達(dá)某個(gè)狀態(tài)時(shí)，它就在一條最優(yōu)路徑上，因此我們永遠(yuǎn)不需要將某個(gè)狀態(tài)重復(fù)添加到邊界中，也不必更改reached中的條目。但是，如果使用不一致的啟發(fā)式函數(shù)，最終可能導(dǎo)致多個(gè)路徑到達(dá)相同狀態(tài)，而且如果每條新路徑的路徑代價(jià)都小于前一條路徑，最終中該狀態(tài)會(huì)有多個(gè)節(jié)點(diǎn)，這會(huì)耗費(fèi)時(shí)間和空間。因此，有些A*搜索算法的實(shí)現(xiàn)會(huì)注意讓一個(gè)狀態(tài)只進(jìn)入邊界一次，如果找到了到達(dá)該狀態(tài)的更優(yōu)路徑，那么該狀態(tài)的所有后繼都會(huì)更新（這要求節(jié)點(diǎn)除了父指要有子指針）。這些復(fù)雜性使得許多研究人員在實(shí)現(xiàn)A*搜索時(shí)避免使用不一致的啟發(fā)式函數(shù)，但費(fèi)爾納等人（Felner et al., 2011）為，最壞的結(jié)果在實(shí)踐中很少發(fā)生，因此不應(yīng)該害怕不一致的啟發(fā)式函數(shù)。如果采用不可容許的啟發(fā)式函數(shù)，那么A*搜索可能是代價(jià)最優(yōu)的，也可能不是。存在兩種情況使得A*搜索是代價(jià)最優(yōu)的：第一，如果存在一條代價(jià)最優(yōu)路徑，對(duì)于該路徑上的所有節(jié)點(diǎn)n，h(n)都是可容許的，那么無(wú)論啟發(fā)式函數(shù)在路徑外狀態(tài)上的值如何，算法都能找到這條路徑。第二，假設(shè)最優(yōu)解的代價(jià)為C*，次優(yōu)解的代價(jià)為C2，如果h(n)高估了部分代價(jià)但又沒(méi)有高估太多，都不超過(guò)C2 ? 的解是代價(jià)最優(yōu)的。搜索等值線一種對(duì)搜索進(jìn)行可視化的方法是在狀態(tài)空間中繪制等值線（contour），就像在地形圖中繪制等高線一樣。如圖3-20所示，在標(biāo)記為400的等值線內(nèi)，所有節(jié)點(diǎn)都有，以此類推因?yàn)锳*擴(kuò)展的是f代價(jià)最小的邊界節(jié)點(diǎn)，所以它是從初始節(jié)點(diǎn)扇形地向外擴(kuò)展，以f值遞增的同心帶狀方式添加節(jié)點(diǎn)。一致代價(jià)搜索中也存在等值線，但是等值線表示g代價(jià)，而不是g+h。一致代價(jià)搜索中，等值線將以初始狀態(tài)為圓心呈“圓形”向各個(gè)方向均勻擴(kuò)展，而不是偏向于目標(biāo)狀態(tài)。對(duì)于具有好的啟發(fā)式函數(shù)的A*搜索，g+h帶將朝一個(gè)目標(biāo)狀態(tài)延伸（如圖3-20所示），周圍收斂變窄。需要清楚的是，擴(kuò)展路徑時(shí)，g代價(jià)是單調(diào)的（monotonic）：路徑代價(jià)始終隨著路徑的延伸而不斷增加，因?yàn)閯?dòng)作代價(jià)始終為正。[12]因此，所得到的同心等值線彼此不會(huì)交叉，如果希望畫出的等值線足夠精細(xì)，則可以在任何路徑上的任意兩個(gè)節(jié)點(diǎn)之間畫一條線。從技術(shù)上講，始終保持增加的代價(jià)稱為“嚴(yán)格單調(diào)的”；永遠(yuǎn)不會(huì)減少但可能保持不變的代“單調(diào)的”。但代價(jià)是否單調(diào)遞增則并不顯然。當(dāng)你將一條路徑從n擴(kuò)n'時(shí)，代價(jià)變。消去g(n)項(xiàng)，我們可以看到，當(dāng)且僅當(dāng)時(shí)，路徑代價(jià)單調(diào)遞增。換句話說(shuō)，當(dāng)且僅當(dāng)啟發(fā)式函數(shù)是一致的時(shí)，路徑代價(jià)單調(diào)遞增。[13]但需要注意的是，一條路徑可能會(huì)在一行中貢獻(xiàn)若干個(gè)具有相同g(n) + h(n)得分的節(jié)點(diǎn)；當(dāng)h的減少量恰好等于剛剛采取的動(dòng)作代時(shí)，就會(huì)發(fā)生這種情況（例如，在一個(gè)網(wǎng)格問(wèn)題中，當(dāng)n與目標(biāo)在同一行然后向目標(biāo)邁進(jìn)一步時(shí)，g增加1，h減少1）。如果C*是最優(yōu)解路徑的代價(jià)，那么以下說(shuō)法成立?！皢握{(diào)啟發(fā)式函數(shù)”這一術(shù)語(yǔ)是“一致的啟發(fā)式函數(shù)”的同義詞。這兩種觀點(diǎn)是獨(dú)立（Pearl,1984）。的所有節(jié)點(diǎn)。我們稱這些節(jié)點(diǎn)為必然擴(kuò)展節(jié)點(diǎn)（surelyexpandednode）。搜索可能會(huì)在選出目標(biāo)節(jié)點(diǎn)之前擴(kuò)展某些恰好在“線”（即f(nC*）上的節(jié)點(diǎn)。的節(jié)點(diǎn)。圖3-20 羅馬尼亞地圖，其中等值線為f=380、f=400和f=420，初始狀態(tài)為Arad。給定等值內(nèi)的節(jié)點(diǎn)的代價(jià)f=g+h小于或等于等值線值我們認(rèn)為具有一致啟發(fā)式函數(shù)的A*搜索是效率最優(yōu)（optimallyefficient）的，因?yàn)槿魏螐某跏紶顟B(tài)擴(kuò)展搜索路徑并使用相同啟發(fā)式信息的算法都必須擴(kuò)展A*的所有必然擴(kuò)展節(jié)點(diǎn)（因?yàn)槿魏我粋€(gè)必然擴(kuò)展節(jié)點(diǎn)都可能是某個(gè)最優(yōu)解的一部分）。對(duì)于f(n)=C*的節(jié)點(diǎn)，某個(gè)算法可能運(yùn)氣好，首先選擇了最優(yōu)節(jié)點(diǎn)，而另一個(gè)算法就沒(méi)這么幸運(yùn)。我們?cè)诙x最優(yōu)效率時(shí)不考慮這種差異。A*之所以高效，是因?yàn)樗鼤?huì)對(duì)那些對(duì)于尋找最優(yōu)解沒(méi)有幫助的搜索樹節(jié)點(diǎn)進(jìn)行剪枝（pruning）。在圖3-18b中，我們看到，對(duì)于Timisoara，f=447；對(duì)于Zerind，f=449。即使它們是根的子節(jié)點(diǎn)并且是采用一致代價(jià)搜索或廣度優(yōu)先搜索時(shí)首先擴(kuò)展的節(jié)點(diǎn)，它們也永遠(yuǎn)不會(huì)被A*搜索擴(kuò)展，因?yàn)锳*會(huì)首先找到f=418來(lái)說(shuō)，剪枝（不必進(jìn)行檢查就可以排除不正確的答案）非常重要。在所有這些算法中，A*搜索都是完備的、代價(jià)最優(yōu)的和效率最優(yōu)A*搜索需求。問(wèn)題在于，對(duì)于許多問(wèn)題，所擴(kuò)展的節(jié)點(diǎn)數(shù)可能是解路徑長(zhǎng)度的指數(shù)級(jí)。例如，考慮一個(gè)具有超強(qiáng)吸力的真空吸塵器世界，它可以以單位代價(jià)清理任一方格卻不需要訪問(wèn)該方格。在這種情況下，可以按任何順序清理方格。如果開始時(shí)有N個(gè)臟的方格，則有2N種狀態(tài)，其中某個(gè)子集已被清理；所有這些狀態(tài)都在最優(yōu)解路徑上，因此滿足，所以所有這些狀態(tài)都會(huì)被A*搜索訪問(wèn)。滿意搜索：不可容許的啟發(fā)式函數(shù)與加權(quán)A*搜索A*搜索有很多好的性質(zhì)，但它擴(kuò)展了大量節(jié)點(diǎn)。如果我們?cè)敢饨邮艽蝺?yōu)但“足夠好”的解——我們稱之為滿意（satisficing）解，則可以探索更少的節(jié)點(diǎn)（花費(fèi)更少的時(shí)間和空間）。如果我們?cè)试SA*搜索使用不可容許的啟發(fā)式函數(shù)（inadmissibleheuristic）（它可能會(huì)高估到達(dá)某個(gè)目標(biāo)的代價(jià)），那么我們就有可能錯(cuò)過(guò)最優(yōu)解，但是該啟發(fā)式函數(shù)可能更準(zhǔn)確，從而減少了需要擴(kuò)展的節(jié)點(diǎn)數(shù)。例如，道路工程師知道彎道指數(shù)（detourindex）的概念，它是應(yīng)用于直線距離的乘數(shù)，用來(lái)說(shuō)明道路的典型曲率。彎道指數(shù)1.3意味著如果兩個(gè)城市的直線距離相距10千米，那么它們之間的最優(yōu)路徑的一個(gè)恰當(dāng)?shù)墓烙?jì)值是13千米。對(duì)于大多數(shù)地區(qū)，彎道指數(shù)的范圍是1.2到1.6。不僅僅是與道路相關(guān)的問(wèn)題，我們還可以將這一思想應(yīng)用于任何問(wèn)題，我們采用一種稱為加權(quán)A*搜索（weighted A* search）的方法，啟發(fā)式函數(shù)的值進(jìn)行更重的加權(quán)，評(píng)價(jià)函數(shù)為，其中。圖3-21為一個(gè)網(wǎng)格世界中的搜索問(wèn)題。在圖3-21a中，A*搜索必須探索大部分狀態(tài)空間才能找到最優(yōu)解。在圖3-21b中，加權(quán)A*搜索找到一個(gè)代價(jià)稍高的解，但搜索時(shí)間要快得多。我們看到，加權(quán)搜索使得已達(dá)狀態(tài)的等值線專注于趨向某個(gè)目標(biāo)。這意味著需要探索的狀態(tài)變少，但如果最優(yōu)路徑偏離加權(quán)搜索的等值線（就像在這種情況下一樣），則無(wú)法找到最優(yōu)路徑。一般來(lái)說(shuō)，如果最優(yōu)解的代價(jià)是C*，那么加權(quán)A*搜索將找到一個(gè)代價(jià)介于C*和W×C*之間的解；但在實(shí)踐中，通常結(jié)果更接近于C*而不是W×C*。圖3-21 同一網(wǎng)格上的兩種搜索：（a）A*搜索，（b）加權(quán)A*搜索，權(quán)重W=2?；疑€條表示障礙，紫色線是一條從綠色起始點(diǎn)到紅色目標(biāo)點(diǎn)的路徑，較小的點(diǎn)是每次搜索到達(dá)的狀態(tài)。在這個(gè)特定問(wèn)題上，加權(quán)A*搜索探索的狀態(tài)數(shù)不到A*搜索探索的狀態(tài)數(shù)的七分之一，找到的徑的代價(jià)只比最優(yōu)代價(jià)大了5%我們已經(jīng)考慮過(guò)以各種方式組合g和h來(lái)評(píng)價(jià)狀態(tài)的搜索方法；加權(quán)A*搜索可以看作是其他方法的一般化。一致代價(jià)搜索：貪心最佳優(yōu)先搜索：你可以稱加權(quán)A*搜索為“有點(diǎn)貪心的搜索”：就像貪心最佳優(yōu)先搜索一樣，它使得搜索專注于趨向一個(gè)目標(biāo)；但是，它不會(huì)完全忽略路徑代價(jià)，并且會(huì)暫停代價(jià)高昂但進(jìn)展甚微的路徑。次優(yōu)的搜索算法有很多，其區(qū)別在于“足夠好”的標(biāo)準(zhǔn)。在有界次優(yōu)搜索（boundedsuboptimalsearch）中，我們尋找一個(gè)能保證代價(jià)在最優(yōu)代價(jià)的常數(shù)因子W倍內(nèi)的解。加權(quán)A*搜索提供了這一保證。在有界代價(jià)搜索（bounded-costsearch）中，我們尋找一個(gè)代價(jià)小于某個(gè)常數(shù)C的解。在無(wú)界代價(jià)搜索（unbounded-cost search）中，我們接受任何代的解，只要能快速找到它。無(wú)界代價(jià)搜索算法的一個(gè)例子是快速搜索（speedysearch），它是一種貪心最佳優(yōu)先搜索，使用到達(dá)目標(biāo)所需動(dòng)作個(gè)數(shù)的估計(jì)值作為啟發(fā)式函數(shù)，不考慮這些動(dòng)作的代價(jià)。因此，對(duì)于所有動(dòng)作都具有相同代價(jià)的問(wèn)題，它等于貪心最佳優(yōu)先搜索，但當(dāng)動(dòng)作具有不同代價(jià)時(shí)，它往往會(huì)導(dǎo)致搜索快速找到一個(gè)代價(jià)可能很高的解。內(nèi)存受限搜索A*搜索的主要問(wèn)題是它對(duì)內(nèi)存的使用較多。在本節(jié)中，我們將介紹一些可以節(jié)省空間的實(shí)現(xiàn)技巧和一些能夠更好地利用可用空間的全新算法。內(nèi)存被分為frontier狀態(tài)和reached狀態(tài)。在我們所實(shí)現(xiàn)的最佳優(yōu)先搜索中，邊界上的狀態(tài)存儲(chǔ)在兩個(gè)位置：邊界中的一個(gè)節(jié)點(diǎn)（因此我們可以決定下一步擴(kuò)展哪個(gè)節(jié)點(diǎn)）和已達(dá)狀態(tài)表中的一個(gè)表項(xiàng)（因此我們知道之前是否訪問(wèn)過(guò)該狀態(tài)）。對(duì)于許多問(wèn)題（例如探索網(wǎng)格），這種重復(fù)不是關(guān)注點(diǎn)，因?yàn)閒rontier要比reached小得多，所以復(fù)制邊界中的狀態(tài)所需內(nèi)存相對(duì)較少。但是有些算法實(shí)現(xiàn)只保留這兩個(gè)位置中的其中一個(gè)，從而節(jié)省了一點(diǎn)空間，其代價(jià)是算法變得更復(fù)雜（可能會(huì)減慢速度）。另一種可能性是，當(dāng)我們能夠證明不再需要某些狀態(tài)時(shí)，就將它們從reached中刪除。對(duì)于某些問(wèn)題，我們可以利用分離性質(zhì)（圖3-6），同時(shí)禁止掉頭行動(dòng)，以確保所有行動(dòng)要么是從邊界向外移動(dòng)，要么是移動(dòng)到另一個(gè)邊界狀態(tài)。在這種情況下，我們只需檢查邊界就能判斷是否有冗余路徑，并且可以刪除reached狀態(tài)表。對(duì)于其他問(wèn)題，我們可以維護(hù)引用計(jì)數(shù)（reference count）——達(dá)某一狀態(tài)的次數(shù)，并且在再也沒(méi)有路徑可以到達(dá)該狀態(tài)時(shí)將其從reached表中刪除。例如，在網(wǎng)格世界中，每個(gè)狀態(tài)只能從它的4個(gè)鄰居狀態(tài)到達(dá)，一旦我們已經(jīng)到達(dá)了一個(gè)狀態(tài)4次，就可以將它從表中刪除?，F(xiàn)在，我們考慮旨在節(jié)省內(nèi)存使用的新算法。束搜索（beamsearch）對(duì)邊界的大小進(jìn)行了限制。最簡(jiǎn)單的方法是只保留具有最優(yōu)f值的k個(gè)節(jié)點(diǎn)，放棄其他已擴(kuò)展節(jié)點(diǎn)。這當(dāng)然會(huì)導(dǎo)致搜索變成不完備的和次優(yōu)的算法，但我們可以選取合適的k以充分利用可用內(nèi)存，算法執(zhí)行速度也會(huì)更快，因?yàn)樗粩U(kuò)展了較少的節(jié)點(diǎn)。對(duì)于許多問(wèn)題，它可以找到很好的近似最優(yōu)解。你可以將一致代價(jià)搜索或A*搜索看作在同心等值線的各個(gè)方向擴(kuò)展，而將束搜索看作只探索這些等值線的主要部分，即包含k個(gè)最佳候選的部分。另一種形式的束搜索并不嚴(yán)格限制邊界的大小，而是保留f值在最優(yōu)f值的范圍內(nèi)的所有節(jié)點(diǎn)。這樣的話，當(dāng)存在幾個(gè)強(qiáng)得分節(jié)點(diǎn)時(shí)，只會(huì)保留幾個(gè)節(jié)點(diǎn)，但如果不存在強(qiáng)節(jié)點(diǎn)，則會(huì)保留更多節(jié)點(diǎn)，直到出現(xiàn)一個(gè)強(qiáng)節(jié)點(diǎn)。迭代加深A(yù)*搜索（iterative-deepeningA*search，IDA*）之于A*搜索，就像迭代加深搜索之于深度優(yōu)先搜索一樣：IDA*既擁有A*的優(yōu)問(wèn)某些狀態(tài)。它是一種非常重要且常用的用于解決內(nèi)存不足問(wèn)題的算法。在標(biāo)準(zhǔn)的迭代加深搜索中，截?cái)嘀禐樯疃?，每次迭代深度增?。而在IDA*中，截?cái)嘀凳莊代價(jià)（g+h）；在每次迭代中，新的截?cái)嘀禐槌^(guò)上一次迭代截?cái)嘀档墓?jié)點(diǎn)中最小的f代價(jià)。換句話說(shuō)，每次迭代都會(huì)徹底地搜索一個(gè)f等值線，找到一個(gè)剛好超出該等值線的節(jié)點(diǎn)，并使用該節(jié)點(diǎn)的f代價(jià)作為下一個(gè)等值線。像8數(shù)碼這樣的問(wèn)題，每條路徑的f代價(jià)都是整數(shù)，這非常有效地使得每次迭代都朝著目標(biāo)穩(wěn)步前進(jìn)。如果最優(yōu)解的代價(jià)是C*，那么迭代的次數(shù)不可能超過(guò)C*（例如，最難的8數(shù)碼問(wèn)題的迭代次數(shù)不超過(guò)31）。但對(duì)于每個(gè)節(jié)點(diǎn)的f代價(jià)都不相同的問(wèn)題，每一個(gè)新的等值線可能只包含一個(gè)新節(jié)點(diǎn)，并且迭代次數(shù)可能等于狀態(tài)數(shù)。遞歸最佳優(yōu)先搜索（recursive best-first 見圖3-22）試圖模擬標(biāo)準(zhǔn)的最佳優(yōu)先搜索的操作，但僅僅使用線性空間。RBFS類似于遞歸深度優(yōu)先搜索，但它不是沿著當(dāng)前路徑無(wú)限地向下搜索，而是使用f_limit變量跟蹤從當(dāng)前節(jié)點(diǎn)的任意祖先節(jié)點(diǎn)可得到的最優(yōu)備選路徑的f值。如果當(dāng)前節(jié)點(diǎn)超過(guò)了這個(gè)限制，那么遞歸將回到備選路徑上。隨著遞歸的展開，RBFS將路徑上每個(gè)節(jié)點(diǎn)的f值替換為一個(gè)倒推值（backed-up value）——其子節(jié)點(diǎn)的最優(yōu)f值。通過(guò)這種方式RBFS可以記住被它遺忘的子樹中最優(yōu)葉節(jié)點(diǎn)的f值，因此，在之后的某個(gè)時(shí)刻，RBFS可以決定是否要重新擴(kuò)展該子樹。圖3-23展示了RBFS是如何到達(dá)Bucharest的。圖3-22 遞歸最佳優(yōu)先搜索算法在一定程度上，RBFS比IDA*更高效，但仍然存在重復(fù)生成大量節(jié)點(diǎn)的問(wèn)題。在圖3-23的示例中，RBFS沿著經(jīng)過(guò)Rimnicu Vilcea的路徑然后“改變主意”去嘗試經(jīng)過(guò)Fagaras，然后又“回心轉(zhuǎn)意”。之所以會(huì)發(fā)生這些改變，是因?yàn)槊看螖U(kuò)展當(dāng)前的最優(yōu)路徑時(shí)，它的f值很可能增加——對(duì)于靠近目標(biāo)的節(jié)點(diǎn)，h值通常不那么樂(lè)觀。當(dāng)這種情況發(fā)生時(shí)，次優(yōu)路徑可能會(huì)成為最優(yōu)路徑，因此搜索必須回溯。每一次改變對(duì)應(yīng)于IDA*的一次迭代，并且可能需要多次重新擴(kuò)展已經(jīng)遺忘的節(jié)點(diǎn)，以重建最優(yōu)路徑，并對(duì)該路徑再擴(kuò)展一個(gè)節(jié)點(diǎn)。圖3-23使用RBFS搜索到Bucharest的最短路線的各個(gè)階段。每次遞歸調(diào)用的f_limit值標(biāo)注在每個(gè)當(dāng)前節(jié)點(diǎn)的上方，每個(gè)節(jié)點(diǎn)上都標(biāo)有它的f代價(jià)。（a）沿著經(jīng)過(guò)RimnicuVilcea的路徑前進(jìn)，直到當(dāng)前最優(yōu)葉節(jié)點(diǎn)（Pitesti）的值比最優(yōu)備選路徑（Fagaras）差。（b）遞歸回溯，被遺忘子樹的最優(yōu)葉節(jié)點(diǎn)值（417）被備份到RimnicuVilcea；接著擴(kuò)展Fagaras，得到最優(yōu)葉節(jié)點(diǎn)值450。（450）被備份到Fagaras；然后擴(kuò)展RimnicuVilcea。這一次，因?yàn)樽顑?yōu)備選路徑（經(jīng)由Timisoara）的代價(jià)至少為447，所以繼續(xù)擴(kuò)展Bucharest如果啟發(fā)式函數(shù)h(n)是可容許的，那么RBFS是最優(yōu)的。它的空間復(fù)雜性在最深的最優(yōu)解的深度上是線性的，但時(shí)間復(fù)雜性很難刻畫：既取決于啟發(fā)式函數(shù)的準(zhǔn)確性，也取決于最優(yōu)路徑隨節(jié)點(diǎn)擴(kuò)展變化的頻率。它按照f(shuō)得分遞增的順序來(lái)擴(kuò)展節(jié)點(diǎn)，即使f是非單調(diào)的。IDA*和RBFS使用內(nèi)存太少，它們的時(shí)間復(fù)雜性會(huì)受到影響。在兩次迭代之間，IDA*只保留一個(gè)數(shù)值：當(dāng)前的f代價(jià)限制。RBFS在內(nèi)存中保留了更多的信息，但它只使用線性空間：即使有更多的內(nèi)存可用，RBFS也無(wú)法利用。因?yàn)樗鼈儠?huì)遺忘它們所做的大部分事情，這兩種算法都可能會(huì)多次重復(fù)探索相同狀態(tài)。因此，確定我們有多少可用內(nèi)存并允許算法使用所有內(nèi)存似乎是明智的。執(zhí)行這樣操作的兩種算法是MA*（memory-bounded 限的A*）和SMA*（simplified 到內(nèi)存被填滿。此時(shí)，它不能再為搜索樹添加新節(jié)點(diǎn)，除非刪除舊節(jié)點(diǎn)。SMA*總是丟棄最差的葉節(jié)點(diǎn)，即f值最大的葉節(jié)點(diǎn)。和RBFS一樣，SMA*將被遺忘節(jié)點(diǎn)的值備份到其父節(jié)點(diǎn)。這樣，被遺忘子樹的祖先知道該子樹中最優(yōu)路徑的質(zhì)量。有了這一信息，只有在所有其他路徑看起來(lái)都比它已經(jīng)遺忘的路徑更差時(shí)，SMA*才會(huì)重新生成該子樹。這意味著如果節(jié)點(diǎn)n的所有后代都被遺忘了，那么盡管我們不知道從n開始應(yīng)該走哪條路徑，但我們?nèi)灾朗欠駪?yīng)該從n開始走。本書附帶的在線代碼庫(kù)中描述了完整的SMA*算法。有一點(diǎn)值得注意，我們之前提到SMA*將擴(kuò)展最優(yōu)葉節(jié)點(diǎn)，刪除最差葉節(jié)點(diǎn)。如果所有葉節(jié)點(diǎn)的f值都相同呢？為了避免算法選擇同一個(gè)節(jié)點(diǎn)進(jìn)行刪除和擴(kuò)展操作，SMA*擴(kuò)展最新的最優(yōu)葉節(jié)點(diǎn)并刪除最老的最差葉節(jié)點(diǎn)。當(dāng)只有一個(gè)葉節(jié)點(diǎn)時(shí)，這兩者是同一個(gè)節(jié)點(diǎn)，但在這種情況下，當(dāng)前的搜索樹一定是一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的占滿所有內(nèi)存的單一路徑。如果葉節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，那么即使它在最優(yōu)解路徑上，也無(wú)法在可用內(nèi)存范圍內(nèi)得到這個(gè)解。因此，完全可以丟棄該節(jié)點(diǎn)，就好像它沒(méi)有后繼節(jié)點(diǎn)一樣。如果存在任意可達(dá)解，也就是說(shuō)，如果最淺的目標(biāo)節(jié)點(diǎn)的深度d小于內(nèi)存大?。ㄓ霉?jié)點(diǎn)數(shù)表示），那么SMA*就是完備的。如果存在可達(dá)的最優(yōu)解，那么SMA*就是最優(yōu)的；否則，就返回當(dāng)前最優(yōu)的可達(dá)解。在實(shí)踐中，SMA*是尋找最優(yōu)解的一個(gè)相當(dāng)穩(wěn)健的選擇，特別是當(dāng)狀態(tài)空間是一個(gè)圖、行動(dòng)代價(jià)不一致，并且生成節(jié)點(diǎn)的總開銷相比維護(hù)邊界集和已達(dá)集的總開銷更大時(shí)。然而，在非常困難的問(wèn)題上，常常會(huì)出現(xiàn)SMA*被迫在許多候選解路徑之間來(lái)回不斷切換的情況，只有一小部分路徑可以存入內(nèi)存。［這類似于磁盤分頁(yè)系統(tǒng)中的抖動(dòng)（thrashing）問(wèn)題。］那么，重復(fù)生成相同節(jié)點(diǎn)就需要額外的時(shí)間，這意味著，在給定無(wú)限內(nèi)存的情況下可以用A*實(shí)際求解的問(wèn)題，對(duì)于SMA*將變得難以處理。也就是說(shuō)，從計(jì)算時(shí)間的角度，內(nèi)存限制會(huì)使問(wèn)題變得難以處理。雖然還沒(méi)有現(xiàn)有理論解釋如何在時(shí)間和內(nèi)存之間權(quán)衡，但這似乎是