DFS,BFS,ID,IDA*,A*搜索算法简介

发布于 2022-09-08  298 次阅读


前言

搜索一般分为盲目搜索和启发式搜索

下面列举以下OI常用的盲目搜索:

  1. 迪杰斯特拉
  2. SPFA
  3. BFS
  4. DFS
  5. 双向BFS
  6. 迭代加深搜索(ID)

下面列举以下OI常用的启发式搜索:

  1. 最佳优先搜索(A)
  2. A*
  3. IDA (ID + A ??? (大雾) )

什么?? 我用了这么多年的bfs是盲目是搜索!!!

举个例子,假如你在学校操场,老师叫你去国旗那集合,你会怎么走?
假设你是瞎子,你看不到周围,那如果你运气差,那你可能需要把整个操场走完才能找到国旗。这便是盲目式搜索,即使知道目标地点,你可能也要走完整个地图。
假设你眼睛没问题,你看得到国旗,那我们只需要向着国旗的方向走就行了,我们不会傻到往国旗相反反向走,那没有意义。
这种有目的的走法,便被称为启发式的。

给个图您就明白了

左图是广搜 右图是最佳优先搜索(A):

下图是A* 搜索:

动画展示各种路径搜索算法

搜索算法浅谈

关于DFS

这东西应该是妇孺皆知,不知道的话您就可以退役了.

优点

我就不多讲了,说一下她的优点:

  1. 代码简洁易于编写
  2. 可以方便的加一些剪枝

缺点

  1. 浪费时间,要用剪枝来优化

为什么浪费时间呢?

看个图你就明白了:

不要随便加剪枝,有些剪枝用处很小,不会节约太多时间,但是你的程序将会对她进行无数次特判,这个代价可比你剪枝节约的时间高多了

代码大体框架:

void dfs(状态A)
{
    if(A不合法)
        return;
    if(A为目标状态)
        输出或记录路径
    if(A不为目标状态)
        dfs(A+Δ ) 
 } 

关于BFS

这东西也应该是妇孺皆知,不知道的话您就又可以退役了.

bfs适合目标明确的情况,是典型的空间换时间的算法.

优点

我就不多讲了,说一下他的优点 (又是这句话(大雾

  1. 一般比dfs快
  2. 难写(有些人就爱写BFS)

缺点

  1. 难写
  2. 十分占空间

代码大体框架:

q.push(head);
while(!q.empty())
{
    temp=q.front();
    q.pop();
    if(tempÎ为目标状态)
        输出或记录
    if(temp不合法 )
        continue;
    if(temp合法)
        q.push(temp+¦Δ ); 
}

关于迭代加深搜索(ID)与IDA*

蓦然回首,再去看一眼上图:

我们发现如果现在的路的深度没有上限,即没有底,那么直接DFS就回不来了,但终点就在第二层,怎么办?

我们设一个深度d每次搜到d层就回头去搜别的分支,如果没搜到就让d++,再从头搜一次.这种算法思想上相当于是DFS+BFS的合体,但是缺点很明显,重复遍历解答树上层多次,造成巨大浪费。

于是我们伟大的前辈们开动脑筋,发明了 IDA_star.

IDA star多了评估函数(或者说剪枝),每次预估如果这条路如果继续下去也无法到达终点,则放弃这条路(剪枝的一种,即最优性剪枝)。IDA star原理实现起来简单,非常方便,但难的地方是评估函数的编写,足够好的评估函数可以避免走更多的不归路,如果评估函数太差或者没有评估函数,那会退化到迭代加深搜索那种浪费程度。

评估函数f = g + h

g是已经走的

h是估计代价

代码大致如下


//1代表墙,0代表空地,2代表终点
int G[maxn][maxn];
int n, m;

int endx, endy;
int maxd;

const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, -1, 1 };

namespace ida
{
    bool dfs(int x, int y, int d);
    inline int h(int x, int y);

    bool ida_star(int x, int y, int d)
    {
        if (d == maxd)                   //是否搜到答案
        {
            if (G[x][y] == 2)
                return true;
            return false;
        }

        int f = h(x, y) + d;          //评估函数
        if (f > maxd)                //maxd为最大深度
            return false;

    //尝试向左,向右,向上,向下走

        for (int i = 0; i < 4; i++)
        {
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if (next_x > n || next_x < 1 || next_y > m || next_y < 1 || G[next_x][next_y] == 1)
                continue;

            if (ida_star(next_x, next_y, d + 1))
                return true;
        }
        return false;
    }

    inline int h(int x, int y)
    {
        return abs(x - endx) + abs(y - endy);
    }
}

调用:

    //枚举步数,最少多少步能到达目标 
    for(maxd = 1; ;maxd++)
        if(dfs(0, 0, 0))
        {
            cout << maxd << endl; 
            break;
        }

迭代加深&&IDA_star只适用于有解的情况

关于A*

还是那个例子,假如现在是周一早上7:30分,全体师生要到国旗台前集合.

如果你是bfs(大雾,你会到处搜索,甚至南辕北辙。

人类会怎么走呢,人类的做法是向着国旗台的方向走,假如那个人和国旗台之间没有障碍物,那么这条路径的距离我们也很好计算,只需使用两点间距离公式(欧几里得距离)计算便可。

$$ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} $$

我们可以用这个公式求得的距离给搜索到的点附一个权值,每次优先走距离最小的。这个算法的大体思路就是这样。其实这个算法是一种启发式搜索,学名叫A算法。下面研究的就是A算法的优化——A*算法。

本质上就是一个BFS的优化

A*搜索算法在实际执行过程中,会去选择一个最小的启发式函数f(x)去处理。

函数定义如下

$$ f(x)=g(x)+h(x) $$

上面的g(x)表示从初始状态转移到目标状态x需要的最小代价,在静态路网的最短路径中可以认为是开始位置到位置x的最短路径。而h(x)则是A启发式搜索的估价函数,可以说,估价函数h(x)的选择决定了A算法的运行速度,它表示从当前状态转移到最终状态预计的最小代价,它是人为估计的,在静态路网的最短路径搜索中,可以使用两点间距离公式(欧几里得距离)作为估价函数进行计算。

因此,对于每一个格子,可以建立一个结构体来进行存储,结构体的定义如下:

struct node
{
    int x, y g ,h;
    node(int _x, int _y, int _g) //构造函数
    {
        x = _x;
        y = _y;
        g = _g;
        h = sqrt(pow(finalx - x, 2) + (finaly - y, 2));
    }
}

下面用一个例子来说明A*算法:
假如我们有一张如下图所示静态路网,求从红色的点走道绿色的点的最短路径。(灰色的格子为障碍)

那么,假如忽略障碍的话,绿色格子到红色格子的最短路线就是它们的直线距离。由于该算法的特点,程序进行搜索路径的时候会优先沿着它们两点间的连线的方向寻找。

首先程序会从绿色的点开始搜索,然后扩展它周围的节点,把它们的估价函数分别进行计算。并把它们存到一个优先级队列中。

程序找到了这个点(黄色):

它的估价函数f为3。程序想继续向前走,但没有路了,于是程序放弃了这个点,从优先级队列中删掉了它,转而使用优先级队列中另外两个估价函数最小的点,如图所示。

为了方便起见,这里只讨论上方的决定最终答案的点。

接着,程序开始搜索上方于黄点相连接的周围的点的估价函数的值,并把它们存在优先级队列中。程序找到了这个估价函数最小的点(黄色),如下图。

后面的运行步骤和上面一致,这里不再赘述了。程序最终找到的路径如下图所示。

A*的核心代码大致如下:

while(!q.empty())
{
    node u = q.top();
    q.pop();
    if(u.x = finalx and u.y = finaly.y) // 目标状态
    {
        cout << u.g << endl; // 输出步数
        return 0;
    }
    for(int i = 0; i < 8; i++) // 上下左右走
    {
        int nx = u.x + dx[i], ny = u.y + dy[i];
        if(nx < 1 or ny < 1 or nx > n or ny > n or a[nx][ny] == 1) // 判断边界及墙壁
            continue;
        if(!vis[nx][ny]) // 查找当前状态是否被遍历过
        {
            vis[nx][ny] = 1; // 标记
            q.push(node(nx, ny, u.g + 1)); // 扔到priority_queue中
        }
    }
}

参考资料:

对于DFS,BFS,A与IDA*等寻路算法的总结跟感悟