《人工智能》全套PPT第3章 智能搜索

1、第三章智能搜索3.1搜索概論3.2盲目搜索3.3啟發(fā)式搜索3.4博弈樹搜索of311習(xí)題3.1 搜索概論第三章 智能搜索of312 科學(xué)發(fā)展觀要求建立人與自然和諧的社會(huì)，經(jīng)濟(jì)全球化、信息網(wǎng)絡(luò)化、智能社會(huì)化成為當(dāng)前發(fā)展的特征。探索人類智慧的道路，從思維科學(xué)走向社會(huì)智能科學(xué)，是時(shí)代的要求，體現(xiàn)了人文與科技的交融。在人工智能領(lǐng)域，所需求解的問(wèn)題大多都具備結(jié)構(gòu)不良或非結(jié)構(gòu)化性質(zhì)。這類問(wèn)題通常并不存在“一馬平川”式的求解方案。人們發(fā)現(xiàn)，很多問(wèn)題的求解，其實(shí)可以通過(guò)試探性的搜索來(lái)獲得。1搜索的定義3.1 搜索概論第三章 智能搜索of313 求解問(wèn)題的第一步，就是把問(wèn)題描述清楚，也就是目標(biāo)的表示，它涉及到一

2、種知識(shí)表示策略狀態(tài)空間表示法。第二步就是搜索策略。這里的“搜索”是指，智能系統(tǒng)嘗試性地找到目標(biāo)解的動(dòng)作序列。 搜索問(wèn)題可分解為兩個(gè)關(guān)鍵的子問(wèn)題：（1）搜索什么；（2）在哪里搜索。前者是指搜索的解，即目標(biāo)為何。后者是指搜索空間。搜索空間就是由一系列狀態(tài)構(gòu)成。那什么是狀態(tài)呢？下面我們來(lái)討論這個(gè)基礎(chǔ)問(wèn)題。1搜索的定義3.1 搜索概論第三章 智能搜索of3142狀態(tài)空間表示3.1 搜索概論第三章 智能搜索of315 定義2：狀態(tài)空間（State Space）：某個(gè)問(wèn)題的全部可能狀態(tài)或關(guān)系集合。2狀態(tài)空間表示 還是拿下棋來(lái)舉例，它的狀態(tài)空間，就是指它的每一個(gè)合法棋局的全體集合。很顯然，由于狀態(tài)空間可能非

3、常巨大，所以在搜索之前，通常并不會(huì)一次性地把所有狀態(tài)都生成出來(lái)，而是漸進(jìn)式地?cái)U(kuò)展，“目標(biāo)”狀態(tài)就是在每次新展開的狀態(tài)中搜索。 3.1 搜索概論第三章 智能搜索of316 定義2：狀態(tài)空間（State Space）：某個(gè)問(wèn)題的全部可能狀態(tài)或關(guān)系集合。2狀態(tài)空間表示 和普通搜索算法不同的是，對(duì)于人工智能系統(tǒng)而言，在問(wèn)題求解之前，搜索空間是未知的。通常是“走一步、看一步”，“摸著石頭過(guò)河”。因此，搜索通常分為兩個(gè)階段：1）狀態(tài)空間的生成階段。2）對(duì)該狀態(tài)空間中尋找目標(biāo)解的階段。對(duì)于博弈類游戲，上述特征尤其明顯。我們通常無(wú)需把每一個(gè)棋局都考慮一邊，而是在對(duì)方落子后，方才考慮我方可能走的每一步有利的棋局

4、。3.1 搜索概論第三章 智能搜索of317 定義3：操作算子（Operator）：使問(wèn)題從一種狀態(tài)變遷到另外一種狀態(tài)的操作規(guī)則或函數(shù)。2狀態(tài)空間表示 操作算子可以是某個(gè)動(dòng)作（如下棋的走步），也可以數(shù)學(xué)運(yùn)算符、邏輯運(yùn)算符等。3.1 搜索概論第三章 智能搜索of3181定義狀態(tài)空間。根據(jù)問(wèn)題的特性，給出相應(yīng)的狀態(tài)空間，包括初始狀態(tài)、目標(biāo)狀態(tài)和狀態(tài)的一般表示形式。2確定操作算子集合：能夠作用于一個(gè)狀態(tài)后，遷移到另外一個(gè)狀態(tài)。3確定一組搜索策略，使得能夠從初始狀態(tài)出發(fā)，沿著某條路徑出發(fā)，達(dá)到目標(biāo)路徑。 有了上面概念上的鋪墊，下面我們可以給出基于狀態(tài)空間法的搜索算法基本流程：2狀態(tài)空間表示3.1 搜索

5、概論第三章 智能搜索of319 這樣一來(lái)，問(wèn)題求解的求解過(guò)程可歸納為：應(yīng)用合法的規(guī)則和控制策略，取遍歷或搜索狀態(tài)空間，直至找到從初始狀態(tài)到目標(biāo)狀態(tài)的某個(gè)路徑。在這個(gè)過(guò)程中，要涉及兩類函數(shù)： （1）目標(biāo)檢測(cè)函數(shù)：用來(lái)確定某個(gè)狀態(tài)是不是目標(biāo)狀態(tài)。 （2）路徑代價(jià)函數(shù)：對(duì)每條路徑賦予一定的權(quán)重，看走那條路最劃算（代價(jià)最?。?。2狀態(tài)空間表示3.1 搜索概論第三章 智能搜索of3110下面我們列舉一個(gè)案例來(lái)說(shuō)明知識(shí)的狀態(tài)空間表示法。【例3.1】八數(shù)碼問(wèn)題的狀態(tài)空間表示法。 在一個(gè)九宮格里面放入8個(gè)數(shù)字，數(shù)字只能上下左右移動(dòng)，并且只能移動(dòng)到空白處。通過(guò)若干此移動(dòng)后，能把圖3-1中左圖數(shù)字移動(dòng)成右圖數(shù)字。2

6、狀態(tài)空間表示八數(shù)碼游戲初始與結(jié)果3.1 搜索概論第三章 智能搜索of3111 我們將九宮格中的格子從左到右，從上至下依次編號(hào)成1至9個(gè)格子，如圖3-2所示。2狀態(tài)空間表示八數(shù)碼游戲格子編號(hào)3.1 搜索概論第三章 智能搜索of3112 則我們的狀態(tài)空間中的初始狀態(tài)為：Q1=1,2,3,X,6,4,8,7,5。其中X 代表該位置的數(shù)字為空?，F(xiàn)在如圖3所示，有以下幾種操作算子：2狀態(tài)空間表示f1=數(shù)字8移動(dòng)到X位上。產(chǎn)生對(duì)應(yīng)的狀態(tài)為：Q2=1,2,3,X,6,4,8,7,5。f2=數(shù)字7移動(dòng)到X位上。產(chǎn)生對(duì)應(yīng)的狀態(tài)為：Q3=1,2,3,8,6,4,7,X,5。f3=數(shù)字1移動(dòng)到X位上。產(chǎn)生對(duì)應(yīng)的狀態(tài)

7、為：Q4=X,2,3,8,6,4,1,7,5。f4=數(shù)字6移動(dòng)到X位上。產(chǎn)生對(duì)應(yīng)的狀態(tài)為：Q5=1,2,3,8,X,4,6,7,5。f5=數(shù)字5移動(dòng)到X位上。產(chǎn)生對(duì)應(yīng)的狀態(tài)為：Q6=1,2,3,8,6,4,5,7,X。f6=數(shù)字6移動(dòng)到X位上。產(chǎn)生對(duì)應(yīng)的狀態(tài)為：Q7=1,2,3,8,X,4,6,7,5。3.1 搜索概論第三章 智能搜索of3113則操作算子的集合F=f1，f2，f3，f4,，f5，f6，目標(biāo)狀態(tài)Q7=1,2,3,8,X,4,6,7,5。2狀態(tài)空間表示狀態(tài)空間表示法示例八：數(shù)碼游戲第三章智能搜索3.1搜索概論3.2盲目搜索3.3啟發(fā)式搜索3.4博弈樹搜索of3114習(xí)題3.2 盲

8、目搜索第三章 智能搜索of3115 盲目搜索（Blind Search）又叫非啟發(fā)式搜索（Uninformed Search），它只會(huì)按預(yù)定的搜索策略進(jìn)行搜索，而不會(huì)考慮問(wèn)題本身的特性而做變通，它唯一能區(qū)分的就是，下一個(gè)狀態(tài)是目標(biāo)狀態(tài)（即問(wèn)題的解）還是非目標(biāo)狀態(tài)。 因此，盲目搜索一般只適用于求解比較簡(jiǎn)單的問(wèn)題。我們將學(xué)習(xí)的寬度優(yōu)先搜索和深度優(yōu)先搜索，屬于盲目搜索方法。3.2 盲目搜索第三章 智能搜索of31161寬度優(yōu)先搜索 寬度優(yōu)先搜索（Breadth First Search，BFS）又稱廣度優(yōu)先搜索，是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最

9、短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。 寬度優(yōu)先搜索屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說(shuō)，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。3.2 盲目搜索第三章 智能搜索of31171寬度優(yōu)先搜索寬度優(yōu)先搜索示例圖13.2 盲目搜索第三章 智能搜索of31181寬度優(yōu)先搜索3.2 盲目搜索第三章 智能搜索of31191寬度優(yōu)先搜索3.2 盲目搜索第三章 智能搜索of31201寬度優(yōu)先搜索圖3-5 寬度優(yōu)先搜索示例圖23.2 盲目搜索第三章 智能搜索of31212深度優(yōu)先搜索 深度優(yōu)先搜索（Depth Firs

10、t Search，DFS）屬于圖算法的一種。其過(guò)程簡(jiǎn)要來(lái)說(shuō)是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次。3.2 盲目搜索第三章 智能搜索of31222深度優(yōu)先搜索 深度優(yōu)先搜索所使用的策略就如其名字一樣，只要可能，就在圖中盡量的深入。深度優(yōu)先搜素總是對(duì)最近才發(fā)現(xiàn)的結(jié)點(diǎn)V 的出發(fā)邊進(jìn)行探索，直到該結(jié)點(diǎn)的所有出發(fā)邊都被發(fā)現(xiàn)為止。一旦結(jié)點(diǎn)V 的所有出發(fā)邊都被發(fā)現(xiàn)，搜索則回溯到V 的前驅(qū)結(jié)點(diǎn)（V 是經(jīng)過(guò)該點(diǎn)才被發(fā)現(xiàn)的），來(lái)探索該前驅(qū)結(jié)點(diǎn)的出發(fā)邊。 該過(guò)程一直持續(xù)到從源結(jié)點(diǎn)可以到達(dá)的所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。如果還存在尚未發(fā)現(xiàn)的結(jié)點(diǎn)，則深度優(yōu)先搜索將從這些未被發(fā)現(xiàn)的結(jié)點(diǎn)中任選一個(gè)作

11、為新的源節(jié)點(diǎn)，并重復(fù)同樣的搜索過(guò)程。3.2 盲目搜索第三章 智能搜索of31232深度優(yōu)先搜索深度優(yōu)先遍歷圖的基本思路是，從圖中某頂點(diǎn)V 出發(fā)： （1）訪問(wèn)頂點(diǎn)V 。 （2）依次從V 的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和 v 有路徑相通的頂點(diǎn)都被訪問(wèn)。 （3）若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則從一個(gè)未被訪問(wèn)的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問(wèn)過(guò)為止。3.2 盲目搜索第三章 智能搜索of31242深度優(yōu)先搜索 下面采用一個(gè)示例圖來(lái)說(shuō)明這個(gè)過(guò)程。如圖3-6所示，示例圖是一個(gè)無(wú)向圖，如果我們從A 點(diǎn)發(fā)起深度優(yōu)先搜索（以下的訪問(wèn)次序并不是唯一的，第二個(gè)點(diǎn)既可以是B

12、 也可以是C ，D ），則我們可能得到如下的一個(gè)訪問(wèn)過(guò)程：AB E（沒(méi)有路了！回溯到 A ) C F H G D（沒(méi)有路，最終回溯到A ，A 也沒(méi)有未訪問(wèn)的相鄰節(jié)點(diǎn)，本次搜索結(jié)束）。深度優(yōu)先搜索示例圖第三章智能搜索3.1搜索概論3.2盲目搜索3.3啟發(fā)式搜索3.4博弈樹搜索of3125習(xí)題3.3 啟發(fā)式搜索第三章 智能搜索of31261啟發(fā)式搜索策略 啟發(fā)式搜索(Heuristically Search)又稱為有信息搜索(Informed Search)，它是利用問(wèn)題擁有的啟發(fā)信息來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍、降低問(wèn)題復(fù)雜度的目的，這種利用啟發(fā)信息的搜索過(guò)程稱為啟發(fā)式搜索。3.3 啟發(fā)式搜索第

13、三章 智能搜索of31271啟發(fā)式搜索策略 啟發(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)謂的搜索路徑，提高了效率。 如果能夠利用搜索過(guò)程所得到的問(wèn)題自身的一些特征信息來(lái)指導(dǎo)搜索過(guò)程，則可以縮小搜索范圍，提高搜索效率。像這樣利用問(wèn)題自身特征信息來(lái)引導(dǎo)搜索過(guò)程的方法成為啟發(fā)式方法。 啟發(fā)式策略可以通過(guò)指導(dǎo)搜索向最有希望的方向前進(jìn)，降低了復(fù)雜性。通過(guò)刪除某些狀態(tài)及其延伸，啟發(fā)式算法可以消除組合爆炸，并得到令人能接受的解(通常并不一定是最優(yōu)解)。3.3 啟發(fā)式搜索第三章 智能搜索of31281啟發(fā)式搜索策略 然而，啟發(fā)式策

14、略是極易出錯(cuò)的。在解決問(wèn)題的過(guò)程中啟發(fā)僅僅是下一步將要采取措施的一個(gè)猜想，常常根據(jù)經(jīng)驗(yàn)和直覺(jué)來(lái)判斷。由于啟發(fā)式搜索只有有限的信息(比如當(dāng)前狀態(tài)的描述)，要想預(yù)測(cè)進(jìn)一步搜索過(guò)程中狀態(tài)空間的具體行為則很難。一個(gè)啟發(fā)式搜索可能得到一個(gè)次優(yōu)解，也可能一無(wú)所獲。這是啟發(fā)式搜索固有的局限性。這種局限性不可能由所謂更好的啟發(fā)式策略或更有效的搜索算法來(lái)消除。 一般說(shuō)來(lái)，啟發(fā)信息越強(qiáng)，擴(kuò)展的無(wú)用節(jié)點(diǎn)就越少。引入強(qiáng)的啟發(fā)信息，有可能大大降低搜索工作量，但不能保證找到最小耗散值的解路徑(最佳路徑)。因此，在實(shí)際應(yīng)用中，最好能引入降低搜索工作量的啟發(fā)信息而不犧牲找到最佳路徑的保證。3.3 啟發(fā)式搜索第三章 智能搜索o

15、f31291啟發(fā)式搜索策略以下為一個(gè)啟發(fā)式搜索的八數(shù)碼游戲例子： 如圖3-7所示，在一個(gè)九宮格里面放入8個(gè)數(shù)字，數(shù)字只能上下左右移動(dòng)，并且只能移動(dòng)到空白處。通過(guò)若干次這樣的移動(dòng)后，把左圖數(shù)字位置移動(dòng)成右圖數(shù)字位置。八數(shù)碼游戲初始與結(jié)果3.3 啟發(fā)式搜索第三章 智能搜索of31301啟發(fā)式搜索策略 解決此問(wèn)題的啟發(fā)策略：每次移動(dòng)的時(shí)候，正確位置數(shù)碼的個(gè)數(shù)要大于交換前正確位置數(shù)碼個(gè)數(shù)。正確位置數(shù)碼的個(gè)數(shù)是指每個(gè)數(shù)碼的位置與最終格局的對(duì)比，如果位置相同，則說(shuō)明此數(shù)碼在正確位置。圖3-8中紅色字體標(biāo)識(shí)的數(shù)碼為正確位置數(shù)碼，由此我們可以發(fā)現(xiàn)下圖中左邊初始圖案正確位置的數(shù)碼個(gè)數(shù)為4個(gè)。八數(shù)碼游戲?qū)ふ艺_位

16、置數(shù)碼個(gè)數(shù)3.3 啟發(fā)式搜索第三章 智能搜索of31311啟發(fā)式搜索策略 由下圖3-9所示可得，正確位置數(shù)碼個(gè)數(shù)大于等于4的只有左下方的格局，那么下一步選擇的就是左下方的格局。八數(shù)碼游戲3.3 啟發(fā)式搜索第三章 智能搜索of31321啟發(fā)式搜索策略再次調(diào)用次算法如下圖3-10所示：這樣一步一步地進(jìn)行，最終即可得到最終格局。八數(shù)碼游戲3.3 啟發(fā)式搜索第三章 智能搜索of31332有序搜索 有序搜索（Ordered Search）又稱之為最佳優(yōu)先搜索（Best First Search），是一種啟發(fā)式搜索算法，我們也可以將它看作廣度優(yōu)先搜索算法的一種改進(jìn)；最佳優(yōu)先搜索算法在廣度優(yōu)先搜索的基礎(chǔ)上，

17、用啟發(fā)估價(jià)函數(shù)對(duì)將要被遍歷到的點(diǎn)進(jìn)行估價(jià)，然后選擇代價(jià)小的進(jìn)行遍歷，直到找到目標(biāo)節(jié)點(diǎn)或者遍歷完所有的點(diǎn)，算法結(jié)束。3.3 啟發(fā)式搜索第三章 智能搜索of31342有序搜索 要實(shí)現(xiàn)最佳優(yōu)先搜索我們必須使用一個(gè)優(yōu)先隊(duì)列（Priority Queue）來(lái)實(shí)現(xiàn)，通常采用一個(gè)open 優(yōu)先隊(duì)列和一個(gè)closed 集open 優(yōu)先隊(duì)列用來(lái)儲(chǔ)存還沒(méi)有遍歷將要遍歷的節(jié)點(diǎn)，而closed 集用來(lái)儲(chǔ)存已經(jīng)被遍歷過(guò)的節(jié)點(diǎn)。我們用下面圖3-11作為一個(gè)示例圖來(lái)描述最佳優(yōu)先搜索過(guò)程。最佳優(yōu)先搜索示例圖3.3 啟發(fā)式搜索第三章 智能搜索of31352有序搜索最佳優(yōu)先搜索的過(guò)程如圖3-12所示，可以被描述為：搜索出的路徑為

18、：A-H-G-D-E，整條路徑的代價(jià)和為16。最佳優(yōu)先搜索示例圖詳細(xì)過(guò)程3.3 啟發(fā)式搜索第三章 智能搜索of31362有序搜索 （1）將根節(jié)點(diǎn)放入優(yōu)先隊(duì)列 open 中。 （2）從優(yōu)先隊(duì)列中取出優(yōu)先級(jí)最高的節(jié)點(diǎn)X 。 （3）根據(jù)節(jié)點(diǎn)X 生成子節(jié)點(diǎn)Y ： X 的子節(jié)點(diǎn)Y 不在 open 隊(duì)列或者 closed 中，由估價(jià)函數(shù)計(jì)算出估價(jià)值，放入open 隊(duì)列中。 X 的子節(jié)點(diǎn)Y 在open 隊(duì)列中，且估價(jià)值優(yōu)于open 隊(duì)列中的子節(jié)點(diǎn)Y ，將 open 隊(duì)列中的子節(jié)點(diǎn)Y 的估價(jià)值替換成新的估價(jià)值并按優(yōu)先值排序。 X 的子節(jié)點(diǎn)Y 在closed 集中，且估價(jià)值優(yōu)于closed 集中的子節(jié)點(diǎn)Y ，將

19、 closed 集中的子節(jié)點(diǎn)Y 移除，并將子節(jié)點(diǎn)Y 加入open 優(yōu)先隊(duì)列。 （4）將節(jié)點(diǎn)X 放入closed 集中。 （5）重復(fù)過(guò)程2,3,4直到目標(biāo)節(jié)點(diǎn)找到，或者open 為空，程序結(jié)束。3.3 啟發(fā)式搜索第三章 智能搜索of31373通用圖搜索算法 在圖算法中經(jīng)常要執(zhí)行遍歷每個(gè)頂點(diǎn)和每條邊的操作，即圖搜索。許多圖算法都以圖搜索為基礎(chǔ)，如2-著色問(wèn)題、連通性計(jì)算基于深度優(yōu)先搜尋（DFS），而無(wú)權(quán)最短路徑則基于廣度優(yōu)先搜索（BFS）。 基于搜索的算法還包括計(jì)算最小生成樹的Prim算法以及計(jì)算最短路徑的Dijkstra算法。其中我們?cè)谇懊嬲鹿?jié)已經(jīng)介紹過(guò)廣度優(yōu)先搜索以及深度優(yōu)先搜索，本小節(jié)著重介

20、紹Prim算法和Dijkstra算法。3.3 啟發(fā)式搜索第三章 智能搜索of31383通用圖搜索算法 普里姆（Prim）算法，圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹，即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖中的所有頂點(diǎn)（Vertex），且使得樹中所有的邊的權(quán)值之和亦為最小值。 Prim算法基于貪心算法設(shè)計(jì)，該算法從一個(gè)頂點(diǎn)出發(fā)，選擇這個(gè)頂點(diǎn)發(fā)出的邊中權(quán)重最小的一條加入最小生成樹中，隨后從當(dāng)前的樹中的所有頂點(diǎn)發(fā)出的邊中選出權(quán)重最小的一條加入樹中，以此類推，直到所有頂點(diǎn)都在樹中，算法結(jié)束。算法可以按如下具體描述：3.3 啟發(fā)式搜索第三章 智能搜索of31393通用圖搜索算法

21、3.3 啟發(fā)式搜索第三章 智能搜索of31403通用圖搜索算法 下面舉一個(gè)例子來(lái)說(shuō)明，圖3-13是一個(gè)無(wú)向圖，假設(shè)我們從頂點(diǎn)a 出發(fā)使用Prim算法計(jì)算最小生成樹，其算法運(yùn)行過(guò)程如下。Prim算法示例圖3.3 啟發(fā)式搜索第三章 智能搜索of31413通用圖搜索算法 從頂點(diǎn)a發(fā)出的邊有，和，其中權(quán)重最小的邊為，于是我們將邊加入到最小生成樹中，此時(shí)最小生成樹包括圖3-14中的陰影邊和灰色頂點(diǎn)。Prim算法示例圖3.3 啟發(fā)式搜索第三章 智能搜索of31423通用圖搜索算法 接下來(lái)我們繼續(xù)從當(dāng)前最小生成樹中的頂點(diǎn)發(fā)出的所有邊中尋找權(quán)重最小的一條，即邊，中的邊，于是我們將邊加入到樹中，如下圖3-15所

22、示。 Prim算法示例圖3.3 啟發(fā)式搜索第三章 智能搜索of31433通用圖搜索算法 繼續(xù)上述步驟，從頂點(diǎn)a、f、d 發(fā)出的邊中選出權(quán)重最小的一條，即邊，并將它加入到樹中，如下圖3-16所示。Prim算法示例圖3.3 啟發(fā)式搜索第三章 智能搜索of31443通用圖搜索算法重復(fù)上述步驟，最后得到圖的最小生成樹如下圖3-17所示。Prim算法示例圖3.3 啟發(fā)式搜索第三章 智能搜索of31453通用圖搜索算法 迪杰斯特拉（Dijkstra）算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問(wèn)題。迪杰斯特拉

23、算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。 Dijkstra算法采用的是一種貪心的策略，聲明一個(gè)數(shù)組Dis來(lái)保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合T 。初始時(shí)，原點(diǎn)s 的路徑權(quán)重被賦為0(Dis s =0)。若對(duì)于頂點(diǎn)s 存在能直接到達(dá)的邊(s , m)，則把Dis m 設(shè)置為w (s , m)，同時(shí)把所有其他（s 不能直接到達(dá)的）頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大。初始時(shí)，集合T 只有頂點(diǎn)s 。3.3 啟發(fā)式搜索第三章 智能搜索of31463通用圖搜索算法 從Dis 數(shù)組選擇最小值，則該值就是源點(diǎn)s 到該值對(duì)應(yīng)的頂點(diǎn)的最短路徑，并且把該點(diǎn)加入到T 中，

24、完成一個(gè)頂點(diǎn)。 然后，我們需要看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過(guò)該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長(zhǎng)度是否比源點(diǎn)直接到達(dá)短，如果是，那么就替換這些頂點(diǎn)在Dis 中的值。 之后，從Dis 中找出最小值，重復(fù)上述動(dòng)作，直到T 中包含了圖的所有頂點(diǎn)。3.3 啟發(fā)式搜索第三章 智能搜索of31473通用圖搜索算法Dijkstra算法示例圖3.3 啟發(fā)式搜索第三章 智能搜索of31483通用圖搜索算法首先第一步，先聲明一個(gè)Dis 數(shù)組，該數(shù)組初始化的值為如圖3-19所示：Dijkstra算法示例圖Dis 數(shù)組3.3 啟發(fā)式搜索第三章 智能搜索of31493通用圖搜索算法Dijkstra算法示例圖Dis

25、 數(shù)組3.3 啟發(fā)式搜索第三章 智能搜索of31503通用圖搜索算法Dijkstra算法示例圖Dis 數(shù)組3.3 啟發(fā)式搜索第三章 智能搜索of31513通用圖搜索算法Dijkstra算法示例圖Dis 數(shù)組3.3 啟發(fā)式搜索第三章 智能搜索of31523通用圖搜索算法Dijkstra算法示例圖Dis 數(shù)組3.3 啟發(fā)式搜索第三章 智能搜索of31533通用圖搜索算法Dijkstra算法示例圖結(jié)果起點(diǎn)終點(diǎn)最短路徑長(zhǎng)度無(wú)105030603.3 啟發(fā)式搜索第三章 智能搜索of31544A* 算法3.3 啟發(fā)式搜索第三章 智能搜索of31554A* 算法3.3 啟發(fā)式搜索第三章 智能搜索of31564

26、A* 算法 如下就A*算法與深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法進(jìn)行比較： 深度優(yōu)先搜索會(huì)朝一個(gè)方向進(jìn)發(fā)，直到遇到邊界或者障礙物，才回溯。一般在實(shí)現(xiàn)的時(shí)候，我們采用遞歸的方式來(lái)進(jìn)行，也可以采用模擬壓棧的方式來(lái)實(shí)現(xiàn)。3.3 啟發(fā)式搜索第三章 智能搜索of31574A* 算法 如圖3-24，S 代表起點(diǎn)，E 代表終點(diǎn)。我們?nèi)绻凑沼?、下、左、上這樣的擴(kuò)展順序的話，算法就會(huì)一直往右擴(kuò)張，直到走到地圖的右邊界，發(fā)現(xiàn)沒(méi)找到目標(biāo)點(diǎn)，然后再回溯。深度優(yōu)先搜索方式3.3 啟發(fā)式搜索第三章 智能搜索of31584A* 算法 這個(gè)算法的好處就是實(shí)現(xiàn)簡(jiǎn)單，不過(guò)也存在兩個(gè)明顯的問(wèn)題：1、路徑可能不是最優(yōu)解；2、尋路時(shí)間

27、比較長(zhǎng)。 圖3-25展示了廣度優(yōu)先算法的方式，廣度優(yōu)先搜索像是地震波，從起點(diǎn)向外輻射，直到找到目標(biāo)點(diǎn)。我們?cè)趯?shí)現(xiàn)的時(shí)候，一般采用隊(duì)列來(lái)實(shí)現(xiàn)。廣度優(yōu)先搜索方式3.3 啟發(fā)式搜索第三章 智能搜索of31594A* 算法 廣度優(yōu)先算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，同時(shí)保證算法能夠找到一條最優(yōu)的路徑。但是也存在不足之處就是算法消耗的時(shí)間比較大，遍歷的點(diǎn)會(huì)很多。那么這里我們就可以思考一個(gè)問(wèn)題：為什么廣度優(yōu)先算法能找到最優(yōu)路徑，但是卻很耗時(shí)呢？ 廣度優(yōu)先搜索之所以能找到最優(yōu)的路徑，原因就是每一次擴(kuò)展的點(diǎn)，都是距離出發(fā)點(diǎn)最近、步驟最少的。如此這樣遞推，當(dāng)擴(kuò)展到目標(biāo)點(diǎn)的時(shí)候，也是距離出發(fā)點(diǎn)最近的。這樣的路徑自然形成了最短

28、的路線。 正是由于廣度優(yōu)先搜索是一層層的擴(kuò)展，讓它可以保證了算法能找到一條最優(yōu)的路線的可能性，但是卻同時(shí)也因此消耗了更多的時(shí)間和計(jì)算能力去走了絕大多的無(wú)效步驟。3.3 啟發(fā)式搜索第三章 智能搜索of31604A* 算法 從另一個(gè)角度看，廣度優(yōu)先搜索算法只關(guān)注了當(dāng)前擴(kuò)展點(diǎn)和出發(fā)點(diǎn)之間的關(guān)系，而忽略了當(dāng)前點(diǎn)和我們的目標(biāo)點(diǎn)的之間的關(guān)系，也就是一種缺乏指引搜索，較為盲目的搜索方式。情況如圖3-26所示時(shí)：存在兩種搜索方式時(shí)3.3 啟發(fā)式搜索第三章 智能搜索of31614A* 算法3.3 啟發(fā)式搜索第三章 智能搜索of31624A* 算法SM的距離+ME的距離3.3 啟發(fā)式搜索第三章 智能搜索of316

29、34A* 算法第三章智能搜索3.1搜索概論3.2盲目搜索3.3啟發(fā)式搜索3.4博弈樹搜索of3164習(xí)題3.4 博弈樹搜索第三章 智能搜索of31651博弈的定義 博弈本意是：下棋。引申義是：在一定條件下，遵守一定的規(guī)則，一個(gè)或幾個(gè)擁有絕對(duì)理性思維的人或團(tuán)隊(duì)，從各自允許選擇的行為或策略進(jìn)行選擇并加以實(shí)施，并從中各自取得相應(yīng)結(jié)果或收益的過(guò)程。有時(shí)候也用作動(dòng)詞，特指對(duì)選擇的行為或策略加以實(shí)施的過(guò)程。3.4 博弈樹搜索第三章 智能搜索of31661博弈的定義一個(gè)完整的博弈應(yīng)當(dāng)包括五個(gè)方面的內(nèi)容： 1. 博弈的參加者，即博弈過(guò)程中獨(dú)立決策、獨(dú)立承擔(dān)后果的個(gè)人和組織。 2. 博弈信息，即博弈者所掌握的對(duì)

30、選擇策略有幫助的情報(bào)資料。 3. 博弈方可選擇的全部行為或策略的集合。 4. 博弈的次序，即博弈參加者做出策略選擇的先后。 5. 博弈方的收益，即各博弈方做出決策選擇后的所得和所失。3.4 博弈樹搜索第三章 智能搜索of31671博弈的定義 博弈樹是一種與/或樹的一種，為了方便博弈樹的研究，我們使用一種簡(jiǎn)單的博弈作為研究的對(duì)象。具體的說(shuō)這樣的博弈具有如下的特點(diǎn)： （1）對(duì)壘的A，B 雙方輪流采取行動(dòng)(這就比同時(shí)采取行動(dòng)在分析上方便的許多)，博弈的結(jié)果只有三種情況：A 方勝，B 方?。籄 方敗，B 方勝；雙方戰(zhàn)成平局。 （2）在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前的格局及過(guò)去的歷史。 （3）任何一方在

31、采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對(duì)自己最為有利而對(duì)對(duì)方最為不利的對(duì)策,不存在“碰運(yùn)氣”的偶然因素。即雙方都是十分理智地決定自己的行動(dòng)。3.4 博弈樹搜索第三章 智能搜索of31681博弈的定義 在博弈過(guò)程中，任何一方都希望自己取得勝利。因此,在某一方當(dāng)前有多個(gè)行動(dòng)方案可供選擇時(shí)，他總是挑選對(duì)自己最為有利而對(duì)對(duì)方最為不利的那個(gè)行動(dòng)方案。此時(shí)，如果我們站在A 方的立場(chǎng)上，則可供A 方選擇的若干行動(dòng)方案之間是“或”關(guān)系，因?yàn)橹鲃?dòng)權(quán)操在A 方手里，他或者選擇這個(gè)行動(dòng)方案，或者選擇另一個(gè)行動(dòng)方案，完全由A 方?jīng)Q定。但是，若B 方也有若干個(gè)可供選擇的行動(dòng)方案，則對(duì)A 方來(lái)說(shuō)這些行動(dòng)方案

32、之間是“與”關(guān)系，因?yàn)檫@時(shí)主動(dòng)權(quán)操在B 方手里，這些可供選擇的行動(dòng)方案中地任何一個(gè)都可能被B 方選中，A 方必須考慮到對(duì)自己最不利的情況發(fā)生。 若把上述博弈過(guò)程用圖表示出來(lái)，得到的是一棵“與/或”樹。這里要特別指出，該“與/或”樹是始終站在某一方（例如A 方）的立場(chǎng)上得出的，決不可一會(huì)兒站在這一方的立場(chǎng)上,一會(huì)兒又站在另一方的立場(chǎng)上。3.4 博弈樹搜索第三章 智能搜索of31692極小極大分析法 極大極小過(guò)程是考慮雙方對(duì)弈若干步之后，從可能的走法中選一步相對(duì)好的走法來(lái)走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。 為此我們需要定義一個(gè)局面估價(jià)函數(shù)：我們給每個(gè)局面（State）規(guī)定一個(gè)估價(jià)函數(shù)值f ，評(píng)

33、價(jià)它對(duì)于己方的有利程度。勝利的局面的估價(jià)函數(shù)值為+，而失敗的局面的估價(jià)函數(shù)值為。3.4 博弈樹搜索第三章 智能搜索of31702極小極大分析法 Max局面：假設(shè)這個(gè)局面輪到己方走，有多種決策可以選擇，其中每種決策都會(huì)形成一種子局面（Sub-State）。由于決策權(quán)在我們手中，當(dāng)然是選擇估價(jià)函數(shù)值f最大的子局面，因此該局面的估價(jià)函數(shù)值等于其子局面f的最大值，把這樣的局面稱為Max局面。 Min局面：假設(shè)這個(gè)局面輪到對(duì)方走，它也有多種決策可以選擇，其中每種決策都形成一種子局面（Sub-State）。但由于決策權(quán)在對(duì)方手中，在最壞的情況下，對(duì)方當(dāng)然是選擇估價(jià)函數(shù)值f最小的子局面，因此該局面的估價(jià)函數(shù)

34、值等于其子局面f值的最小值，把這樣的局面稱為Min局面。3.4 博弈樹搜索第三章 智能搜索of31712極小極大分析法終結(jié)局面：勝負(fù)已分（假設(shè)沒(méi)有和局）極小極大分析法示例圖3.4 博弈樹搜索第三章 智能搜索of31722極小極大分析法3.4 博弈樹搜索第三章 智能搜索of31732極小極大分析法 但是，實(shí)際問(wèn)題中的所有局面所產(chǎn)生的博弈樹一般都是非常龐大，非常龐大的多叉樹，并不能依靠暴力搜索來(lái)尋找最佳解法。因此需要用到一些剪枝手段，常用的比較初級(jí)的有-剪枝技術(shù)。3.4 博弈樹搜索第三章 智能搜索of31743-剪枝技術(shù) -剪枝算法是一個(gè)搜索算法旨在減少在其搜索樹中，被極大極小算法評(píng)估的節(jié)點(diǎn)數(shù)。這

35、是一個(gè)常用人機(jī)游戲?qū)沟乃阉魉惴?。它的基本思想是根?jù)上一層已經(jīng)得到的當(dāng)前最優(yōu)結(jié)果，決定目前的搜索是否要繼續(xù)下去。 -剪枝算法是對(duì)Minimax方法的優(yōu)化，它們產(chǎn)生的結(jié)果是完全相同的，只不過(guò)運(yùn)行效率不一樣。3.4 博弈樹搜索第三章 智能搜索of31753-剪枝技術(shù)這種方法的前提假設(shè)與Minimax也是一樣的： 1）雙方都按自己認(rèn)為的最佳著法行棋。 2）對(duì)給定的盤面用一個(gè)分值來(lái)評(píng)估，這個(gè)評(píng)估值永遠(yuǎn)是從一方（搜索程序）來(lái)評(píng)價(jià)的，紅方有利時(shí)給一個(gè)正數(shù)，黑方有利時(shí)給一個(gè)負(fù)數(shù)。（如果紅方有利時(shí)返回正數(shù)，當(dāng)輪到黑方走棋時(shí)，評(píng)估值又轉(zhuǎn)換到黑方的觀點(diǎn)，如果認(rèn)為黑方有利，也返回正數(shù)，這種評(píng)估方法都不適合于常規(guī)的算

36、法描述）。 3）從我們的搜索程序（通常把它稱為Max）看來(lái)，分值大的數(shù)表示對(duì)己方有利，而對(duì)于對(duì)方Min來(lái)說(shuō)，它會(huì)選擇分值小的著法。3.4 博弈樹搜索第三章 智能搜索of31763-剪枝技術(shù) -剪枝技術(shù)只能用遞歸來(lái)實(shí)現(xiàn)。這個(gè)思想是在搜索中傳遞兩個(gè)值，第一個(gè)值是，即搜索到的最好值，任何比它更小的值就沒(méi)用了，因?yàn)椴呗跃褪侵赖闹?，任何小于或等于的值的合理著法都不?huì)對(duì)整個(gè)局面的獲勝率有更高的提高。 第二個(gè)值是，即對(duì)于對(duì)手來(lái)說(shuō)最壞的值。這是對(duì)手所能承受的最壞的結(jié)果，因?yàn)槲覀冎涝趯?duì)手看來(lái)，他總是會(huì)找到一個(gè)對(duì)策不比更壞的。如果搜索過(guò)程中返回或比更好的值，那就夠好的了，走棋的一方就沒(méi)有機(jī)會(huì)使用這種策略。3.

37、4 博弈樹搜索第三章 智能搜索of31773-剪枝技術(shù) 在搜索著法時(shí)，每個(gè)搜索過(guò)的著法都返回跟和有關(guān)的值，它們之間的關(guān)系非常重要，或許意味著搜索可以停止并返回。 如果某個(gè)著法的結(jié)果小于或等于，那么它就是很差的著法，因此可以拋棄。因?yàn)槲仪懊嬲f(shuō)過(guò)，在這個(gè)策略中，局面對(duì)走棋的一方來(lái)說(shuō)是以為評(píng)價(jià)的。3.4 博弈樹搜索第三章 智能搜索of31783-剪枝技術(shù) 如果某個(gè)著法的結(jié)果大于或等于 ，那么整個(gè)節(jié)點(diǎn)就作廢了，因?yàn)閷?duì)手不希望走到這個(gè)局面，而它有別的著法可以避免到達(dá)這個(gè)局面。因此如果我們找到的評(píng)價(jià)大于或等于 ，就證明了這個(gè)結(jié)點(diǎn)是不會(huì)發(fā)生的，因此剩下的合理著法沒(méi)有必要再搜索。 如果某個(gè)著法的結(jié)果大于但小于

38、，那么這個(gè)著法就是走棋一方可以考慮走的，除非以后有所變化。因此會(huì)不斷增加以反映新的情況。有時(shí)候可能一個(gè)合理著法也不超過(guò) ，這在實(shí)戰(zhàn)中是經(jīng)常發(fā)生的，此時(shí)這種局面是不予考慮的，為了避免這樣的局面，我們必須在博弈樹的上一個(gè)層局面中選擇另外一個(gè)著法。3.4 博弈樹搜索第三章 智能搜索of31793-剪枝技術(shù) 下圖3-29中第四層的4的值為4比其父節(jié)點(diǎn)的值5要小，所以將其剩余的枝剪去。AlphaBeta剪枝示例圖3.4 博弈樹搜索第三章 智能搜索of31804蒙特卡洛樹搜索 蒙特卡洛樹搜索（Monte Carlo Tree Search）并不是一種模擬人的算法。而是通過(guò)隨機(jī)的對(duì)游戲進(jìn)行推演來(lái)逐漸建立一棵不對(duì)稱的搜索樹的過(guò)程?？梢钥闯墒悄撤N意義上的強(qiáng)化學(xué)習(xí)，當(dāng)然這一點(diǎn)學(xué)界還有一些爭(zhēng)議。 我們經(jīng)常會(huì)聽到“蒙特卡洛樹搜索”這個(gè)概念，事實(shí)上，蒙