J2meGame学习四种寻路算法比较Java认证考试

文章作者 100test 发表时间 2010:01:01 15:43:05
来源 100Test.Com百考试题网

　　四种算法是DFS, BFS, Heuristic DFS, Heuristic BFS (A*)
　　用了两张障碍表，一张是典型的迷宫：
　　char Block[SY][SX] = {
　　{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
　　{1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1},
　　{1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1},
　　{1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
　　{1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1},
　　{1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1},
　　{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
　　{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
　　{1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1},
　　{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
　　}.
　　第二张是删掉一些障碍后的:
　　char Block[SY][SX] = {
　　{1,1,1,1,1,1,1,1,1,1,1 },
　　{1,0,1,0,1,0,0,0,0,0,1 },
　　{1,0,1,0,0,0,1,0,1,1,1 },
　　{1,0,0,0,0,0,1,0,0,0,1 },
　　{1,0,0,1,0,0,1,0,0,1,1 },
　　{1,0,1,0,0,1,0,1,0,0,1 },
　　{1,0,0,0,0,0,0,0,1,0,1 },
　　{1,0,1,0,0,0,1,0,1,0,1 },
　　{1,0,0,1,0,0,1,0,0,0,1 },
　　{1,1,1,1,1,1,1,1,1,1,1 }
　　}.
　　结果：
　　尝试节点数 合法节点数 步数
　　深度优先 416/133 110/43 19/25
　　广度优先 190/188 48/49 19/15
　　深度 启发 283/39 82/22 19/19
　　广度 启发 189/185 48/49 19/15
　　所以可以看出深度 启发是最好的，效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。
　　附：dfs heu的源程序，bc 3.1通过
　　if ((x == TargetX)