不好意思~想請問大大們
我這有道問題是問說老鼠走迷宮是用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 ..

訪客只能看到部份內容，免費 加入會員 或由臉書 Google 可以看到全部內容

我不是很懂= =

也是第一次看

不過因該會有人會跟你說怎用的^^

那是程式碼嗎??

BFS(廣度優先搜尋)
DFS(深度優先搜尋)
是否可請教大大
以上兩項是什麼意思
因為c++小弟還沒讀
所以還是一頭霧水
謝謝

下面是引用 csr 於 2011-07-20 16:59 發表的 :
BFS(廣度優先搜尋)
DFS(深度優先搜尋)
是否可請教大大
以上兩項是什麼意思
因為c++小弟還沒讀
所以還是一頭霧水
謝謝

我自己也不太懂，我去查了一下資料

大概了解一點，這就是演算法的選擇，好的演算法能有較高的效率、較好的結果


例如 CS 的 BOT(虛擬電腦機器人)，在不同地圖時會 自動演算最近的距離一樣 (要救人質、拆炸彈)，而產生 nav 檔案

我看大部分都是用 A* 演算法，不過效率佳不一定有好的結果

CS 的 BOT 在 3D 垂直部分作的非常不好，例如 cs_italy 救人質地圖中，從1樓往2樓的樓梯

演算法為了選最近距離，會讓 BOT 卡在百貨公司 小心夾頭 的那個地方，但這在 CS:S 就被重新考慮而做的比較好

所以演算法是一個好的程式的中樞呢

---

參考維基百科：

BFS 廣度搜索

DFS 深度優先搜索


參考知識+  (這個說得很清楚，我一下就瞭解了)：

深度優先搜尋與廣度優先搜尋？


而這個網站有介紹 A* 的運算法：

http://blog.minstrel.idv.tw/20...gorithm.html



而這是我用流程圖做的展示 (Tool by http://cac...com)：


BFS :







DFS :

---

在 老鼠走迷宮的情況下，想到用 DFS 很正常

不過用 BFS 又是怎麼回事? 老鼠可以瞬間移動?

還有在上層的節點中，沒有走完下面又為什麼要 在同層的節點中尋找呢


還是說，老鼠已經知道迷宮長怎麼樣，卻不知道最快的走法

所以要來演算?

那麼到底哪個比較好應該要用數學來證明了

維基百科中有出現 空間複雜度、時間複雜度 的東西，應該與那個相關，我看不懂


在不同的節點環境下，兩個演算法都會有各自時間跑最快的狀況

如果分支的層數一樣的話，看起來 DFS 會比較快

如果層數很多，分支不廣，看起來 BFS 會比較快

下面是引用 ebolaman 於 2011-07-20 18:53 發表的 :


我自己也不太懂，我去查了一下資料
大概了解一點，這就是演算法的選擇，好的演算法能有較高的效率、較好的結果

.......

原來它是使用資料結購地二元樹結點的搜尋
大概知道它的來源
以後看程式就會比較清楚些
感謝大大一再為小弟解惑
只能跟您說聲
謝謝

根本看不董