不好意思~想请问大大们
我这有道问题是问说老鼠走迷宫是用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 发表的 :


我自己也不太懂，我去查了一下资料
大概了解一点，这就是演算法的选择，好的演算法能有较高的效率、较好的结果

.......

原来它是使用资料结购地二元树结点的搜寻
大概知道它的来源
以后看程式就会比较清楚些
感谢大大一再为小弟解惑
只能跟您说声
谢谢

根本看不董