A星算法試驗報告11_第1頁
A星算法試驗報告11_第2頁
A星算法試驗報告11_第3頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

本文格式為Word版，下載可任意編輯——A星算法試驗報告11

人工智能

學(xué)院：信息學(xué)院班級:學(xué)號：姓名：

一、試驗原理

A*算法，作為啟發(fā)式算法中很重要的一種，被廣泛應(yīng)用在最優(yōu)路徑求解和一些策略設(shè)計的問題中。而A*算法最為核心的部分，就在于它的一個估值函數(shù)的設(shè)計上：

f(n)=g(n)+h(n)

其中f(n)是每個可能試探點的估值，它有兩部分組成：一部分為g(n)，它表示從起始探尋點到當(dāng)前點的代價（尋常用某結(jié)點在探尋樹中的深度來表示）。另一部分，即h(n)，它表示啟發(fā)式探尋中最為重要的一部分，即當(dāng)前結(jié)點到目標(biāo)結(jié)點的估值，h(n)設(shè)計的好壞，直接影響著具有此種啟發(fā)式函數(shù)的啟發(fā)式算法的是否能稱為A*算法。

一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：1)探尋樹上存在著從起始點到終了點的最優(yōu)路徑。2)問題域是有限的。

3）所有結(jié)點的子結(jié)點的探尋代價值>0。4）h(n)=g+1;}

if(lei==2)//假使是斜線走

{g_value=father->g+1.414;}

修改后的擴展結(jié)點數(shù)837三、試驗分析

A*算法最為核心的過程，就在每次選擇下一個當(dāng)前探尋點時，是從所有已探知的但未探尋過點中(可能是不同層，亦可不在同一條支路上)，選取f值最小的結(jié)點進行展開。而所有“已探知的但未探尋過點〞可以通過一個按f值升序的隊列(即優(yōu)先隊列)進行排列。這樣，在整體的探尋過程中，只要依照類似廣度優(yōu)先的算法框架，從優(yōu)先隊列中彈出隊首元素（f值），對其可能子結(jié)點計算g、h和f值，直到優(yōu)先隊列為空(無解)或找到終止點為止。

若修改地圖該算法得到的路徑是：

算法仍舊有效

其實該算法的啟發(fā)函數(shù)是兩點之間的歐式距離，即當(dāng)前點到目標(biāo)點的直線距離，對于此題目來說歐式距離啟發(fā)信息相對太少，若將啟發(fā)函數(shù)改為：

chang=end_x-x;

kuan=end_y-y;if(chang>=kuan)

{distance=(int)1.414*kuan+chang-kuan;}else

{distance=(int)1.414*chang+kuan-chang;

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論