|
引用 | 编辑
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
|
|
