【算法&AI】搜索策略
2024-04-22 23:00:44 #AI #算法

引子

搜索，就是通过一定算法对状态空间进行分割，选出所需的解。

1. 搜索算法的形象化描述

抽象为图

形象化搜索问题有助于我们设计相关的算法。举个例子，对于如下的二阶汉诺塔问题：

设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。

我们可以做出如下的抽象：

设定一些状态，用二元组表示，对于任意时刻$k$，任意的二元组$S_k=(S_{k0}, S_{k1})$，$S_{k0},S_{k1}$分别表示A和B所在的钢针号。

接着，我们可以抽象出这样一张图：

从$(1,1)$到$(2,2)$或$(3,3)$的所有路径都是可行解。

抽象为树

这种抽象方法很简单，程序也易于编写，思想是：从起点开始，将所有的可能节点列为子节点。

但是，这种方法会导致抽象出来的结果出现大量重复的结构。

与或树

一个问题，可以被分解为不同的部分，解决所有部分也就解决了该问题；可以被分割成不同的等价的子问题，解决任一子问题，也就相当于解决了该问题。当这两种分割方式同时存在时，就可以使用与或树表示。

与或树里包含着几种节点：

  • 叶子节点
  • 与节点：与节点代表的问题被分割成很多部分。
  • 或节点：或节点代表的问题被分割成很多等价的子问题。

看个例子吧：

img

叶节点用弧表示的，是与节点；不带弧的，是或节点。根节点引出的“2”“3”两个节点就是与节点。

2. 深度优先搜索

若能够将问题抽象为图，便可以应用图论的相关算法，深度优先搜索(DFS)便是其中一个。它可以用来搜索一条从起点到终点的路径。

若想进行深度优先搜索，则需要用到栈。

该算法的思想是，逐条探寻可行路径。

该算法步骤如下：

  1. 从起点开始，沿着任意一条边探索下去。将探索到的点入栈，并将其标记为探索过的点。
  2. 若探索到一个顶点，该顶点还有未被探索过的后继点，则将该后继点入栈，做标记。若该顶点的所有后继点都被探寻过了，则将该点出栈。
  3. 若探索到最后还有没探索到的点，则表明该图非连通图，则选择任意一个未被探索过的点当作起点，回到步骤1。

拿一个问题来说：

洛谷 - P1706 全排列问题

问题摘录如下：

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

C语言代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>

int totalLayer;
int answer[10], used[11];

void dfs(int currentLayer) {
    if(currentLayer == totalLayer) {
        for(int i = 0; i < currentLayer; i++) {
            printf("%5d", answer[i]);
        }
        printf("\n");
    }
    
    for(int i = 0; i < totalLayer; i++) {
        if(used[i+1] == 0) {
            answer[currentLayer] = i+1;
            used[i+1] = 1;
            dfs(currentLayer+1);
            used[i+1] = 0;
        }
    }
}
fen ge
int main(int argc, char **argv) {
    scanf("%d", &totalLayer);
    dfs(0);
    return 0;
}

本题中，将问题抽象为森林，对于三层的情况，两棵树如下：

img

在dfs()函数中，先判断是否为应该输出答案的状态，若非，则一层一层的探寻可行的状态。

3. 广度优先搜索

广度优先搜索(BFS)需要用到队列。

该算法思想是：从起点开始不断扩散，寻找可行解。

该算法步骤为：从起点开始，将所有未探索的后继点加入队列，将起点出队。重复此步骤。

3.5 双向搜索

您也可以从起点、终点同时开始深搜、广搜，能一定程度上降低复杂度。

4. 代价一致搜索

在广度优先搜索的步骤中，我们假定每次拓展都是等代价的，这样我们可以同时拓展未探索的节点。然而在实际生活中，对于不同的节点，扩展的代价往往不同。那么我们先设定拓展节点的代价，接着每次拓展时，都拓展总代价最小的那一个节点。代价可以通过如下的公式计算：

我们假设$g(n_1)$代表从初始节点到$n_1$节点的路径代价，$c(n_1,n_2)$是从$n_1$到$n_2$的代价，那么有：
$$
g(n_2)=g(n_1)+c(n_1,n_2)
$$
举个例子，对于如下的图：

假设A为起点，E为终点，搜索步骤如下：

  1. 先探索A。
  2. 探索C，因为A到C的代价为1，A到B代价为3。
  3. 探索B，因为若探索D，代价为4，探索B代价为3。
  4. 探索D。
  5. 探索E，探索到了终点，程序终止。

该方法探索到的路径一定是代价最小的路径。

5. 贪婪最佳优先搜索

上面所提到的搜索方法都是无信息的搜索方式，即没有任何信息，直接开始搜索。

从该搜索方式开始，都属于有信息的搜索方式。

和代价一致搜索略有区别，该搜索方法的代价为到目标节点的剩余距离。每次扩展，只扩展代价最小的子节点。

同样对于上面这张图，探索步骤如下：

  1. 先探索A。
  2. 探索C。
  3. 探索D。
  4. 探索E。

该方法没法保证最终能够得到路径，假设能得到路径，也没法保证最佳性。

6. A*算法

代价一致搜索考虑的是已经走过的距离，贪婪最佳优先搜索算法考虑的是余下的距离，而A*算法则将这两种算法结合起来。

该算法中，节点$n_1$代价函数为：
$$
f(n_1) = g(n_1)+h(n_1)
$$
其中$f(n_1)$是节点$n_1$的代价函数，$g(n_1)$是起始节点到节点$n_1$走过的距离，$h(n_1)$是节点$n_1$到目标节点的估计代价。

如您所见，估计代价函数是很重要的，设定估计代价函数时，一定要保证估计代价要小于等于实际的代价。过高地估计，有可能会让算法错误地放弃真实的最短路径。

7. 博弈搜索

博弈搜索主要讨论在确定的、全局可观察的、竞争对手轮流行动的对抗搜索两人对决游戏。

极小极大分析法

对于博弈问题，可以生成一个与或树。与节点、或节点交替层级出现。奇数层为己方先手，偶数层为对方先手。此外，我们还有一个代价函数，假定为对你的有利程度。或节点表示己方可选的下法，与节点则表明我需要考虑对方所有可能的落子方法。

利用极小极大分析法，我们需要从叶子节点向上推导，对“或”节点, 选其子节点中一个最大的得分作为父节点的得分；对“与”节点, 选其子节点中一个最小的得分作为父节点的得分。奇数层节点（我方节点）总是会选择赢面最大的子节点状态，而偶数层（对方节点）总是会选择我方赢面最小的的子节点状态。

Alpha-Beta剪枝

极大极小分析法要分析的节点太多了，如果能有一种算法剪去一些枝，则能一定程度上降低复杂度。

偷个懒，引用一下别人的文章，您能在参考资料中找到原文：

(1) 对于一个与节点MIN, 若能估计出其倒推值的上确界β,并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β, 则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。

(2) 对于一个或节点MAX, 若能估计出其倒推值的下确界α, 并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β, 即α≥β,则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。 这一过程称为β剪枝。

所谓MIN节点，就是与节点。

蒙特卡洛树搜索

我们也可以用类似抽样的方法进行搜索。

该方法由四个步骤组成：

  1. 选择
  2. 拓展
  3. 模拟
  4. 反向传播

最开始，我们将需要决策的局面设置为根节点。对于蒙特卡洛搜索树中的每一个节点，都包含着三个信息：

  1. 该节点代表的局面。
  2. 该节点被访问的次数。
  3. 累积评分。

同时，节点可以被分成三类：

  1. 被完全评估过的节点。拿国际象棋举例，也就是对于该节点来说，所有的可能走法都被评估过了。
  2. 未被完全评估的节点。拿国际象棋举例，也就是对于该节点来说，还有一些落子方法没有被评估过。
  3. 结束节点。拿国际象棋举例，也就是对于该节点来说，一方将另一方将死。

在选择阶段，我们从根节点开始，逐步评估子节点，对于上面的三种节点，分别采取不同的策略：

  1. 若节点被完全评估，则计算所有子节点的评分，则将评分最高的子节点设为待评估节点，进行选择操作。
  2. 若节点未被完全评估，则该节点设为待评估节点，进行拓展操作。
  3. 若节点为结束节点，则该节点设为待评估节点，进行反向传播操作。

在拓展阶段，我们在待评估节点的基础上，随机选择一个动作A，在搜索树中创建一个子节点，该子节点表示待评估节点经过动作A所转换得到的局面，接着进行模拟操作。

在模拟阶段，我们在上一步得到的子节点的基础上，随机进行游戏，直到得到一个结束节点，若结束节点代表己方被将死，则视为失败，反之视为成功。接着进行反向传播操作。

在反向传播阶段，从结束节点开始，回溯更新父节点的评分值。

当算法结束时，访问次数越高的节点往往是最佳的选择。

计算评分，常常使用应用到搜索树上的上限置信区间算法UCT，公式如下：
$$
UCT=\frac{w_i}{n_i}+C\sqrt{\frac{lnN_i}{n_i}}
$$
其中$w_i$表示选择$i$节点的胜利次数，$n_i$是$i$节点的模拟次数，$C$是一个平衡系数，$N_i$是全部的模拟次数。该公式的形式，来自正态分布的置信区间的计算公式，您可以在参考资料中查看相关的资料。

参考资料

OI Wiki

博弈树搜索

【最佳实战】蒙特卡洛树搜索算法

强化学习(十八) 基于模拟的搜索与蒙特卡罗树搜索(MCTS)

怎样全面理解95%置信区间

Prev
2024-04-22 23:00:44 #AI #算法
Next