導航:首頁 > 源碼編譯 > 尋路演算法php

尋路演算法php

發布時間:2022-11-26 17:04:16

⑴ 誰能介紹一下JPS尋路演算法的思想

這是一個近年來發現的高效尋路演算法。不過有一個限制就是只能在規則的網格地圖上尋路,而且圖上的點或邊不能帶權重,也就是不能有復雜的地形,只支持平坦和障礙兩種地形。


思想就是跳過矩形平坦區域的大量對稱路徑,只尋找所謂的跳躍點,作為搜索的節點。這樣做的好處是裁剪了矩形區域內大量的節點,使open
list中的節點數相對較少。要知道,通常啟發式搜索演算法如A*,大量時間耗費在對open
list的操作上。實現得好的A*演算法會使用優先隊列,甚至HOT(heap on top)來對操作進行優化。但當open
list中的節點過多,這些操作還是會變得很昂貴。不過JPS有個缺點是每生成一個節點,也就是要找到一個跳躍點,相比較A*演算法,是比較昂貴的。幸好通
常來說,得到的收益更多些。所以,在適用的情況下,還是推薦使用JPS的。

具體的實現,主要有兩部分。第一部分,從open list中取一個最佳節點,然後從幾個特定方向展開搜索,把每個方向得到的跳躍點,加入open list里。第二部分,就是找到一個跳躍點。

對於起始點,可以向所有方向展開搜索。對於其他節點,要看父節點指向本節點的方向,向所有自然鄰居和被迫鄰居節點方向進行搜索。
例如下圖的例子,對於節點n和父節點p和障礙x,+是n的自然鄰居,也就是說從p到n到+是最佳路徑。如果x不是障礙,從p到n到-不是最佳路徑,因為從p到x到-最近。但是如果x是障礙,那麼從p到n到-就是最佳路徑了,所以這時候稱-為被迫鄰居。
- + +
x n +
p x -
以上是n和p對角的例子。還有種情況是n和p是直線:
x x -
p n +
x x -


尋跳躍點是遞歸進行的。首先判斷一個節點是否是跳躍點。如果這個點有被迫鄰居,那麼這個節點就是跳躍點。第二種情況,如果這個節點是目的地節點那麼也當作
跳躍點。如果不是,那麼就遞歸地沿本來方向繼續搜尋下去。對於對角方向要額外多做兩步,即先對其相應的(左右兩個)直線方向進行搜索,如果找到跳躍點,就
把自身也當作跳躍點返回。如果直線沒找到,那麼就一樣繼續按對角方向遞歸尋找跳躍點,並返回那個跳躍點。

⑵ 從頭理解JPS尋路演算法

本文的思路受到博客: http://blog.sina.com.cn/s/blog_4a5c75d40102wo5l.html
和論文: http://www.doc88.com/p-6099778647749.html 的啟發和借鑒。
JPS(jump point search)演算法實際上是對A 尋路演算法的一個改進,即在擴展搜索節點時,提出了更優化的策略,A 在擴展節點時會把節點所有鄰居都考慮進去,這樣openlist中點的數量會很多,搜索效率較慢。JPS演算法通過尋找跳點的方式,排除了大量不感興趣的點,減少了openlist中搜索的點的數量,速度大大提高。

水平(垂直)搜索:如圖右邊部分描述,點1和4如果經過x到達,還不如從點p(x)到達,所以不用考慮點1,4,同理繼續向右搜索時,點2,5和點3,6,都是類似的情況,直到遇到黑色的障礙,沒有發現感興趣的點,x處水平方向搜索完成,垂直方向搜索類似。如圖左邊部分描述,在點x處向右搜索至點y時,點y有一個強迫鄰居(點7),因此y是從點x處沿水平方向搜索的一個跳點,需要將y加入到openlist中。水平搜索結束。

對角搜索:斜向搜索時,需要先在當前點的水平和垂直方向搜索一下,看能否找到感興趣的點,如果找到,則將當前點加到openlist,結束斜向搜索,如果找不到,則繼續斜向多走一步,繼續,直到找到感興趣的點或者斜向方向遇到障礙。

一條完整路線的搜索過程:

搜索演算法:

下面兩張對比圖,摘自上面的論文,可以看出,JPS演算法實在優秀。

github鏈接

上圖中紅色塊為節點x,基於前節點為P(x)的情況下的自然鄰居節點。而被迫鄰居則是圖中綠色的方塊(其對稱情況未畫出)。x被迫鄰居包含三層隱藏含義:首先被迫鄰居的位置是基於P(x)、x、阻擋塊的相對關系定的,如第三個圖所示,如果第三個圖中,P(x)的位置在節點6的位置,那麼綠色方塊就不是x的被迫鄰居了。其次,被迫鄰居一點是考察非自然鄰居的節點。最後被迫鄰居一定是P(x)經過x到達才能取得最短路徑的點。

起點S,終點T,黑色塊為阻擋黃色塊為跳點,紅色箭頭是搜索方向,但是沒有找到跳點,綠色箭頭表示找到跳點。橫坐標A-N,縱坐標1-10。

起始位置S,將A10加入openlist里,開始演算法流程。
從openlist里取出代價最小的節點(現在為S),當前節點沒有方向,所以需要搜索8個方向,只有右上方B9點是跳點。因為根據跳點定義iii,斜向搜索時,需要在兩個分量方向查找跳點,右方是牆壁,略過,上方B8點有強迫鄰居點C7,所以B8是跳點(根據跳點定義ii),所以B9是跳點。將B9加入openlist里。A10處理完後,將其從openlist中移除,加入closelist里。

從openlist中取出B9點,該點的父親是S,所以搜索方向為右斜上,需要在右斜上,右方,上方搜索跳點,只有B8滿足要求,將B8加入openlist。處理完B9點將其移到closelist。

從openlist取出B8點,該點搜索方向為上,B8有被鄰居C7點,在斜上方搜索跳點,可以看出D8是C7的被迫鄰居,所以C7是跳點,B8處繼續向上搜索結束。

從openlist中取出C7點。需要搜索右上,右,上三個方向。水平搜索時發現被迫鄰居D8,加入openlist。右上搜索時發現跳點G3(因其在上方搜索時發現具有被迫鄰居節點的G2),將G3加入openlist。C7點處理結束。

取出G3點(為啥是G3,而不是D8點呢,因為從總代價來說G3比D8更小,總代價=已經走過的距離 + 估值,估值可採用曼哈頓距離或者高斯距離),需要搜索右上,右,上三個方向。向上搜索到跳點G2。

其餘點路徑在圖上標注,就不再重復了。

(1) 若current方向是直線
i. 如果current左後方不可走且左方可走,則沿current左前方和左方尋找跳點。
ii. 如果current當前方向可走,則沿current方向尋找跳點。
iii. 如果current右後方不可走且右方可走,則沿current右前方和右方尋找跳點。
(2) 若current方向是斜線
i. 如果當前方向的水平分量可走,則沿current方向的水平分量方向尋找跳點。
ii. 如果當前方向可走,沿current方向尋找跳點。
iii. 如果當前方向的垂直分量可走,則沿current方向的垂直分量方向尋找跳點。

上述演算法流程是建立在斜向不可穿過阻擋基礎上。

⑶ 游戲開發需要學什麼編程語言

游戲編程也是編程,都是需要敲代碼的。所以基本的語言基本功是不能少的,比如C語言或者C++或者C#至少要精通其中一門。精通到什麼地步呢,基本數據結構和基礎的演算法還有設計模式你得非常熟悉。這樣算是入門了。

接下來你就可以選擇一個游戲引擎了,市面上主流的游戲引擎有兩種一個Unity3D一個虛幻四。但是這兩款引擎的腳本語言並不一樣,Unity是C#虛幻四是C++所以在學習之前要想好使用引擎開發什麼類型的游戲。

主要學的內容如下:

1.游戲程序設計:C++程序設計入門;基本數據類型和輸入輸出;流程式控制制語句;數組、指針和引用、函數;程序結構和書寫規;范結構體和聯合體、類;繼承與多態;異常處理與程序調試。

2.演算法與數據結構:演算法分析;數據結構;基本演算法;STL的概念與使用;靜態庫與動態庫;XML庫的使用。

3.Win32程序設計:Windows程序入門;Windows消息;GDI繪圖游戲工具與MFC;網路編程基礎。

4.游戲數學和智能應用:游戲中的坐標系;矢量、矩陣;幾何碰撞;物理模擬;人工智慧與尋路演算法。

5.2D游戲技術與應用:2D游戲技術概論;游戲地圖系統;GUI系統;戰斗系統設計;任務系統;優秀的聲音引擎BASS;Cocos2D-X引擎;Box2D物理引擎。

互聯網行業目前還是最熱門的行業之一,學習IT技能之後足夠優秀是有機會進入騰訊、阿里、網易等互聯網大廠高薪就業的,發展前景非常好,普通人也可以學習。

想要系統學習,你可以考察對比一下開設有相關專業的熱門學校,好的學校擁有根據當下企業需求自主研發課程的能力,能夠在校期間取得大專或本科學歷,中博軟體學院、南京課工場、南京北大青鳥等開設相關專業的學校都是不錯的,建議實地考察對比一下。

祝你學有所成,望採納。

⑷ 最短路徑演算法

Dijkstra演算法,A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法,用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解,但由於它遍歷計算的節點很多,所以效率低。

Dijkstra演算法是很有代表性的最短路演算法,在很多專業課程中都作為基本內容有詳細的介紹,如數據結構,圖論,運籌學等等。

Dijkstra一般的表述通常有兩種方式,一種用永久和臨時標號方式,一種是用OPEN, CLOSE表方式,Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致,這里均採用OPEN,CLOSE表的方式。

大概過程:
創建兩個表,OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點,CLOSED表中記錄已訪問過的節點。
1. 訪問路網中里起始點最近且沒有被檢查過的點,把這個點放入OPEN組中等待檢查。
2. 從OPEN表中找出距起始點最近的點,找出這個點的所有子節點,把這個點放到CLOSE表中。
3. 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值,放子節點到OPEN表中。
4. 重復2,3,步。直到OPEN表為空,或找到目標點。

提高Dijkstra搜索速度的方法很多,常用的有數據結構採用Binary heap的方法,和用Dijkstra從起始點和終點同時搜索的方法。

A*(A-Star)演算法是一種啟發式演算法,是靜態路網中求解最短路最有效的方法。

公式表示為: f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數,
g(n) 是在狀態空間中從初始節點到n節點的實際代價,
h(n)是從n到目標節點最佳路徑的估計代價。

保證找到最短路徑(最優解的)條件,關鍵在於估價函數h(n)的選取:
估價值h(n)<= n到目標節點的距離實際值,這種情況下,搜索的點數多,搜索范圍大,效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少,搜索范圍小,效率高,但不能保證得到最優解。
估價值與實際值越接近,估價函數取得就越好。
例如對於幾何路網來說,可以取兩節點間歐幾理德距離(直線距離)做為估價值,即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny));這樣估價函數f在g值一定的情況下,會或多或少的受估價值h的制約,節點距目標點近,h值小,f值相對就小,能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程:
創建兩個表,OPEN表保存所有已生成而未考察的節點,CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點,將n節點放入CLOSE中,取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小,從最小路徑的節點向下進行。
}

A*演算法和Dijistra演算法的區別在於有無估價值,Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網,最短路演算法 D*A* 在靜態路網中非常有效(very efficient for static worlds),但不適於在動態路網,環境如權重等不斷變化的動態環境下。

D*是動態A*(D-Star,Dynamic A*) 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出,主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法:
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k(k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4),4(7)。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動,在移動的下一節點沒有變化時,無需計算,利用上一步Dijstra計算出的最短路信息從出發點向後追述即可,當在Y點探測到下一節點X狀態發生改變,如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y),h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G),Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算,這里假設用A*演算法,遍歷Y的子節點,點放入CLOSE,調整Y的子節點a的h值,h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中,方法如下:
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表;
OPEN表比較k值大小進行排序;
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效,向目標點移動中,只檢查最短路徑上下一節點或臨近節點的變化情況,如機器人尋路等情況。對於距離遠的最短路徑上發生的變化,則感覺不太適用。

⑸ PHP程序員想轉入游戲開發,需要學習哪些知識

游戲開發根據平台有PC游戲開發、移動設備游戲開發(如手機游戲,PSP)、網頁游戲開發等。一般還可以分為2D游戲開發和3D游戲開發。在PC上開發大型的3D游戲一般用C++,在手機上一般是小型的2D游戲,用JAVA,J2ME,網頁不怎麼清楚,一般用flash吧。做游戲的話要掌握一些數學知識(如三角函數)、物理知識(碰撞模擬等),要懂得進行圖形編程,向高級發展還要懂人工智慧(如有限狀態機,A*尋路演算法),如果做3D游戲的話還要懂一些計算機圖形學演算法(如空間變換,光照計算,插值演算法等),根據樓主現有的知識建議樓主做網頁游戲吧,用PHP+flex。樓主既然有興趣那就去做,下定決心,本人以前是做化工的,因為興趣自學轉了做程序員。只要相信自己就能成功。

⑹ 游戲中的常用的尋路演算法有哪些

f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點,
直到最終達到目的結點
– A*演算法的成功很大程度依賴於h(n)函數的構建
?;) = g(n? 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
A*演算法
? h(n) = 從結點n到目的結點的耗費評估值,啟發函數
?,程序返回n
else 生成結點n的每一個後繼結點n;
foreach 結點n的後繼結點n;{
將n』的父結點設置為n
計算啟發式評估函數h(n『)值,評估從n『到node_goal的費用
計算g(n『) = g(n) + 從n』到n的開銷
計算f(n?? 在演算法啟動時,Closed列表為空 A* 演算法偽代碼初始化OPEN列表
初始化CLOSED列表
創建目的結點;稱為node_goal
創建起始結點;稱為node_start
將node_start添加到OPEN列表
while OPEN列表非空{
從OPEN列表中取出f(n)值最低的結點n
將結點n添加到CLOSED列表中
if 結點n與node_goal相等then 我們找到了路徑;)
if n『位於OPEN或者CLOSED列表and 現有f(n)較優then丟棄n』 ;) + h(n?? 包含我們還沒有處理到的結點
? g(n) = 從初始結點到結點n的耗費
?? 包含我們已經處理過的結點
,處理後繼n』
將結點n『從OPEN和CLOSED中刪除
添加結點n『到OPEN列表
}
}
return failure (我們已經搜索了所有的結點?? 啟發式搜索
– 在搜索中涉及到三個函數
??? 我們最開始將起始結點放入到Open列表中
– Closed列表
?

⑺ A*演算法——啟發式路徑搜索

A*是一種路徑搜索演算法,比如為游戲中的角色規劃行動路徑。

A* 演算法的輸入是, 起點(初始狀態) 終點(目標狀態) ,以及兩點間 所有可能的路徑 ,以及涉及到的 中間節點(中間狀態) ,每兩個節點間的路徑的 代價

一般還需要某種 啟發函數 ,即從任意節點到終點的近似代價,啟發函數能夠非常快速的估算出該代價值。

輸出是從 起點到終點的最優路徑 ,即代價最小。同時,好的啟發函數將使得這一搜索運算盡可能高效,即搜索盡量少的節點/可能的路徑。

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

f(n) 是從初始狀態經由狀態n到目標狀態的代價估計

g(n) 是在狀態空間中從初始狀態到狀態n的實際代價

h(n) 是從狀態n到目標狀態的最佳路徑的估計代價

A*演算法是從起點開始,檢查所有可能的擴展點(它的相鄰點),對每個點計算g+h得到f,在所有可能的擴展點中,選擇f最小的那個點進行擴展,即計算該點的所有可能擴展點的f值,並將這些新的擴展點添加到擴展點列表(open list)。當然,忽略已經在列表中的點、已經考察過的點。

不斷從open list中選擇f值最小的點進行擴展,直到到達目標點(成功找到最優路徑),或者節點用完,路徑搜索失敗。

演算法步驟:

參考

A* 演算法步驟的詳細說明請參考 A*尋路演算法 ,它包含圖文案例清楚的解釋了A*演算法計算步驟的一些細節,本文不再詳細展開。

看一下上面參考文檔中的案例圖,最終搜索完成時,藍色邊框是close list中的節點,綠色邊框是open list中的節點,每個方格中三個數字,左上是f(=g+h),左下是g(已經過路徑的代價),右下是h(估計未經過路徑的代價)。藍色方格始終沿著f值最小的方向搜索前進,避免了對一些不好的路徑(f值較大)的搜索。(圖片來自 A*尋路演算法 )

現在我們可以理解,A*演算法中啟發函數是最重要的,它有幾種情況:

1) h(n) = 0
一種極端情況,如果h(n)是0,則只有g(n)起作用,此時A*演變成Dijkstra演算法,這保證能找到最短路徑。但效率不高,因為得不到啟發。

2) h(n) < 真實代價
如果h(n)經常都比從n移動到目標的實際代價小(或者相等),則A*保證能找到一條最短路徑。h(n)越小,A*擴展的結點越多,運行就得越慢。越接近Dijkstra演算法。

3) h(n) = 真實代價
如果h(n)精確地等於從n移動到目標的代價,則A*將會僅僅尋找最佳路徑而不擴展別的任何結點,這會運行得非常快。盡管這不可能在所有情況下發生,你仍可以在一些特殊情況下讓它們精確地相等(譯者:指讓h(n)精確地等於實際值)。只要提供完美的信息,A*會運行得很完美,認識這一點很好。

4) h(n) > 真實代價
如果h(n)有時比從n移動到目標的實際代價高,則A*不能保證找到一條最短路徑,但它運行得更快。

5) h(n) >> 真實代價
另一種極端情況,如果h(n)比g(n)大很多,則只有h(n)起作用,A*演變成BFS演算法。

關於啟發函數h、Dijkstra演算法、BFS(最佳優先搜索)演算法、路徑規劃情況下啟發函數的選擇、演算法實現時List的數據結構、演算法變種等等更多問題,請參考: A*演算法

⑻ 游戲開發都會學什麼

游戲開發需要學習C語言系列、UE4這些常用游戲引擎,門檻很高。但游戲開發行業的整體收入水平,確實算是高薪了,學成後回報較高。

游戲開發所涉及的技能知識面較多,且難以把握學習難度,不建議自學。小白建議從UI做起,因為UI開發中簡單重復而瑣碎的工作相對比較多。

主要學的內容如下:

1.游戲程序設計:C++程序設計入門;基本數據類型和輸入輸出;流程式控制制語句;數組、指針和引用、函數;程序結構和書寫規;范結構體和聯合體、類;繼承與多態;異常處理與程序調試。

2.演算法與數據結構:演算法分析;數據結構;基本演算法;STL的概念與使用;靜態庫與動態庫;XML庫的使用。

3.Win32程序設計:Windows程序入門;Windows消息;GDI繪圖游戲工具與MFC;網路編程基礎。

4.游戲數學和智能應用:游戲中的坐標系;矢量、矩陣;幾何碰撞;物理模擬;人工智慧與尋路演算法。

5.2D游戲技術與應用:2D游戲技術概論;游戲地圖系統;GUI系統;戰斗系統設計;任務系統;優秀的聲音引擎BASS;Cocos2D-X引擎;Box2D物理引擎。

互聯網行業目前還是最熱門的行業之一,學習IT技能之後足夠優秀是有機會進入騰訊、阿里、網易等互聯網大廠高薪就業的,發展前景非常好,普通人也可以學習。

想要系統學習,你可以考察對比一下開設有相關專業的熱門學校,好的學校擁有根據當下企業需求自主研發課程的能力,能夠在校期間取得大專或本科學歷,中博軟體學院、南京課工場、南京北大青鳥等開設相關專業的學校都是不錯的,建議實地考察對比一下。

祝你學有所成,望採納。

⑼ 夢幻西遊自動尋路的尋路演算法怎麼算

A*尋路演算法 A*(A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為: f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數,
g(n) 是在狀態空間中從初始節點到n節點的實際代價,
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑(最優解的)條件,關鍵在於估價函數h(n)的選取:
估價值h(n)<= n到目標節點的距離實際值,這種情況下,搜索的點數多,搜索范圍大,效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少,搜索范圍小,效率高,但不能保證得到最優解。
估價值與實際值越接近,估價函數取得就越好。
例如對於幾何路網來說,可以取兩節點間歐幾理德距離(直線距離)做為估價值,即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny));這樣估價函數f在g值一定的情況下,會或多或少的受估價值h的制約,節點距目標點近,h值小,f值相對就小,能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程:
創建兩個表,OPEN表保存所有已生成而未考察的節點,CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點,將n節點放入CLOSE中,取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小,從最小路徑的節點向下進行。
啟發式搜索其實有很多的演算法,比如:局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數,但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法,就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點,父親節點,而一直得搜索下去。這種搜索的結果很明顯,由於舍棄了其他的節點,可能也把最好的
節點都舍棄了,因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了,他在搜索時,便沒有舍棄節點(除非該節點是死節點),在每一步的估價
中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢?其實A*演算法也是一種最
好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時,我們希望能夠求解出狀態空間搜索的最短路徑,也就是用最快的方法求解問題,A*就是干這種事情的!
我們先下個定義,如果一個估價函數可以找出最短的路徑,我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為:
f'(n) = g'(n) + h'(n)
這里,f'(n)是估價函數,g'(n)是起點到終點的最短路徑值,h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的,所以我們用前面的估價函數f(n)做
近似。g(n)代替g'(n),但 g(n)>=g'(n)才可(大多數情況下都是滿足的,可以不用考慮),h(n)代替h'(n),但h(n)<=h'(n)才可(這一點特別的重要)。可以證明應用這樣的估價
函數是可以找到最短路徑的,也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎?肯定沒懂。接著看。
舉一個例子,其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數,h(n)=0,這種h(n)肯定小於h'(n),所以由前述可知廣度優先演算法是一種可採納的。實際也是
。當然它是一種最臭的A*演算法。
再說一個問題,就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件,如果信息越多或約束條件越多則排除的節點就越多,估價函
數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了,誰叫它的h(n)=0,一點啟發信息都沒有。但在游戲開發中由於實時性的問題,h(n)的信息越多,它的計
算量就越大,耗費的時間就越多。就應該適當的減小h(n)的信息,即減小約束條件。但演算法的准確性就差了,這里就有一個平衡的問題。
}

閱讀全文

與尋路演算法php相關的資料

熱點內容
安卓諾基亞質量怎麼樣 瀏覽:67
有沒有不懂英文的程序員 瀏覽:985
hhkb鍵盤適用程序員嗎 瀏覽:871
室內設計pdf下載 瀏覽:3
同步助手app文件夾 瀏覽:966
pythontofile 瀏覽:279
我的世界中國版創造伺服器地址 瀏覽:671
rs232與單片機連接 瀏覽:563
程序員培訓機構感覺很坑 瀏覽:160
編譯器腳本意思 瀏覽:326
apachelinux配置代理 瀏覽:294
程序員的命運會怎樣 瀏覽:663
看逗逗App怎麼樣 瀏覽:445
新英朗壓縮比 瀏覽:297
代購幫app的錢怎麼提現 瀏覽:338
android藍牙可見 瀏覽:360
python游戲編程入門pdf 瀏覽:701
深金融app是干什麼的 瀏覽:611
程序員公園倒立 瀏覽:384
工作應酬吃辣片緩解壓力嗎 瀏覽:427