| 对于DFS，BFS，A*与IDA*等寻路算法的总结跟感悟 | 您所在的位置：网站首页 › 迷路径路优缺点 › 对于DFS，BFS，A*与IDA*等寻路算法的总结跟感悟 |
对于DFS，BFS，A*与IDA*等寻路算法的总结跟感悟
|
一周前看见了贪吃蛇AI算法，受到震撼于是就把以前的win32贪吃蛇加了个AI实现，让我这个渣渣写了好几天才完工 不说了，进入正题吧，常见的搜索有深度优先搜索，广度优先搜索，迭代加深搜索，双向广度优先先搜索，A*搜索，IDA*搜索等，这些搜索分为盲目式搜索跟启发式搜索。 何为盲目？何为启发？ 举个例子，加入你在学校操场，老师叫你去国旗那集合，你会怎么走？
假设你是瞎子，你看不到周围，那如果你运气差，那你可能需要把整个操场走完才能找到国旗。这便是盲目式搜索，即使知道目标地点，你可能也要走完整个地图。 假设你眼睛没问题，你看得到国旗，那我们只需要向着国旗的方向走就行了，我们不会傻到往国旗相反反向走，那没有意义。 这种有目的的走法，便被称为启发式的。 而今天要提到的深度优先跟广度优先，便是盲目式搜索，而A*跟IDA*，便是启发式搜索。 盲目式搜索
BFS
广度优先（BFS）是，每次先搜索周围，先把原点方圆1m找完，如果找不到，就找再向外扩展1m，如果找不到，就再向外扩展1m，每次扩大自己的圈子，直到整个地图走完。很像传染病，从开始一个点慢慢传染到整个地区 BFS则是用队列实现跟循环实现，每次把当前节点周围的节点加入队列，然后pop出队列，不断循环，直到队列为空。一种用递归一种用循环，很明显，在时间上，深度优先搜索一般要比广度优先搜索慢，但广度优先搜索需要大量的空间。所以说这两种算法各有优缺点。 在说启发式搜索之前，先说说寻路算法
寻路算法
一般要到终点，我们会关注两件事，要走多远以及这条路要怎么走。然后为了不重复走过的路，我们还需要标记这条路已经走过，即判重。 走多远，即是最少步数。如果用DFS来说，即是深度，用BFS来说，便是向外扩展了多少米（其实也是深度）。 那怎么记录路径呢？办法是每个节点加个指向前一个节点的指针，每一步记录前一步，便能记录整条路径。DFS不用说，就是解答树的一个分支，而BFS则是会形成一颗BFS树 但是这样得出来的路径是从终点到起点的路径，这里便需要从终点开始用递归打印出来，便能打印起点到终点的路径。
判重的方法可以用bool数组，然后true表示走过节点，false表示没走过的节点，如果是比较复杂的状态等，其他判重的方法如hash（快速查找O(1)），红黑树（查找较快）等比较复杂的数据结构。C++红黑树直接用set或者map就是了，一般不会为了写个搜索亲自去写麻烦的数据结构的（当然hash还是可以的） 因此BFS缺点是非常浪费空间。经典的以空间换时间的算法。下面给出 #include #include using namespace std; const int maxn = 100; const int inf = 0x3fffffff; //1代表墙，0代表空地，2代表终点 int G[maxn][maxn]; //此数组记录到此节点的最小步数，类似dp。同时用来判重 int book[maxn][maxn]; int n, m; struct Node { int x; int y; Node(int x, int y):x(x), y(y){} }; //移动时的坐标改变量 const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; //bfs寻找最短路径，不存在返回-1 int bfs(int sx, int sy) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { book[i][j] = inf; } } book[sx][sy] = 0; queue q; Node temp(sx, sy); q.push(temp); while(!q.empty()) { Node u = q.front(); q.pop(); int x = u.x; int y = u.y; //尝试向左，向右,向上，向下走 for(int k = 0; k < 4; k++) { int next_x = x + dx[k]; int next_y = y + dy[k]; //不能越界，也不能往障碍走 if(next_x >= n || next_x < 0 || next_y >= m || next_y < 0 || G[next_x][next_y] == 1) continue; //如果可以走，看是否之前走过 if(book[next_x][next_y] == inf) { //从此点继续扩展 Node temp(next_x, next_y); q.push(temp); //更新步数,其实这个可以不用，因为，bfs原本就是从近到远，上次一定不比这次远，为了跟上面保持一致而进行 book[next_x][next_y] = book[x][y] + 1; } else { //更新步数 book[next_x][next_y] = min(book[next_x][next_y], book[x][y] + 1); } if(G[next_x][next_y] == 2) { return book[next_x][next_y]; } } } return -1; } int main() { cin >> n >> m; cout > m; cout > m; cout |
，终于能吃完全屏了，虽然离自己看的那个贪吃蛇AI的gif还有些距离emmmm，贪吃蛇AI不可避免的用到了寻路算法，所以今天当做复习总结提一提，
【本文地址】