哈爾濱工業(yè)大學(xué)人工智能導(dǎo)論實(shí)驗(yàn)報(bào)告(編輯修改稿)
2024-08-23 08:00 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。如下圖：在breadthFirstSearch中，大體的搜索思路與深度優(yōu)先算法一致，只是搜索的次序發(fā)生了變化。在這里注意，在深度優(yōu)先搜索和廣度優(yōu)先搜索方法中，我們使用的圖搜索算法是一樣的，但是涉及到具體的數(shù)據(jù)結(jié)構(gòu)卻是不同的。在深度優(yōu)先搜索算法中，我們使用棧進(jìn)行操作，在深度優(yōu)先搜索算法中，我們使用隊(duì)列進(jìn)行操作，如下圖所示。這兩種數(shù)據(jù)結(jié)構(gòu)的不同之處就在于其中元素的輸出次序，在深度優(yōu)先搜索中需要按照壓棧順序的逆序進(jìn)行搜索，咋子廣度優(yōu)先搜索中需要按照入隊(duì)順序的順序進(jìn)行搜索。Q3: Uniform Cost Search很多情況下，路徑中的代價(jià)是可以改變的，在這個(gè)問題中，我們完成代價(jià)一致搜索方法。代價(jià)一致搜索，其實(shí)就是一個(gè)貪心搜索，取代擴(kuò)展深度最淺的節(jié)點(diǎn)，代價(jià)一致搜索擴(kuò)展的是路徑消耗最低的節(jié)點(diǎn)n。如果所有單步耗散都相等的話，這種算法就和廣度優(yōu)先搜索算法是一樣的。不過，這樣在擴(kuò)展到一個(gè)具有能返回到同一狀態(tài)的零耗散行動(dòng)的節(jié)點(diǎn)時(shí)就會(huì)陷入無限循環(huán)。在uniformCostSearch函數(shù)中，我們計(jì)算每條路徑的總代價(jià)，將總代價(jià)作為優(yōu)先級(jí)進(jìn)行搜索，待搜索序列存儲(chǔ)于隊(duì)列中。對(duì)于每個(gè)節(jié)點(diǎn)，使用代價(jià)函數(shù)getCostOfActions計(jì)算其所產(chǎn)生的代價(jià)，并依次作為搜索的優(yōu)先級(jí)進(jìn)行搜索。同樣的，對(duì)于每個(gè)節(jié)點(diǎn)添加是否被訪問的標(biāo)記。Q4: A* SearchA*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法，也是許多其他問題的常用啟發(fā)式算法，對(duì)代價(jià)一致搜索算法進(jìn)行了改進(jìn)，加入了一個(gè)估計(jì)代價(jià)h。公式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的代價(jià)估計(jì)，g(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià)，h(n) 是從狀態(tài)n到目標(biāo)狀態(tài)的最佳路徑的估計(jì)代價(jià)（對(duì)于路徑搜索問題，狀態(tài)就是圖中的節(jié)點(diǎn)，代價(jià)就是距離）。在本實(shí)驗(yàn)中，我們使用曼哈頓距離作為啟發(fā)函數(shù)。在aStarSearch函數(shù)中，我們首先搜索具有最低組合成本和啟發(fā)式的節(jié)點(diǎn)。類似于問題三，我們計(jì)算每個(gè)節(jié)點(diǎn)的代價(jià)，并以此為依據(jù)搜索產(chǎn)生結(jié)果集，在搜索的過程中，還需要標(biāo)記節(jié)點(diǎn)是否已經(jīng)被訪問過。Q5: Corners Problem: Representation找到所有的角落，在角落迷宮的四個(gè)角上面有四個(gè)豆，通過這個(gè)函數(shù)找到一條訪問所有四個(gè)角落的最短的路徑。在CornersProblem
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1