台灣最大程式設計社群網站
線上人數
801
 
會員總數:244988
討論主題:188956
歡迎您免費加入會員
討論區列表 >> C/C++ >> 演算法
[]  
[我要回覆]
1
回應主題 加入我的關注話題 檢舉此篇討論 將提問者加入個人黑名單
演算法
價值 : 30 QP  點閱數:5808 回應數:4

樓主

0.1
門外漢
0 5
68 13
發送站內信



http://www.chinagamedev.net/cgd/develop/ai/200111/CloudWuAStar.htm

請問各位大大

我在找最短路徑時``找到此篇資料

並下載了~~左下角" 本文附带的源程序"

我把整段程式碼複製ㄚ~~~可是一直出現錯誤

他還有附一個map的檔案

請問那是~~要如果用呢??拜託~~~

本篇文章發表於2005-03-06 15:56
別忘捐VP感謝幫助你的人 新手會員瞧一瞧
1樓
回應

小白
捐贈 VP 給 Marcus 檢舉此回應
MAP.DAT 應該是該程式的輸入檔案。

其實 A* 搜尋算法並不難寫,如果別人的 Run 不到的話,就自己寫一個好了 :)
最好是去參考一下別人的估計函數 h(x) 怎麼寫,這個對於您寫 A* 算法會有很大的幫助。

另外,尋找最短路徑也不一定要用 A* ,對於某些情況來說(如推箱子遊戲)的最佳解反而用廣度優先搜尋比較快。

本篇文章回覆於2005-03-07 00:11
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
2樓
作者回應

0.1
檢舉此回應

感謝回答~~~
本篇文章回覆於2005-03-07 20:38
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
3樓
作者回應

0.1
檢舉此回應
請問有大大知道~~比較豐富的演算法論壇還是網站嗎?

最近狂需找有關最短路徑的搜尋法~~

而a*比較符合我所需要之方法~~~
本篇文章回覆於2005-03-07 23:43
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
4樓
最有價值解答

小白
捐贈 VP 給 Marcus 檢舉此回應
最主要的論壇有 ACM UVA 的論壇 (http://acm.uva.es/ 的 electronic board)

其實我在這堨i以簡單地介紹一下一些最短路徑尋找方法的演算法。

1. 最簡單的:廣度優先搜尋 Breadth First Search
對於所有未尋訪而當前節點可到達的節點,即搜尋他,並把它加進隊列內。
這是假設了在 G(V,E) 中每個 Edge 的長度為一。

2. Dijkstra's Algorithm
對於所有未到達而可到達的節點,把它加進優先隊列 (priority queue) 內,依照 edge 的長度由短至長搜尋之。
這堸眾]在 G(V,E) 中每個 Edge 的長度不是負數。

3. Bellman Ford Algorithm
對於每一個節點,先假設它們之間的長度是無限 (通常在電腦編程時會設成 2147483647/2 )
然後執行 V-1 次:對於每個 Edge (u,v) ,如果距離[u] < 距離[v] + 由 u 到 v 的 Edge 的長度,則把距離[u]設成距離[v] + 由 u 到 v 的 Edge 的長度。

4. Foyld-Warshall Algorithm
這個演算法可以找出*所有*節點的最短路徑。

首先把 d[i][j] 設成由 i 至 j 之間的 edge 長度。

For k ← 1 To N Do
   For i ← 1 To N Do
      For j ← 1 To N Do
         d[i][j] = Min(d[i][j], d[i][k] + d[k][j])

5. A* 搜尋法
以一估計函數 h(x) 判斷跟目標相差多遠。使用一 priority queue ,使用 h(x) + 該步的代價排序,使用類似 BFS 的方法作搜尋。


另外還有一些演算法你可以去找找:
IDA* 搜尋法
MA*
SA*
雙向式 BFS

加油!
本篇文章回覆於2005-03-08 00:22
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
   
1

回覆
如要回應,請先登入.