ArchiverateZ

Appearance

搜索和遍历 ​

基本概念 ​

关于搜索和遍历 ​

  • 搜索是一种通过系统地检查给定数据对象的每个节点，寻找一条从开始节点到目标节点的路径的过程。

  • 遍历则要求按照某种规则，依次访问数据对象中的每一个节点，而且每个节点仅访问一次。

  • 状态空间：搜索和遍历的对象是一个状态空间，状态空间是一个有限的状态集合，每一种情况对应一个状态。

  • 初始状态：搜索和遍历的起始状态。

  • 目标状态（答案状态）：一个或多个满足特定条件的状态。

关于搜索方法 ​

  • 无知搜索（盲目搜索、穷举搜索）：无知搜索(Uninformed Search)是指在搜索过程中，不考虑任何启发信息，只是简单地对状态空间进行搜索。DFS和BFS是最常见的无知搜索算法。

  • 有知搜索（启发式搜索）：有知搜索(Informed Search)是指在搜索过程中，利用启发信息来指导搜索方向，以期望更快地找到目标状态。启发式是一种提高搜索效率的方法。它一边搜索，一边评估达到目标状态的剩余距离，这种评估依赖于已有的关于问题领域的知识和经验规则。但是，启发式搜索并不保证找到最优解，只是找到一个较好的解。A*搜索算法是最常见的有知搜索算法。

  • 著名的搜索算法：深度优先搜索(DFS)、广度优先搜索(BFS)、A*搜索算法(A* Search)、IDA*搜索算法(IDA* Search)、Dijkstra算法、Bellman-Ford算法、Floyd算法等。

无知搜索 ​

概念 ​

  • 无知搜索(Uninformed Search)，又叫盲目搜索、穷举搜索，是指在搜索过程中，不考虑任何启发信息，只是简单地对状态空间进行搜索。
  • 无知搜索因为不涉及启发信息，所以在代码实现上较为简单；但是，正因为如此，无知搜索的时空复杂度均较高，搜索效率较低。可以考虑加入剪枝等优化策略来提高搜索效率。
  • 广度优先搜索(Breadth First Search)、深度优先搜索(Depth First Search)、双向搜索(Bidirectional Search)、迭代加深搜索(Iterative Deepening Search)等搜索算法都属于无知搜索。
  • 节点状态：
    • 未访问(Not Visited)：节点未被访问，称作未访问状态；
    • 未检测(Unexplored)：节点自身已被访问，但其后继节点未被访问；（也可以称作活结点）
    • 已检测(Discovered)：节点自身已被访问，且其后继节点已被访问；（也可以称作死结点）
    • 扩展节点（简称E-节点）：当算法正要从节点u出发，欲访问节点v时，节点u称为扩展节点；在算法的任意时刻，只有一个节点是扩展节点。
  • DFS和BFS选择E-节点的规则不同：
    • BFS：对于一个未检测的节点，广度优先搜索在访问它的全部的后继节点之后（即使得该节点成为已检测节点后），才另选一个未检测节点作为扩展节点，并进行检测。
    • DFS：对于一个未检测的节点，深度优先搜索访问该节点并使该节点变为未检测的节点后，立即被算法检测，成为一个E-节点，而此时，原先的E-节点还未检测完毕，仍处于未检测状态，需要在以后的适当时候再次被检测。
    • D-搜索：用BFS方式选择E-节点，并使用活结点表来储存活结点。

深度优先搜索(DFS) ​

概念 ​

  • 深度优先搜索是一种无知搜索算法，其基本思想是：沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

  • 其实称为“远度优先搜索”更容易理解些。因为这种策略能往前走一步就往前走一步，总是试图走得更远。所谓远近（或深度），就是以距离起点的步数来衡量的。

  • DFS适合此类题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。

代码实现 ​

  • 伪代码：
text
bool check(参数)
{
    if(满足条件) return true ;
    return false;
}
  
void dfs(int step)
{
    if(边界条件) 执行相应操作;
    for(枚举所有可能的下一步){
        if(check()){
            visit();//访问节点
            dfs(step+1);
            reset();//恢复初始状态，回溯
        }
    }
}
  • Java
java
public class DFS {
    public void dfs(int step) {
        if (step == n) {
            // 达到边界条件，执行相应操作
            return;
        }
        for (int i = 0; i < n; i++) {
            if (check(i)) {
                visit(i);
                dfs(step + 1);
                reset(i);
            }
        }
    }
}

DFS可以使用“栈”(Stack)来实现。

时间复杂度 ​

  • 对于一棵深度为h的m叉树来说，其时间复杂度为O(mh)。如果节点总数为n，则为O(n)。

Considering worst case:

Worst Case=1+m+m2+⋯+mh−1=mh−1m−1
  • The complexity is O(n+m) where n is the number of nodes in your tree, and m is the number of edges.

特点 ​

  • DFS的优点：可以更深入地探索图的细节，有助于找到更多的解决方案。
  • DFS的缺点：相对于BFS，空间复杂度较高，可能导致内存不足。

广度优先搜索(BFS) ​

  • 广度优先搜索是一种无知搜索算法，其基本思想是：从起始节点开始，沿着树的宽度遍历树的节点。如果所有节点都被访问，则算法终止。因为其使用队列来存储活结点，所以被称为LIFO搜索。

  • BFS适合此类题目：给定初始状态跟目标状态，要求找出最短路径。

代码实现 ​

java
public class BFS {
    public void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i = 0; i < n; i++) {
                if (check(i)) {
                    visit(i);
                    queue.offer(i);
                }
            }
        }
    }
}

BFS可以使用“队列”(Queue)来实现。

时间复杂度 ​

  • BFS搜索图的时间复杂度为O(n+m)，其中n是节点数，m是边数。
  • 特别地，如果使用邻接矩阵来表示图，时间复杂度为O(n2)。

定义 ​

  • 双向搜索是一种无知搜索算法，其基本思想是：从起始节点和目标节点同时开始搜索，当两个搜索方向相遇时，搜索结束，认为已经获得了可行解。这里，可以同时j使用BFS或DFS进行搜索。

过程 ​

将开始结点和目标结点加入队列 q
标记开始结点为 1
标记目标结点为 2
while (队列 q 不为空)
{
  从 q.front() 扩展出新的 s 个结点

  如果 新扩展出的结点已经被其他数字标记过
    那么 表示搜索的两端碰撞
    那么 循环结束

  如果 新的 s 个结点是从开始结点扩展来的
    那么 将这个 s 个结点标记为 1 并且入队 q 

  如果 新的 s 个结点是从目标结点扩展来的
    那么 将这个 s 个结点标记为 2 并且入队 q
}

特殊的算法：Meet in the Middle ​

  • Meet in the middle 算法没有正式译名，常见的翻译为「折半搜索」、「双向搜索」或「中途相遇」。

  • 它适用于输入数据较小，但还没小到能直接使用暴力搜索的情况。

  • Meet in the middle 算法的基本思想是：将问题分成两部分，分别在两部分中搜索，然后将两部分的结果合并。

  • 性质：可以降低数据规模较小的问题的时间复杂度。（复杂度可以从O(ab)降低至O(ab/2)）。

  • 应用：

    例题：

    有n盏灯，每盏灯与若干盏灯相连，每盏灯上都有一个开关，如果按下一盏灯上的开关，这盏灯以及与之相连的所有灯的开关状态都会改变。一开始所有灯都是关着的，你需要将所有灯打开，求最小的按开关次数。其中，1≤n≤35。

    思路：

    如果这道题暴力 DFS 找开关灯的状态，时间复杂度就是O(2n), 显然超时。不过，如果我们用 meet in middle 的话，时间复杂度可以优化至O(n2n/2)。meet in middle 就是让我们先找一半的状态，也就是找出只使用编号为 1 到 mid 的开关能够到达的状态，再找出只使用另一半开关能到达的状态。如果前半段和后半段开启的灯互补，将这两段合并起来就得到了一种将所有灯打开的方案。具体实现时，可以把前半段的状态以及达到每种状态的最少按开关次数存储在 map 里面，搜索后半段时，每搜出一种方案，就把它与互补的第一段方案合并来更新答案。

    代码实现：

    cpp
    #include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>

using namespace std;

int n, m, ans = 0x7fffffff;
map<long long, int> f;
long long a[40];

int main() {
  cin >> n >> m;
  a[0] = 1;
  for (int i = 1; i < n; ++i) a[i] = a[i - 1] * 2;  // 进行预处理

  for (int i = 1; i <= m; ++i) {  // 对输入的边的情况进行处理
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    a[u] |= ((long long)1 << v);
    a[v] |= ((long long)1 << u);
  }

  for (int i = 0; i < (1 << (n / 2)); ++i) {  // 对前一半进行搜索
    long long t = 0;
    int cnt = 0;
    for (int j = 0; j < n / 2; ++j) {
      if ((i >> j) & 1) {
        t ^= a[j];
        ++cnt;
      }
    }
    if (!f.count(t))
      f[t] = cnt;
    else
      f[t] = min(f[t], cnt);
  }

  for (int i = 0; i < (1 << (n - n / 2)); ++i) {  // 对后一半进行搜索
    long long t = 0;
    int cnt = 0;
    for (int j = 0; j < (n - n / 2); ++j) {
      if ((i >> j) & 1) {
        t ^= a[n / 2 + j];
        ++cnt;
      }
    }
    if (f.count((((long long)1 << n) - 1) ^ t))
      ans = min(ans, cnt + f[(((long long)1 << n) - 1) ^ t]);
  }

  cout << ans;

  return 0;
}

启发式搜索 ​

概括 ​

  • 启发式搜索（英文：heuristic search）是一种在普通搜索算法的基础上引入了启发式函数的搜索算法。

  • 启发式函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。

  • 具体应用：

    **例题：**采药（NOIP2005普及组）：有 N 种物品和一个容量为 W 的背包，每种物品有重量 wi 和价值 vi 两种属性，要求选若干个物品（每种物品只能选一次）放入背包，使背包中物品的总价值最大，且背包中物品的总重量不超过背包的容量。

    **思路：**我们在取的时候判断一下是不是超过了规定体积（可行性剪枝）；在不取的时候判断一下不取这个时，剩下的药所有的价值 + 现有的价值是否大于目前找到的最优解（最优性剪枝）。

    代码：按照思路来写，或者把0-1背包的DP算法的代码转换成搜索算法。

A*算法 ​

  • A*算法（A-star Search Algorithm）,