人工智能中的搜索問(wèn)題

1、Searching Problems in AI人工智能中的搜索問(wèn)題12021/3/17 智能體的初始狀態(tài)是確定的 智能體當(dāng)前狀態(tài)是否為目標(biāo)狀態(tài)是可以檢測(cè)的 智能體的狀態(tài)空間是離散的 智能體在每個(gè)狀態(tài)可以采取的合法行動(dòng)和相應(yīng)后繼狀態(tài)是確定的 環(huán)境是靜態(tài)的 路徑的耗散函數(shù)是已知的什么是搜索問(wèn)題搜索問(wèn)題:已知智能體的初始狀態(tài)和目標(biāo)狀態(tài),求解一個(gè)行動(dòng)序列使得智能體能從初始狀態(tài)轉(zhuǎn)移到目標(biāo)狀態(tài)。如果所求序列可以使得總耗散最低,則問(wèn)題稱為最優(yōu)搜索問(wèn)題。22021/3/17幾個(gè)典型的搜索問(wèn)題起始狀態(tài):Arad路徑規(guī)劃問(wèn)題目標(biāo)狀態(tài):Bucharest合法行動(dòng)與后繼的確定性:與某一城市相鄰的城市才能成為合法后繼

2、狀態(tài)空間的離散性:城市是離散的環(huán)境的靜態(tài)性:城市的相對(duì)位置不會(huì)改變路徑的耗散函數(shù)的確定性:城市之間的距離是已知的搜索問(wèn)題:從Arad到Bucharest的路徑最優(yōu)化搜索問(wèn)題:從Arad到Bucharest的最短路徑32021/3/17幾個(gè)典型的搜索問(wèn)題起始狀態(tài)起始狀態(tài)8-Puzzle問(wèn)題目標(biāo)狀態(tài)目標(biāo)狀態(tài)合法行動(dòng)與后繼的確定性:只有空格四周的格子是可以移動(dòng)的狀態(tài)空間的離散性:8個(gè)格子的排列方式是離散的環(huán)境的靜態(tài)性:九宮格的大小和形狀在格子移動(dòng)過(guò)程中不會(huì)改變路徑的耗散函數(shù)的確定性:相鄰兩個(gè)狀態(tài)之間所需步驟為1搜索問(wèn)題:從起始狀態(tài)到目標(biāo)狀態(tài)的移動(dòng)方法最優(yōu)化搜索問(wèn)題:從起始狀態(tài)到目標(biāo)狀態(tài)步驟最少的移動(dòng)

3、方法華容道是不是一個(gè)搜索問(wèn)題華容道是不是一個(gè)搜索問(wèn)題?42021/3/17幾個(gè)典型的搜索問(wèn)題八皇后問(wèn)題合法行動(dòng)與后繼的確定性:滿足棋盤上所有皇后不能互相攻擊的后繼才是合法的狀態(tài)空間的離散性:0-8個(gè)皇后在棋盤上的擺放方式環(huán)境的靜態(tài)性:棋盤的格局和大小不會(huì)改變路徑的耗散函數(shù)的確定性:相鄰兩個(gè)狀態(tài)之間所需步驟為1搜索問(wèn)題:求出（所有）合法的目標(biāo)狀態(tài)起始狀態(tài):空的棋盤目標(biāo)狀態(tài):棋盤上擺了八個(gè)皇后,并且任意兩個(gè)皇后都不能互相攻擊。目標(biāo)狀態(tài)不確定,但是當(dāng)前狀態(tài)是否為目標(biāo)狀態(tài)是可以檢測(cè)的。52021/3/17搜索問(wèn)題的組成 初始狀態(tài):智能體所處的初始狀態(tài) 后繼函數(shù):輸入給定狀態(tài),可以輸出合法行動(dòng)和相應(yīng)的后

4、繼狀態(tài) 目標(biāo)測(cè)試:用來(lái)確定給定的狀態(tài)是否為目標(biāo)狀態(tài) 路徑耗散函數(shù):在兩個(gè)給定狀態(tài)之間進(jìn)行轉(zhuǎn)移所需的“代價(jià)”普通搜索問(wèn)題:求出一條從初始狀態(tài)到目標(biāo)狀態(tài)之間的行動(dòng)序列全局搜索問(wèn)題:求出所有從初始狀態(tài)到目標(biāo)狀態(tài)之間的行動(dòng)序列最優(yōu)化搜索問(wèn)題:求出從初始狀態(tài)到目標(biāo)狀態(tài)之間耗散最少的行動(dòng)序列62021/3/17搜索問(wèn)題的求解所有搜索過(guò)程都可以用搜索樹算法來(lái)進(jìn)行表示搜索樹72021/3/17搜索問(wèn)題的求解搜索樹實(shí)例82021/3/17搜索問(wèn)題的求解搜索樹實(shí)例92021/3/17搜索問(wèn)題的求解搜索樹實(shí)例102021/3/17搜索問(wèn)題的求解節(jié)點(diǎn)與狀態(tài)的區(qū)別 節(jié)點(diǎn)（Node）是一種數(shù)據(jù)結(jié)構(gòu),每個(gè)節(jié)點(diǎn)的信息包括當(dāng)前

5、狀態(tài)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、深度和路徑耗散 狀態(tài)（State）只是一種系統(tǒng)可能存在的形式 不同節(jié)點(diǎn)包含的狀態(tài)可能是相同的112021/3/17搜索問(wèn)題的求解 完備性:當(dāng)問(wèn)題有解時(shí),這個(gè)算法是否保證能找到一個(gè)解? 最優(yōu)性:這個(gè)搜索策略是否能找到最優(yōu)解? 時(shí)間復(fù)雜度:找一個(gè)解需要花費(fèi)多長(zhǎng)時(shí)間? 空間復(fù)雜度:在執(zhí)行搜索過(guò)程中需要多少內(nèi)存?普通搜索問(wèn)題:求出一條從初始狀態(tài)到目標(biāo)狀態(tài)之間的行動(dòng)序列全局搜索問(wèn)題:求出所有從初始狀態(tài)到目標(biāo)狀態(tài)之間的行動(dòng)序列最優(yōu)化搜索問(wèn)題:求出從初始狀態(tài)到目標(biāo)狀態(tài)之間耗散最少的行動(dòng)序列搜索策略的性能122021/3/17搜索問(wèn)題的求解 無(wú)信息的搜索策略:無(wú)法知道當(dāng)前狀態(tài)離目標(biāo)狀態(tài)的

6、“遠(yuǎn)近”或者不利用類似的先驗(yàn)信息來(lái)進(jìn)行搜索的策略 廣度優(yōu)先搜索（BFS,Breadth-first search） 代價(jià)一致搜索（UCS,Uniform-cost search） 深度優(yōu)先搜索（DFS,Depth-first search） 深度有限搜索（Depth-limited search） 迭代深入搜索（Iterative deepening search） 有信息的（啟發(fā)式）搜索策略:利用啟發(fā)式信息來(lái)進(jìn)行搜索的策略 貪婪最佳優(yōu)先搜索（Greedy best first search） A*搜索（A* search）搜索策略的分類不同搜索策略的區(qū)別僅在于擴(kuò)展節(jié)點(diǎn)的順序132021/3/

7、17無(wú)信息的搜索策略廣度優(yōu)先搜索 先被訪問(wèn)的節(jié)點(diǎn)先進(jìn)行擴(kuò)展 每次擴(kuò)展深度最淺的節(jié)點(diǎn) 可以用一個(gè)先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)來(lái)保存待擴(kuò)展節(jié)點(diǎn)序列CBDECFGDEDGEFCDEDEFG142021/3/17無(wú)信息的搜索策略代價(jià)一致搜索 累積路徑耗散最小的節(jié)點(diǎn)先被擴(kuò)展 倘若每一步的耗散都為正,則保證可以得到最優(yōu)解 若單步耗散相等,該算法和廣度優(yōu)先搜索一樣CBDE?CDE?為累積路徑耗散最小的節(jié)點(diǎn)152021/3/17無(wú)信息的搜索策略深度優(yōu)先搜索 后被訪問(wèn)的節(jié)點(diǎn)先進(jìn)行擴(kuò)展 每次擴(kuò)展深度最深的節(jié)點(diǎn) “一條路走到黑”,對(duì)于無(wú)邊界搜索問(wèn)題無(wú)法保證完備性 可以用一個(gè)后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)來(lái)保存待擴(kuò)展節(jié)點(diǎn)序列162021/

8、3/17無(wú)信息的搜索策略深度優(yōu)先搜索CBEDDIHCECEDCEIH172021/3/17無(wú)信息的搜索策略深度優(yōu)先搜索CHICECEICEIHEICE182021/3/17無(wú)信息的搜索策略深度有限搜索 深度優(yōu)先搜索它可能錯(cuò)誤地選擇一條分支并且沿著一條很長(zhǎng)的（甚至是無(wú)限的）路徑一直走下去 對(duì)于無(wú)邊界的搜索問(wèn)題,可以通過(guò)對(duì)深度優(yōu)先搜索提供一個(gè)預(yù)先設(shè)定的深度限制m來(lái)防止深度優(yōu)先搜索進(jìn)入死循環(huán) 如果目標(biāo)深度d深度限制m,深度有限搜索可能無(wú)法得到解,因此完備性也無(wú)法保證192021/3/17無(wú)信息的搜索策略迭代深入搜索 用來(lái)尋找最合適的深度限制的通用策略,經(jīng)常和深度優(yōu)先搜索結(jié)合使用 不斷增大深度限制,直

9、到找到目標(biāo)節(jié)點(diǎn) 結(jié)合了深度有限搜索的優(yōu)點(diǎn),又保證了完備性,還能保證得到最優(yōu)解202021/3/17無(wú)信息的搜索策略迭代深入搜索212021/3/17無(wú)信息的搜索策略策略之間的比較為了避免含有相同狀態(tài)的節(jié)點(diǎn)被重復(fù)擴(kuò)展,可以用一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄所有被訪問(wèn)過(guò)的節(jié)點(diǎn)。如果當(dāng)前待擴(kuò)展節(jié)點(diǎn)與某個(gè)已訪問(wèn)過(guò)的節(jié)點(diǎn)對(duì)應(yīng)的狀態(tài)相同的話,則當(dāng)前節(jié)點(diǎn)將不會(huì)被擴(kuò)展。這時(shí)樹搜索（Tree Search）策略將成為圖（Graph Search）策略222021/3/17啟發(fā)式搜索策略最佳搜索策略 最佳優(yōu)先搜索的通用思想:用一個(gè)評(píng)價(jià)函數(shù)f(n)來(lái)對(duì)節(jié)點(diǎn)進(jìn)行評(píng)價(jià)。在擴(kuò)展節(jié)點(diǎn)的過(guò)程中,從候選節(jié)點(diǎn)中選擇f(n)最小的節(jié)點(diǎn)來(lái)進(jìn)行擴(kuò)展

10、。 對(duì)于BFS,f(n)表示節(jié)點(diǎn)深度;對(duì)于UCS,f(n)表示節(jié)點(diǎn)的累計(jì)路徑耗散;對(duì)于DFS,f(n)表示節(jié)點(diǎn)深度的負(fù)值 很多時(shí)候f(n)不能真正度量節(jié)點(diǎn)的好壞,因此可以考慮引進(jìn)啟發(fā)式信息來(lái)估計(jì)節(jié)點(diǎn)離目標(biāo)狀態(tài)的距離啟發(fā)式函數(shù):h(n)=從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的耗散估計(jì)值232021/3/17啟發(fā)式搜索策略貪婪最佳優(yōu)先搜索評(píng)價(jià)函數(shù)f(n)=h(n)在這個(gè)路徑規(guī)劃問(wèn)題中,h(n)取為當(dāng)前城市離目標(biāo)Bucharest的直線距離242021/3/17啟發(fā)式搜索策略貪婪最佳優(yōu)先搜索評(píng)價(jià)函數(shù)f(n)=h(n)252021/3/17啟發(fā)式搜索策略貪婪最佳優(yōu)先搜索評(píng)價(jià)函數(shù)f(n)=h(n)26202

11、1/3/17啟發(fā)式搜索策略貪婪最佳優(yōu)先搜索評(píng)價(jià)函數(shù)f(n)=h(n)272021/3/17啟發(fā)式搜索策略貪婪最佳優(yōu)先搜索 與深度優(yōu)先搜索一樣,它更傾向于沿著一條路徑搜索下去直到目標(biāo) 因?yàn)樵跀U(kuò)展節(jié)點(diǎn)時(shí)沒有考慮累計(jì)路徑耗散,因此它也不能保證得到最優(yōu)解 如果狀態(tài)空間是無(wú)限的,它也可能是不完備的282021/3/17啟發(fā)式搜索策略A*搜索 為了彌補(bǔ)貪婪最佳優(yōu)先搜索無(wú)法找到最優(yōu)解的缺點(diǎn),考慮在評(píng)價(jià)函數(shù)里加入累計(jì)路徑耗散,由此形成A*搜索算法評(píng)價(jià)函數(shù)f(n)=g(n)+h(n)g(n):從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的路徑耗散h(n):從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的耗散估計(jì)值f(n):經(jīng)過(guò)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的總耗散估計(jì)值292021/3/17啟發(fā)式搜索策略A*搜索302021/3/17啟發(fā)式搜索策略A*搜索312021/3/17啟發(fā)式搜索策略A*搜索322021/3/17啟發(fā)式搜索策略A*搜索332021/3/17啟發(fā)式搜索策略A*搜索