2.1 搜索问题与求解

问题求解过程是搜索答案（目标）的过程，所以问题求解技术也叫做搜索技术——通过对状态空间的搜索而求解问题的技术。

• 适用情况

  1. 不良结构或非结构化问题

  2. 难以获得求解所需的全部信息

  3.没有现成的算法可供使用

2.1.1 问题与问题的解

问题可形式化地定义成四个组成部分

1. 初始状态
   搜索的开始

2. 后继函数

   • 可能行动的描述，通常为<行动，后继状态>
   • 初始状态和后继函数隐含地定义了问题的状态空间
   • 状态空间中的一条路径是通过行动序列连接起来的一个状态序列

3. 目标测试
   检查给定的状态是不是目标

4. 路径耗散函数
   反应性能度量/求解问题的代价

状态空间

• 状态：表示求解过程中，每一步数据结构的状况，可以表示为：
• 操作：也称为算符，是把问题从一种状态变换为另一种状态的手段，可以是一个机械步骤，一个运算，一条规则或者一个过程。
• 状态空间：用来描述一个问题的全部状态及这些状态之间的相互关系。常用一个三元组表示为（S，F，G）。其中S为初始状态集合，F为操作集合，G是目标状态集合。

搜索空间

在解题过程中达到过的所有状态的集合。不同于状态空间，搜索空间是其中一部分。状态空间和搜索空间都属于过程性知识表示。

2.1.2 问题实例——八数码问题

规则

1. 1-8数字(棋子)/9个方格(棋盘格)/1个空格
2. 可用如下形式的规则来表示数字通过空格进行移动：
   <a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>
3. 共24条操作=4角2+4边3+1中间*4

问题形式化

• 初始状态：用向量表示初始状态，如：<3,8,2,×,5,1,4,7,6>
• 后继函数：24种移动操作选一，得到新的向量
• 目标测试：判断新目标状态是否满足<1,2,3,4,5,6,7,8,×>
• 路径耗散函数：每次移动代价等值，为1

算法实现

八数码问题详解

2.1.3 搜索策略

搜索前需要考虑的问题

• 有限搜索还是无限搜索
• 目标已知未知
• 目标或目标+路径
• 有无约束
• 数据驱动（向前搜索）还是目标驱动
• 单项搜索还是双向搜索
  搜索过程一般使用图搜索算法，其中盲目搜索技术、启发式搜索技术是图搜索策略的具体化

图搜索

• 扩展一个节点：生成出该结点的所有后继结点，并给出它们之间的代价，这一过程称为“扩展一个节点”
• 图搜索的一般过程

1. 建立一个只含有起始节点S的搜索图G，把S放到OPEN表中，用于存放未扩展节点表
2. 初始化CLOSED为空表，用于存放已扩展结点
3. 循环：若OPEN是空表，则失败退出；否则选择OPEN表上的第一个节点，从OPEN中移除放入CLOSED中。记这一个结点为节点n
4. 若n为目标状态，则有解，所求解是G中沿着指针从n 到S的一条路径
5. 否则，扩展节点n，生成不是n祖先的那些节点，并作为后继节点加到G中
6. 根据扩展出的节点类型，标记和修改指针
7. 按某一方式或某个评价函数，重排OPEN表

• 对几种扩展节点类型的说明

  1. 既不在OPEN也不再CLOSED中的扩展结点（最正常情况）：设置一个通向n的指针，并加入OPEN中
  2. 已经在OPEN中（扩展出同级节点已经扩展出的节点）：确定是否需要改变通向n的指针方向
  3. 已在CLOSED中（扩展出祖先节点）：确定是否需要更改G中通向它的每个后裔节点的指针。

• 图搜索程序流程图

  
  

两种搜索技术

• 盲目搜索技术：人为排序规则
• 启发式搜索技术：依据估价函数的值

2.2 无信息搜索策略

无信息搜索策略也称盲目搜索：没有任何附加信息，只有生成后继和区分目标和非目标状态。
五种盲目搜索策略有：广度优先搜索，代价一直搜索，深度优先搜索，深度有限搜索，迭代深入深度优先搜索。

2.2.1 广度优先搜索

• 过程：首先扩展根节点；接着扩展根节点的所有后继节点，依此类推......如此下去，在下一层扩展之前，搜索树上本层深度的所有节点都已经被扩展。
• 数据结构：其OPEN表为先进先出的队列

广度优先搜索 伪代码逻辑

open = [start]; closed = []
while open[]:
    从open[]删除第一个状态，称为n
    将n移入closed[]表
    if n == 目标状态:
        return success
    生成n的所有子状态
    从子状态集合中删除已存在于open 或closed表中出现的状态，
    将剩余n的子状态，按生成次序加入到open表后段

广度优先搜索的性能

从四种度量来评价广度优先搜索

• 完备性：总能找到一个解
• 最优性：如果每步所耗代价相同，则广度优先所求解一定是最优解
• 时间复杂性：指数级的时间消耗，O (b^(d+1))
• 空间复杂性：内存消耗是比执行时间消耗更大的问题

复杂度通常由三个量决定: b——分支因子，任何结点的最多后继；d——目标节点所在的最浅深度；m——状态空间中任何路径的最大长度

2.2.2 深度优先搜索和深度有限搜索

深度优先搜索

过程

• 总是扩展搜索树当前分支（边缘）中最深的节点
• 搜索直接伸展到搜索树的最深层，直到没有后继节点
• 删除扩展完毕的节点
• 搜索算法回退到还有未扩展节点的上层节点继续扩展

• 数据结构：其OPEN表为后进先出的栈

性能：通常使用递归函数实现，一次对当前节点的子节点调用该函数。相比广度优先，内存需求少(分支因子 * 最大深度+1)。但不是完备的也不是最优的*。

深度有限搜索

深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制I来解决。深度=I的节点当作无后继节点看待；虽然解决了无边界问题，但有可能无解；如果选择I>d则深度优先原则也不是最优解。

迭代深入深度优先搜索

每次改变限制深度，多次调用深度有限搜索，当搜索到达最浅的目标节点深度时就可以发现目标节点，称为迭代深入深度优先搜索。这种搜索结合了广度优先和深度优先两种搜索方式的优势。解决了深度优先的完备性问题。空间需求是(b * d),时间需求是(b ^d)。当搜索空间很大且深度未知时，迭代深入深度优先搜索是首选的无信息搜索方式。

迭代深入搜索中因为多次重复搜索上层节点，使部分状态反复生成，看起来很浪费内存空间和时间。但是因为在分支因子比较均衡的搜索树中，多数节点都是叶子节点*（叶子节点数远大于上层节点总和），所以上层节点多次生成的影响并不大，与广度优先相比，效率还是很高。

双向搜索

用于目标状态已知，求解过程的问题。通常通过广度优先搜索实现。从起始节点和目标状态两个方向开始扩展，当两个OPEN表出现交集时表明搜索到了一条从起始到结果的一条路径。缺点：算法编写难。但一旦实现，效率要远高于其他盲目搜索。

2.3 启发式搜索

• 盲目搜索不足的原因：待扩展节点顺序固定，不会对更有希望达到目标状态的结点特别关照。
• 启发式搜索又称有信息搜索：利用相关领域特征的启发信息来排列待扩展节点顺序（重排OPEN表），从而选择最有希望的节点作为下一个扩展结点。缺点：算法找到的解无法保证是最优解。

启发式搜索策略基本思想

假定存在估值函数f(n)，把新状态按估计值从小到大插入OPEN表中（不同于图搜索，扩展的结点包括父结点）。
关键：估值函数f(n)的设计

2.3.1 贪婪最佳优先搜索

评价函数：f ( n ) = h ( n ) ；评价函数等于启发函数
解释：贪婪最佳优先搜索中无条件选择当前离目标最近（代价最小）的结点进行扩展。但是局部最佳不是全局最佳，即非最优。其中h（ n ）称为启发函数，是从节点n到目标节点的最低代价的估计值。

2.3.2 A* 搜索

评价函数：f ( n ) = g ( n ) + h ( n )；评价函数等于启发函数加路径耗散函数
解释：

• g ( n )：从初始节点到该节点n的路径耗散函数
• h ( n )：从节点n到目标节点的最低代价的估计值。
  因此，A* 搜索的评价函数的含义是1.经过结点n；2.具有最低代价的；3.解的估计代价值

另，对于有向图的搜索还可以采用图搜索方式。详情：图搜索和树搜索详解

启发函数的可采纳性

称启发函数是可采纳的，如果h( n ) 满足 h( n ) ≤ h * ( n )，其中 h * ( n )是从当前节点n到达目标的最低真实代价，即h( n )的估值永远小于真实耗散值；因为f ( n ) = g ( n ) + h ( n )，且g（n）为已知常数，所以f（n）永远不会高估经过结点n的解的实际代价，所以是最优解。

• 如果h( n ) 是可采纳的，则A* 树搜索算法是完备且最优的。

如果采用A* 图搜索算法，则不一定返回最优解。因为如果最优路径不是第一个生成的，可能因为有重复状态而被丢弃了。见上个链接：图搜索和树搜索详解

A* 图搜索最优解解决方案：修改算法使得能够比较，只丢弃耗散值大的路径；保证重复状态中最先被选中扩展的节点在最优路径中，即到达任何重复状态的最优路径总是第一条被追随的路径——要求h（n）保持一致性（单调性），一致性见下文

启发函数的一致性

如果对于每个结点n，以及n的行为a产生的后继结点n'满足如下公式：h ( n ) ≤ c ( n, n', a) + h( n ')（c ( n, n', a)可以理解为g（n'）），则称这个h ( n )启发函数是一致的。

• 如果h( n ) 是一致的，则A* 图搜索算法是最优的。
  如果h( n ) 是一致的，那么沿着任何路径的f（n）值是单调非减的。由此，可以在状态空间中画出等值线
  

如果h ( n ) 是一致的，那么它是可采纳的。（用一致性可证可采纳性）

A* 搜索节点的扩展

A* 搜索由初始结点出发开始搜索，以同心带状增长f（n）耗散值的方式扩展结点。如果h（n）= 0 意味着只按g（n）值排序，即同心带为“圆形”。使用启发函数则同心带向目标节点拉伸（椭圆越来越扁）。

如果C*是最优路径的耗散值，则：

• A* 算法扩展所有f ( n ) < C*的结点
• A* 算法在达到目标结点前，可能会扩展一些正好处于“目标等值线”上的结点。
• A* 算法不扩展f ( n ) > C的结点（均被剪枝*）

2.3.3 启发函数

A* 搜索的关键就是设计可采纳的或一致的（单调的）启发函数。

如何设计启发函数

启发函数的核心

绝不高估到达目标的耗散值，尽可能的接近真实耗散值

例如对于八数码问题的常用候选

• h1(n) = 不在位棋子数；一定能做到h1(n) <= h*(n)，即可采纳性
• h2(n) = 所有棋子到指定位置的曼哈顿距离和，也是可采纳的
  启发函数越接近于真实最优解的值，相应的算法效率越高。因为启发函数可以被认为是已知信息的量，显然已知越多求解效率越高。h2的信息量更多，相应的值也更高。显然启发函数h(n)<h*(n)的情况下，值越大越好。

寻找策略

• 从松弛问题中获得——松弛问题的最优解的耗散是原问题的一个可采纳的启发函数。
• 从给定问题的子问题的耗散值中获得——建立模式数据库，存储每一个可能的子问题实例
• 从经验中学习——归纳学习

松弛问题最优解 作为启发函数

• 松弛问题——降低了行动限制
  原始问题的最优解也是松弛问题的最优解，其耗散值不低于松弛问题的最优解。松弛问题的最优解是确切耗散，一定满足三角不等式，因而是单调的。所以启发函数一定是可采纳的。

子问题的解耗散作为启发函数

子问题的解耗散是完整问题的耗散下界。

• 建立模式数据库
  从目标状态向后搜索并记录每个子状态的耗散，存储于数据库中。搜索中遇到的每个完整状态便可查找出相应的子问题布局而设计一个可采纳的启发函数。

归纳学习

从实例中学习，每个实例包含了解路径上各状态及其到达解的耗散值。每个最优解实例提供了可学习h(n)的实例，由此产生可预测其他状态解消耗的启发函数。

2.3.4 联机搜索

• 脱机搜索——不需感知，只要计算
• 联机搜索——必须通过行动与计算交叉进行才能决定下一步搜索。分为两种情况：环境未知——只有行动才能得知如何正确走向目标/；环境空间过大——虽然理论上已知，但实际不可计算。

例如：迷宫问题
联机搜索只能通过行动来解决，因为障碍是不能事先预知的。

联机搜索智能体

联机搜索智能体需要行动和感知，然后扩展当前状态的环境地图

智能体初始位置在S，其已知信息为：

• ACTION(s)——状态S下的行动列表
• c(s,a,s')——通过行动a从s状态到s‘
• Goal-Test(s) / G目标位置

与脱机搜索的区别

A* 搜索在不同子空间结点的跳跃式扩展，模拟而非实际行动；联机搜索只扩展实际占据的结点——采用深度优先。联机搜索必须维护一个回溯表

博弈搜索

博弈搜索是智能体之间的对抗，每个智能体的目的是冲突的。本节需要解决两个问题：如何搜索到取胜的路径/如何提高搜索效率。相应的办法是极大极小决策和α-β剪枝。

博弈游戏

双方的初始状态和合法操作定义了游戏的博弈树，称为博弈搜索

• 初始状态——棋盘局面和出棋顺序
• 后继函数——返回（招数，状态）二元组的一各列表，其中每对表示一个合法招数和相应的结果状态。
• 终止测试——判断是否结束
• 效用函数：又称目标函数，对终止状态给出一个数值如输赢和平局(-∞/ 0/ +∞)

两个智能体博弈时，可令一方为MAX，一方为MIN。MAX希望终局得分高，MIN希望终局得分低。

2.4.1 极大极小决策（最优策略）

博弈搜索中，最优解是导致取胜的终止状态的一系列招数。MAX制定取胜策略时，必须不断考虑MIN应对条件下如何取胜。

1. MAX在初始状态下应该采取什么策略
2. MIN应对造成的状态下采取什么策略
3. 反复第二步

如果博弈双方都按照最优策略进行，则一个结点的极大极小值就是对应状态的效用值

• MAX优先选择极大值状态，MIN优先选择极小值状态。（状态都存在于后继结点中）

极大极小值算法

简单的递归算法——按照定义计算每个后继结点的极大极小值/搜索是从目标到初始结点的反向推导

极大极小值算法复杂度

如果博弈树最大深度为m，每个节点的合法招数为b，则

• 时间复杂度：O（b ^m）
• 每次生成全部后继结点的空间复杂度：O(b * m)
• 每次生成一个后继结点的空间复杂度：O( b )

极大极小值算法优缺点

• 优点：在对手也“尽力而为”时，可返回最优解果
• 缺点：搜索树极大，呈指数级增长。

2.4.2 α-β剪枝

剪掉那些不可能影响最后决策的分支，返回和极大极小值相同的结果。
α-β剪枝可以应用树的任何深度。

α-β剪枝原则

如果在结点n的父节点或更上层有一个更好的选择m，则在搜索中永远不会到达n。

• α = 到目前为止在路径上任意点发现的MAX最佳选择
• β = 到目前为止在路径上任意点发现的MIN最佳选择
• α-β搜索不断更新α 和 β的值，当某个节点的值分别比α 和 β差时，剪掉该节点的剩余分支
  

α-β剪枝效率

很大程度上取决于检查后继节点的次序——应先检查那些可能更好的后继。如果能先检查那些最好的后继，则时间复杂度为O(b^(d/2))。优于极大极小算法的O(b^d)

2.5 局部搜索算法

许多问题中路径是无关紧要的。从当前状态出发，通常只移动到相邻状态，且路径不保留。

2.5.1 局部搜索和最优化

内存消耗少，通常是一个常数。

• 最优化问题——根据一个目标函数找到最优状态。
  极易找到局部最优，但无法找到全局最优。问题在于，如何放弃局部最优。

2.5.2 爬山法

向目标函数值增加的方向持续移动，直到相邻状态没有比它更高的值。取到一个局部最优则终止。
使新状态估计值优于当前状态值和其他所有候补结点值，则取新状态放弃其他状态。

爬山法变形

• 随机爬山法：按某种概率选择下一步
• 首选爬山法：随机选择直到优于当前结点的下一步
• 随机重新开始爬山法：随机生成初始状态。完备的概率接近一。

2.5.3 模拟退火算法（重）

将爬山法（停留在局部最优）和随机行走（下山）以某种方式结合，同时拥有完备性和效率。
技巧是，概率足够大可以弹出局部最优；但概率不能太大而弹出全局最优。

模拟退火

模拟退火算法思路

按照模拟退火的思想，T随时间逐渐减小。如果T下降的足够慢，则找到全局最优解是完备的。

算法核心——移动选择

随机移动，如果评价值改善则采纳；否则以小于一的概率接受。

• 接受概率P = e ^ΔE/T， ΔE <0(下山被接受的概率)
  1. 温度T越大概率越大
  2. 评价值变坏的梯度ΔE越大，意味着新值远低于旧值，P降低

状态产生函数

• 原则：候选解应遍布全部解空间
• 方法：在当前状态邻域内以一定方式（均匀分布，正态分布……）产生

状态接受函数

• 原则
  1. 固定温度下，接受使目标函数下降（上山）的候选解的概率要大于使目标函数上升的候选解概率。
  2. 随温度的下降，接受使目标函数上升（下山）的解的概率要逐渐减小
  3. T趋于零时，只能接受下降解（上山）。
• 方法：
  一般采用min[ 1, e^(-ΔC/T) ],具体形式对算法影响不大

初温

• 收敛性分析：解决实际问题时难以得到精确参数；初温应足够大
• 实验表明：初温越大，获得高质量解的几率越大，但花费较多的计算时间
• 方法
  1. 均匀抽样一组状态，取方差为初温
  2. 随机产生一组状态，以两两状态间最大差值为初温
  3. 利用经验公式

温度更新函数

• 时齐算法的温度下降函数
  1. t{k+1} = a*t{k},k≥0，0≤a≤1，a越接近1温度下降越慢，且其大小可以不断变化
  2. t{k} = [(K-k)/K] * t{0}，t{0}为起始温度，K为算法温度下降总次数

优缺点

• 优点：质量高；初值鲁棒性（程序健壮性）强；简单易实现
• 缺点：要求较高初始温度，较低降温速度等，优化时间长000

2.5.4 局部剪枝搜索

从k个随机生成的状态开始，每步生成k个结点的所有后继状态。如果其中之一是目标状态则停止算法；否则从全部后继状态中选择最佳的k个状态继续搜索。
有用的信息在k个并行的 搜索线程之间传递，算法会很快放弃没有成果的搜索，而把资源放在取得最大进展的搜索上。

随机剪枝搜索

局部剪枝搜索的变种。因为局部剪枝搜索搜索是贪婪的，因而用随机剪枝搜索代替。不是选择最好的k个后代，而是按照一定概率选取k个后继状态。

• 选择给定后继状态的概率是状态值的递增函数。

类似于自然界的选择过程。状态对应个体，其值对应适应性，后代就是状态。因此如果k个状态缺乏多样性，则局部搜索会受影响。

2.5.5 遗传算法（GA）

局部剪枝算法已有群体进化（优胜劣汰）的趋势。遗传算法是随机剪枝的变种。

• 遗传算法：不是通过修改单一状态而是通过把两个父状态结合以生成后继状态。

遗传算法简要描述

1. 定义问题和目标函数
2. 选择候选解作为初始种群，每个解作为个体进行编码表示（类似于染色体）。

• 种群与个体：遗传算法从k个初始状态随机开始，称这k个状态为种群，每个状态为个体
• 编码：个体通常由一个用于描述其基本遗传结构的数据结构（0/1串）表示。此处个体每个位置的0/1都是具有一定含义的，象征着这个状态的某个特征，而非随机的。一个状态与目标状态的匹配度越高，则其越优。

3. 根据目标函数，对于每个个体计算适应函数值

• 评价值（适应函数值）：每个状态用其评价函数给出评价值，象征着适应程度。

4. 为每个个体指定一个与其适应值成正比的被选择概率，体现了优胜劣汰
5. 根据概率选择个体，所选个体通过交叉/变异等操作产生下一代种群

• 选择，交叉和编译被称为遗传算子

6. 直至达到某种状态，否则转到（3）

遗传算法的操作

包括选择，交叉和变异

选择

又称繁殖，按照一定的概率选择两对个体生成后继状态

选择方法——轮盘式选择

计算每个个体i被选中的概率：pi = f(i) / [f(1)+...+f(n)].然后根据概率将圆盘分为n个扇形，每个扇形大小为2Πpi。

交叉

繁殖过程中，后代是父串在杂交点上进行杂交得来的。这样一来，后代子串保留了父串的优良特性又与父串不同。

• 杂交点：在编码中随机选择一个位置，以此形成新状态。

交叉方法——单点一致交叉

首先以概率p随机在种群中选择pa和pb两个个体，再从{1,2,...,m}中（可以按一定概率，如两边概率小于中间概率）选择一个数i，作为交叉点。而后将两个个体的交叉点后面的部分交换。

变异

在新生成的后继状态中各个位置都会按照一个独立的很小的概率随机变异。
变异时要做到一致变异；即相同概率地变异所有个体的每一位。

对于个体p的第j位，再[0,1]范围内随机生成一个数r，如果r < p，则变异；否则不变。

遗传算法的特点

结合了“上山”和随机行走，并在并行搜索线程之间交换信息。遗传算法的最大优点在于杂交。因为杂交可以将独立发展的若干个砖块组合起来，提高搜索的粒度。

砖块：能够执行有用的功能，几个结合起来可以构造问题的解

遗传算法的模式

个体编码某些位置上数字仍未确定的一个状态子串。

• 实例：能够匹配模式的串被称为该模式的实例。

模式定理

如果一个模式的实例的平均适应值超过均值，则种群内这个模式的实例数量会随时间而增长（优胜）；反之则减少（劣汰）

积木块假设

长度较短，高于平均适应度的模式在遗传算子的作用下，相互结合，能生成长度较长、适应度较高的模式。

注意：遗传算法在 模式 和 解的有意义成分 相对应时才会工作的更好。

2.6 约束满足

Constraint Satisfying Problem，CSP。

2.6.1 CSP定义

由一个变量集合{X1~Xn}和一个约束集合{C1~Cn}；每个变量都有一个非空可能的值域Di。每个约束指定了若干变量的一个子集内各变量的赋值范围。

CSP的一个状态是，对一些或每个变量赋值

CSP的解

一组既是相容赋值又是完全赋值的对变量的赋值就是CSP的解。

• 相容赋值：不违反任何约束的对变量的赋值
• 完全赋值：对每个变量都赋值

从搜索角度看待CSP

• 主要问题：从何处开始赋值较好（不影响结果，但影响搜索过程）；回溯时如何回溯

CSP看待问题的形式化

• 初始状态：

• 常使用深度优先搜索
• 深度是有限的：n个变量，深度为n
• 每个解必须完全赋值

CSP问题的分类

CSP问题复杂度

2.6.2 CSP回溯搜索

2.6.3 变量赋值次序的启发式

MRV启发式

度启发式

2.6.4 变量约束的启发式

提前考虑某些约束，以减少搜索空间

前向检验

若X被赋值，检查与X相连的Y，判断是否满足约束，去掉Y中不满足约束的赋值。（进行某种检验，可以不为有问题的Y集合赋值 ）

• 地图染色问题中的前向检验

约束传播

弧相容

2.6.5 关于失败变量的启发式