|
引用 | 編輯
guilty0225
2010-12-30 17:44 |
樓主
▼ |
||
x0
我這有道問題是問說老鼠走迷宮是用BFS(廣度優先搜尋)還是DFS(深度優先搜尋)哪個比較好 要怎麼用程式證明? 以下是我所知的BSF程式 DFS大大們會怎寫? #include <cstdio> #include <list> #define SIZE 10 using namespace std; int ex=9,ey=9; typedef struct _node{ int x; int y; int step; }NODE; int maze={ {0,0,0,0,0,1,1,1,1,1}, {1,0,1,1,1,1,0,0,0,1}, {1,0,0,0,1,1,0,1,1,1}, {1,0,1,0,0,0,0,0,0,1}, {1,0,1,0,1,1,0,1,0,1}, {1,0,1,0,1,1,1,1,0,1}, {1,0,1,0,1,1,0,0,0,1}, {1,1,1,0,0,0,0,1,0,1}, {1,0,0,0,1,1,1,1,0 .. 訪客只能看到部份內容，免費 加入會員  x0
|
|||
|
引用 | 編輯
ebolaman
2011-07-20 18:53 |
3樓
▲ ▼ |
下面是引用 csr 於 2011-07-20 16:59 發表的 : 我自己也不太懂，我去查了一下資料 大概了解一點，這就是演算法的選擇，好的演算法能有較高的效率、較好的結果 例如 CS 的 BOT(虛擬電腦機器人)，在不同地圖時會 自動演算最近的距離一樣 (要救人質、拆炸彈)，而產生 nav 檔案 我看大部分都是用 A* 演算法，不過效率佳不一定有好的結果 CS 的 BOT 在 3D 垂直部分作的非常不好，例如 cs_italy 救人質地圖中，從1樓往2樓的樓梯 演算法為了選最近距離，會讓 BOT 卡在百貨公司 小心夾頭 的那個地方，但這在 CS:S 就被重新考慮而做的比較好 所以演算法是一個好的程式的中樞呢 參考維基百科： BFS 廣度搜索 DFS 深度優先搜索 參考知識+ (這個說得很清楚，我一下就瞭解了)： 深度優先搜尋與廣度優先搜尋？ 而這個網站有介紹 A* 的運算法： http://blog.minstrel.idv.tw/2004/12/star-algorithm.html 而這是我用流程圖做的展示 (Tool by http://cacoo.com)： BFS :  DFS :  在 老鼠走迷宮的情況下，想到用 DFS 很正常 不過用 BFS 又是怎麼回事? 老鼠可以瞬間移動? 還有在上層的節點中，沒有走完下面又為什麼要 在同層的節點中尋找呢 還是說，老鼠已經知道迷宮長怎麼樣，卻不知道最快的走法 所以要來演算? 那麼到底哪個比較好應該要用數學來證明了 維基百科中有出現 空間複雜度、時間複雜度 的東西，應該與那個相關，我看不懂 在不同的節點環境下，兩個演算法都會有各自時間跑最快的狀況 如果分支的層數一樣的話，看起來 DFS 會比較快 如果層數很多，分支不廣，看起來 BFS 會比較快 x1
|
|
