寒假做的最短路徑搜尋程式[補充]
這個東西已經沒用了 分享一下
[BCB5] 是 A-Star 的 BCB 版
本來要拿出來比賽的版本 一開始執行要輸入一個評估值
根據 A-Star 的想法 評估值越大 搜尋速度會越快
但是找出來的並不是最短路徑 用我下面那個 tool 看他的路徑就知道了
如果 maze 每個點都在 1~255 的話 評估值設定 255 它是跑斜線的
所以他定義 每次計算評估成本 一定要比實際成本小
否則就不叫做 A-Star 只是一個普通的寬度搜尋
至於那個評估值要設多少 就不一定了 我在測試都是用 50
[vc] 是 A-Star 的 VC++6版本
在網路上看說用 MS VC++6 配 Intel 的 C++ Compiler
做出來的執行檔跑起來會很快 把它取名為 mazda 是因為我對它賦予重望
結果經過測試是沒什麼感覺啦 甚至是比 BCB or GCC 慢
我在想也有可能是我的 CPU 是 C 開頭的不是 P 開頭的
[gcc] 是 GNU C 版
這個版本除了要測試 BCB 跟 GNU C 的速度差別
另一方面我把它的評估值拿掉了 所以他是完全的廣度搜尋
感覺起來因為不用算評估成本 所以速度有變快
但是學到演算法 BigO 之後知道 我在猜他在迷宮大到一個程度之後
就會比 A-Star 慢 不過實際是要多大還沒測試過
也許可以算的出來 但是目前還不會
至於執行速度 測試如果也有算評估成本其實也是沒什麼差
應該是大家的 Compiler 都已經優化到一個瓶頸了吧
[tool] 是迷宮產生器跟搜尋路徑繪製
簡單的說前面那個程式可以把所有走過的路徑存在一個 maze.txt
然後用這個 tool 把這些點在螢幕上畫出來看他是怎麼跑