搜索算法

• 搜索算法
  • 1. 搜索简介
    • 1.1 DFS深度优先算法
    • 1.2 BFS广度优先算法
  • 2. 搜索实现
  • 3. 搜索剪枝
  • 4. 搜索与动态规划
  • 5. 搜索例题
  • 6. 搜索的高级技巧

1. 搜索简介

1.1 DFS深度优先算法

DFS定义：使用系统栈维护，爆栈跳楼， 一条路走到黑，一直到这条路不能走了，我们才回溯，然后走下一条路。

也有些是使用A*算法的，这个特殊说明，请看第三节。

// DFS基本实现框架

void DFS(int dep)
{
    if (终止条件)
    {
        终止操作
        return ;
    }
    for (遍历所有情况)
    {
        if (没有标记过)
        {
            标记;
            记录路径和其他操作;
            DFS(dep + 1);
            撤销标记，回溯;
        }
    }
}

优点：好写，简单。某些DP题不用推公式，直接打。

缺点：容易爆栈爆空间，效率低下。

1.2 BFS广度优先算法

BFS定义：将一个点可以走到的所有的点用一个队列维护起来，每一次执行对头操作，插入到队尾。

也有一些题是使用双端队列BFS，或者IDA*算法实现的，这个请看第三节。

// BFS基本实现框架

void BFS()
{
    queue <typename> q;
    q.push(初始条件);
    标记;
    while (! q.empty())
    {
        auto f = 对首元素;
        出队;
        for (遍历相邻的点)
            if (没标记)
            {
                标记;
                入队;
                if (终止条件)
                {
                    终止操作;
                    return ;
                }
            }
    }
}

优点：跑得快（相对于DFS来说）。

缺点：难写，难剪枝。

总之，上述的两个搜索算法都是骗分算法。

2. 搜索实现

3. 搜索剪枝

(待补)

4. 搜索与动态规划

(待补)

5. 搜索例题

6. 搜索的高级技巧

(待补)