Re: [問題] 演算法問題...
※ 引述《H45 (!H45)》之銘言：
: ※ 引述《TonyQ (骨頭)》之銘言：
: BFS 不行嗎...?
: 覺得廣度優先走訪太笨的話，就用 Best first search
: 其中的 A* algorithm 應該是最「聰明」的吧？ (當然有許多元素要自己定義)
嗯 後來採用A*
cost不高(距離是20格內的小地圖 , 每次約0~5 ms)
又很自然，是很不錯的東西。
貼上一點當時的參考資料和我的實作code
參考資料 (這兩篇其實是翻譯同一篇文章 不過對照著看有不同收穫)
http://www.roboticfan.com/college/knowledge/200606/147.shtml
http://swf.com.tw/?p=67
code實作
http://tony1223.no-ip.info:1223/bmore?Flyword&4642
(因為碼有點長，我直接貼我的webbs連結。
如果連結跑掉了可以來信跟我說T^T)
底下是一點點的心得 , 有錯的地方歡迎提出來討論 .(冏)
1.基本原理 g = 路徑成本 , h=到達目標的"估計"成本 , F=總成本(g+h)
它並不直接找出一條路徑，而是透過計算成本後指定前一格的方式。
當到達終點時，透過終點回推最低成本的路徑，
從終點的的前一格→前一格→前一格→起始格‧找到路徑。
有點類似LinkedList的那種串聯的概念...
這邊看起來還蠻抽象的T^Ta 失敗了三四次才成功
2.它的發展並不是就單一條線的發展
而是就目前的視野(openlist)
去找出以目前的視野底下成本最低的路徑(F值最低)
我一開始一直以為它是沿線尋找...所以把cango寫錯了...
這是蠢點1 orz
3.它的作法是建立一個大地圖的陣列(whichlist)，然後每次查詢給與不
同的onClose跟onOpen，感覺上是為了方便連續多次的查找的時候，
不會互相混淆。
不過我的case由於地圖本身座標值蠻高的，
幾百個地圖又沒有一個固定的size，所以建表法對我來講不實際。
我採用的是把xy先做hash , f(x,y) = x*最大長度 +y 的狀況，
(in my case f(x,y) = 50000*x+y)
把看過的點(onOpen and onClose) 建立在 allpoint 這個HashMap裡面。
只要透過查找Hash值就可以馬上知道這個點是不是已經存在，
而且也可以知道這個點是 onClose或onOpen 。(透過Node的type紀錄)
4.另外openList採用BinaryHeap維護 ... (minHeap)
降低查找最低F的成本 (這個增進效能非常多)
────────────────────────────────
3跟4 如果是用List再用 O(n) 的列舉法取做查找,效能差蠻多的
以底下的測資來說，我採用前者時是 106ms，採用後者時16 ms...￣▽￣
不過我前者的code沒留下來，所以可能也是我哪裡有沒寫好的地方...XD
另外影響這演算法的地方有兩個...
1.G值的計算, 會直接影響到取點的優先度...
在我的case是以角色為中心的八格損耗都一樣。
在參考文章的範例則是走斜角會加大損耗。
2.cango的地方可以決定哪些點是可以走的
另外 掃點的時候不見得要掃九宮格...
視case不同的情況而定
--
11001100111111110101
01001000001100011001
11010010100111101111
10011100000010100100
10111001011100100101
11101000111111100101
10001101000010000100
11110101010110000100
11101111100010011101
10111000101010011110
11001000011111001101
01101001110100010110
00111100101011111010
10001001110111110011
00001010111010010001
11111101001001101011
10010101111011111010
10111011010110110111
11101001101000011100
00011111001110011111
--
▄▅▆▇███▇▆▅▄▃ ╰┼╯─╮ ╮
◥███████████◣ ╰┼╯＝│=│
◥██████───────◣ ＊． ╯ ╯ ╯ の 物 語 ．＊
◥███████──────◣ ～ ◢◣ ◢◣
◥██████───────◤ ◥◤＊ 空白的世界．翼 ＊◥◤
◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂～telnet://tony1223.no-ip.info
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.27.68
※ 編輯: TonyQ 來自: 220.134.27.68 (05/29 05:32)
討論串 (同標題文章)