人工智能复习（四）

四、搜索策略

1. 搜索的基本概念

2. 状态空间的搜索

2.1 盲目搜索

  • 广度优先
  • 深度优先
  • 代价一致

关于上述几种搜索，在另一篇文章中有对比说明：https://www.awellfrog.cc/p/401ea1e.html

2.2 代价树搜索

  • 代价树的深度优先搜索

    从open表中选择刚扩展的子节点中代价最小的节点

  • 代价树的广度优先搜索

    从open表中选择全体节点中代价最小的节点

2.3 启发式搜索（重点）

A算法

在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法又称为启发式搜索算法（英文：heuristic search）。

对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。

  • 全局择优搜索中，每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。
  • 局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。
A* 算法

A没有对估价函数 f(n)f(n) 做任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。

假设 f∗(n)f^*(n) 为从初始节点 S0S_0 出发，约束经过节点 n 到达目标节点的最小代价值。估价函数 f(n)f(n) 则是 f∗(n)f^*(n) 的估计值。

f∗(n)f^*(n) 应由以下两部分所组成：

  • 一部分是从初始节点 S0S_0 到节点n的最小代价，记为 g∗(n)g^*(n)
  • 另一部分是从节点n到目标节点的最小代价，记为 h∗(n)h^*(n) ，当问题有多个目标节点时，应选取其中代价最小的一个

因此有 f∗(n)=g∗(n)+h∗(n)f^*(n)=g^*(n) +h^*(n)
把估价函数 f(n)f(n) 与 f∗(n)f^*(n) 相比

  • g(n)g(n) 是对 g∗(n)g^*(n) 的一个估计
  • h(n)h(n) 是对 h∗(n)h^*(n) 的一个估计

在这两个估计中，尽管 g(n)g(n) 的值容易计算，但它不一定就是从初始节点 S0S_0 到节点 n 的真正最小代价，很有可能从初始节点 S0S_0 到节点 n 的真正最小代价还没有找到，故有

g(n)≥g∗(n)g(n) \geq g^*(n)

有了 g∗(n)g^*(n) 和 h∗(n)h^*(n) 的定义，如果我们对A算法（全局择优的启发式搜索算法）中的 g(n)g(n) 和 h(n)h(n) 分别提出如下限制：

  • g(n)g(n) 是对 g∗(n)g^*(n) 的估计，且 g(n)>0g(n)>0
  • h(n)h(n) 是对 h∗(n)h^*(n) 的下界，即对任意节点n均有

0<h(n)≤h∗(n)0 < h(n) \leq h^*(n)

则称得到的算法为A*算法。

1. A*算法的可纳性

一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。

2. A*算法的最优性

A*算法的搜索效率很大程度上取决于估价函数 h(n)h(n) 。一般说来，在满足 h(n)≤h∗(n)h(n)≤h^*(n) 的前提下，h(n)h(n)的值越大越好。h(n)h(n) 的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索的效率就越高。

3. h(n)的单调限制

如果启发函数满足以下两个条件：

  • 1） h(Sg)=0h(S_g)=0；
  • 2） 对任意节点 nin_i 及其任意子节点 njn_j ，都有 0≤h(ni)−h(nj)≤c(ni,nj)0 \leq h(n_i) - h(n_j) \leq c(n_i, n_j)

其中 c(ni,nj)c(n_i,n_j)是节点 nin_i 到其子节点 njn_j 的边代价，则称 h(n)h(n) 满足单调限制

如果h满足单调条件，则当A*算法扩展节点n时，该节点就找到了通往它的最佳路径，即

g(n)=g∗(n)g(n) = g^*(n)

例题1

有一包含启发信息的路径搜索算法，其估价函数 f(n)=(2−w)∗g(n)+w∗h(n)f(n) = (2-w)*g(n) + w*h(n)，在此问题中已知 h(n)h(n) 是可纳的。请回答下列问题：

(1). w取什么值时该算法是代价一致搜索算法？为什么？

(2). w取什么值时该算法是贪心搜索算法？为什么？

(3). w取什么值时该算法是A*搜索算法（启发函数需可纳）？其启发函数是什么?

(4). 在问题(3)的A*算法中启发函数为什么是可纳的？在满足可纳性前提下，w取什么值时这种A*算法扩展的节点最少？为什么？

解：

(1). w=0,f(n)=g(n)w=0, f(n)= g(n)，代价一致只考虑从起点到当前点的距离

(2). w=2,f(n)=2∗h(n)w=2, f(n)= 2*h(n) , 节点按 h(n)h(n) 排序，贪心只考虑当前点到终点的距离

(3). 0<w<=1,f(n)=(2−w)∗(g(n)+(w/(2−w))∗h(n))0<w<=1, f(n)= (2-w)*(g(n) + (w/(2-w))*h(n))，启发函数为 (w/(2−w))∗h(n)(w/(2-w))*h(n) ，h(即，heuristic) 的表达式是启发函数

(4). 因为 0<w<=10<w<=1 , 所以启发函数 (w/(2−w))∗h(n)<=h(n)(w/(2-w))*h(n)<= h(n) ，h(n)h(n) 是可纳的，因此 (w/(2−w))∗h(n)(w/(2-w))*h(n) 是可纳的。

所以 w=1w=1 时，启发函数 (w/(2−w))∗h(n)(w/(2-w))*h(n) 可取最大值 h(n)h(n) , 这时候扩展的节点最少。求导发现启发函数单调递增，在定义域 0<w<=10<w<=1 上取 w=1w = 1 时达到最大值

例题2

设有如下结构的移动将牌游戏：其中，B表示黑色将牌，W 表是白色将牌，E表示空格。

游戏的规定走法是：

​ (a) 任意一个将牌可移入相邻的空格，规定其代价为1

​ (b) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1

游戏要达到的目标是把所有W都移到B的左边。

(1). 对这个问题，请定义一个启发函数 h(n) （可以不满足可纳性要求）， 并画出利用这个启发函数产生的搜索树。求出解决该问题的总代价。

(2). 判断这个启发函数是否满足A*算法可纳性的要求？

(3). 基于扩展过的节点判断该启发函数是否满足这些节点的单调限制性？

解：

(1).设 h(x)=W左边的B的个数h(x)=W 左边的 B 的个数，f(x)=g(x)+3∗h(x)f(x)=g(x)+3*h(x) ，则启发函数就是 3∗h(x)3*h(x)

搜索树如下：

(2).判断出构建的启发函数跟每个节点到目标的最小真实代价 h∗(n)h^*(n) 的大小关系。启发函数 3∗h(x)3*h(x) 不满足可纳性，因为在上图倒数第二个节点启发函数值为3,大于这个节点到目标的真实代价2。不满足 h(n)≤h∗(n)h(n) \leq h^*(n) ，即不满足可纳性。

(3).不满足单调限制性，因为满足单调限制性的话，扩展 f(x)f(x) 值不会减小。

也可以解释为，满足单调限制性一定满足可纳性，不满足可纳性所以不满足单调限制性。

也可以解释为，满足单调限制性需要满足，两个下相邻节点的 0≤h(xi+1)−h(xi)≤c(xi,xi+1)0 \leq h(x_{i+1})-h(x_i) \leq c(x_i,x_{i+1})（真实代价），以上最后两个节点，h(xi+1)−h(xi)=3h(x_{i+1})-h(x_i) = 3 ，c(xi,xi+1)=2c(x_i,x_{i+1}) = 2 ，即不满足可纳性。

3. 博弈树搜索

3.1 极大极小值方法（重点）

3.1.1 方法
  • 掌握博弈树搜索中的极大极小方法，能利用其求根节点的估价值

    • 对简单的博弈问题，可生成整个博弈树，找到必胜的策略。

    • 对于复杂的博弈问题，不可能生成整个搜索树，如国际象棋，大约有 1012010^{120} 个节点。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，并利用估价函数 f(n) 对叶节点进行静态估值。

    • 对叶节点的估值方法是：那些对 MAX 有利的节点，其估价函数取正值；那些对 MIN 有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于 0 的值。

    • 为非叶节点的值，必须从叶节点开始向上倒退。其倒退方法是：

      • 对于MAX节点，由于MAX 方总是选择估值最大的走步，因此， MAX节点的倒退值应该取其后继节点估值的最大值。

      • 对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN 节点的倒推值应取其后继节点估值的最小值。

这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。这一过程称为极大极小过程。

简单说就是从可能的子情况（叶结点）开始，向上倒推到根节点，想让谁获得最大收益谁就是 MAX ，从根节点向下，MAX和MIN层交替出现，MAX层的节点取其子节点中最大的，MIN层节点取其子节点中最小的。最后的大收益就是根节点的值。

3.1.2 例题1
3.1.3 例题2

设有如下游戏：开始状态如下图所示。A，B每人各走一步，A先走（A为MAX），而且每个人必须在自己回合将棋子移到一个相邻的空位上。如果对手占据了一个相邻的空位，则可以跳过对手移到再一个相邻的空位上。(例如：如果A在3，B在2，这时A可以跳回1)。当一个玩家到达其初始状态所在位置的对面的尽头，则游戏结束。如果A首先到达4，则A的积分为+1，如果B首先到达1，则A的积分为-1。

(1).按以下要求画出整个游戏的搜索树：

（a）表示每个状态不超过两个变量;

（b）用单层方框将游戏的终止节点框起来，并不再扩展；

（c）有些节点搜索树中已经出现过一次，当其第二次出现，用双层方框将第二次出现的节点框起来。因为其循环重复出现，不需对

​ 第二次出现的节点再扩展。如果他们的估计值不确定，可以用“？”表示。

(2). 在此问题中，利用极大极小方法计算倒推值有何不利因素？

(3). 根据极大极小方法计算各节点倒推值。

(4). 在计算倒推值的过程中，需定义一种规则处理“？”，并给出相应解释。

(5). 判断问题(4)的处理方法是否对于出现循环状态的任意游戏都合适？并说明理由。

(6). 假设棋盘中有n个格子（而不是本题中的4个格子），在n>2的情况下, 判断n取何值A有必胜策略，n取何值B有必胜策略？并简单解释。

解：

（1）如图

（2）倒推时候 “?” 的干扰，难以判断。

（3）如图

(4).

min(−1，?)=−1min(-1，?)=-1 ，因为-1一定会使A失败，？一定不会比-1更小。

max(+1，?)=+1max(+1，?)=+1 ,因为在该问题中+1对A最有利

(5).不是。本问题非常简单，每个节点可以确定胜负。

而对复杂棋类游戏，上述规则没有规定，不确定胜负的节点跟 ？的对比关系。而且没有规定 ？跟和棋节点的对比关系。

(6).n为偶数A可必胜，n为奇数B可必胜。

因为3个格子B可必胜，4个格子A可必胜（如图）。

在5个格子时，AB经过前两步会变为3个格子的情况，

  • 如果A向右，则必输
  • 若A向左，远离了终点，最终也会回到3个格子的状态向右走，所以也必输。同理对于更大n有同样分析。

3.2 α−β\alpha-\beta 剪枝（重点）

  • 能利用 α−β\alpha-\beta 剪枝方法判断博弈树中需要剪枝的部分
3.2.1 剪枝推演过程：

​ 1. 剪枝过程

​ 明确一点，α−β\alpha - \beta 是用来剪枝的，从根节点向下传递到最左叶节点的上一层

​ 首先将根节点置为α=−∞ β=+∞\alpha = -\infty \space \beta=+\infty,先递归传递到左侧最后的MIN层，然后以递归的方式一条分支一条分支遍历。递归时传递前一层结点的 α β\alpha \space \beta 值，回溯时更新父节点的 α β\alpha \space \beta 值。更新规则如下：

​ α=max{α当前节点,α回溯来源子节点,β回溯来源子节点}\alpha=max{\{\alpha_{当前节点},\alpha_{回溯来源子节点},\beta_{回溯来源子节点}\}}

​ β=min{β当前节点,α回溯来源子节点,β回溯来源子节点}\beta = min{\{\beta_{当前节点},\alpha_{回溯来源子节点},\beta_{回溯来源子节点}\}}

​ Max层只更新α\alpha，Min层只更新β\beta

​ 当α>=β\alpha >= \beta时，该节点的右子树被剪枝。

​ 2. 更新节点值

​ 当前节点的所有子节点都遍历结束时，更新子节点的值，MAX层更新为其未被剪枝的子节点的最大值 ，MIN层更新为其未被剪枝的子节点的最小值

  • 原理

    1. α代表的是你的收益将不小于α

    2. β代表的是你的收益将不大于β

    当α大于β时表示此时的收益将比α大，比β小，明显是个空集。所以这个时候进行剪枝

    等于的时候，当前结点的收益已经完全确定，当前结点的未探索的儿子们就都不需要探索了

例题1

来一道例题练练手：

答案如下：

参考文章：https://oi-wiki.org/search/alpha-beta/

例题2

设有如图所示的博弈树，其中标出的数字是假设的估值，请对该博弈树作如下工作：
(1) 计算各节点的倒推值；
(2) 标出MAX节点的α值以及MIN节点的β值，并利用α-β剪枝技术剪去不必要的分枝。 （可只标出最终的α，β值）

解：

（1）不减支，直接使用 MIN-MAX 方法倒推

（2）使用 α−beta\alpha-beta 剪枝，可以看到，最终结果一致，但是省去了很多不必要的搜索

4. 蒙特卡洛树（MCTS）搜索（了解）

4.1 UCB 方法的设计思想

4.2 掌握蒙特卡洛树搜索的基本原理及搜索过程

**蒙特卡洛树搜索：**UCB用于游戏树的搜索方法(Upper Confidence Bound applied to Trees, UCT)，由Kocsis和Szepesavri在2006年提出。

包括四个步骤：选择(Selection)**、拓展(Expansion)、模拟(simulation)、**反向传播(backpropagation)四个阶段：

4.3 了解 AlphaGo 中蒙特卡洛树搜索的应用方法

五、机器学习初步

1. 机器学习的概念及分类

  • 有监督
  • 无监督
  • 强化学习

2. 有监督

2.1 回归

  • 线性回归
    • 了解线性回归模型的工作原理
    • 了解损失函数，学习率，梯度下降等概念

2.2 分类

  • KNN 算法
    • 掌握 KNN 算法的原理及其特点
    • k 值对算法的影响

3. 无监督

3.1 聚类

  • K-means
    • 相似性度量-欧氏距离，余弦相似度等
    • 掌握 Kmeans 算法的原理，及其特点

4. 强化学习

了解强化学习的思想

5. 人工神经网络

5.1 感知机

  • 基本原理——线性分类
  • 了解感知机的不足

5.2 多层感知机

5.3 卷积神经网络

  • 了解 CNN 的设计思想
  • 掌握卷积，卷积核，填充，步幅，池化等概念
  • 理解 CNN 的架构及工作原理