1 问题求解
1.1 状态空间法
状态空间法是以状态和算符为基础来表示和求解问题de
- 问题求解=问题的表达+求解的控制（搜索过程）
- 状态：\(S_k=\{{S_k}_0,{S_k}_1,\cdots\}\)
- 操作符（算符）：将问题从一种状态变换为另一种状态的手段（规则、数学算子、逻辑符号等）
- 状态空间：\((S,F,G)\)，\(S\)为初始状态的集合，\(F\)为操作符集合，\(G\)为目标状态集合
状态空间图：用状态标识节点，用操作标识有向边，形成的有向图
状态空间问题求解：
- 为问题选择适当的状态及操作符的形式化描述方法，定义初始状态集合、目标状态集合以及操作符集合
- 将操作符作用在某状态上生成新状态逐步构造状态空间，判断新状态是否为目标状态，如果是则转3，不是则重复2
- 寻找从初始状态到目标状态的一个路径，路径边上所使用的操作符序列即为问题的一个解
求解系统的构成：
- 初始数据库：初始状态、目标状态等构成的部分状态空间
- 规则库：操作条件&操作
- 控制策略：决定当前状态所使用的操作及结束条件
状态空间的搜索策略：按照是否使用启发式信息分类，分为
- 盲目搜索（搜索过程中不改变控制策略）
- 启发式搜索（启发性信息指导搜索朝最有希望的方向前进）
状态空间搜索的基本思想：从初始状态开始，对当前状态进行扩展生成子节点，然后检查目标状态是否存在于子节点，如果存在则结束，否则按某种策略从已生成的节点中选择一个节点进行扩展，如此反复，直到出现目标状态或没有可扩展的节点为止。
1.2 状态空间的盲目搜索
open表与closed表：
- open表用于存放刚生成的节点，因此又称为未扩展节点列表
- closed表用于存放已经扩展的节点，因此又称为已扩展节点列表·
广度优先搜索BFS：穷举式搜索的一种，始终优先在同一级节点中考察，因此是自顶向下逐层生成
- 算法：
- 将初始节点放入open表
- 如果open表为空，则问题无解，退出
- 将open表的第一个节点取出放入closed表，并标记为n
- 考察节点n是否为目标节点，如果是则结束
- 若n不可扩展，则转2
- 扩展节点n，将子节点放入open表的
尾部，为每个子节点设置指向n的指针，转2 - 特点：
- open表是一种队列
- BFS是一种完备策略，只要有解就一定能找到解，并且是最优解
- 盲目性较大，可能生成许多无用节点，搜索效率较低
深度优先搜索DFS：穷举式搜索的一种，每层始终优先只扩展一个节点，因此是逐枝生成
- 算法：
- 将初始节点放入open表
- 如果open表为空，则问题无解，退出
- 将open表的第一个节点取出放入closed表，并标记为n
- 考察节点n是否为目标节点，如果是则结束
- 若n不可扩展，则转2
- 扩展节点n，将子节点放入open表的
首部，为每个子节点设置指向n的指针，深度为\(d(n)+1\)，转2 - 特点：
- open表是一种堆栈
- DFS是一种不完备策略，不一定能找到解，找到的解也不一定是最优解
有界深度优先搜索：
- 算法：
- 将初始节点放入open表，设置
深度为\(d(s_o)=0\) - 如果open表为空，则问题无解，退出
- 将open表的第一个节点取出放入closed表，并标记为n
- 考察节点n是否为目标节点，如果是则结束
- 若n不可扩展，或深度\(d(n)\)等于深度限制值\(d_m\)，则转2
- 扩展节点n，将子节点放入open表的
首部，为每个子节点设置指向n的指针，转2 - 特点：
- 深度限制\(d_m\)是很重要的参数，能否找到解与问题的解的深度和深度限制有关
- \(d_m\)太大会降低搜索效率，太小可能找不到解
- 优化方法：从小的\(d_m\)开始尝试，逐渐增大\(d_m\)
代价树的广度优先搜索（分支界限法）：
- 算法：
- 将初始节点放入open表，设置
代价为\(g(s_o)=0\) - 如果open表为空，则问题无解，退出
- 将open表的第一个节点取出放入closed表，并标记为n
- 考察节点n是否为目标节点，如果是则结束
- 若n不可扩展，则转2
- 扩展节点n，将子节点\(n_i\)放入open表，为每个子节点设置指向n的指针；按公式\(g(n_i)=g(n)+c(n,n_i)\)计算open表中节点代价并排序，然后转2
- 特点：
- 代价树的广度优先搜索是完备的，找到的解一定是最优解
代价树的深度优先搜索：
- 算法：
- 将初始节点放入open表，设置
代价为\(g(s_o)=0\) - 如果open表为空，则问题无解，退出
- 将open表的第一个节点取出放入closed表，并标记为n
- 考察节点n是否为目标节点，如果是则结束
- 若n不可扩展，则转2
- 扩展节点n，将子节点
按代价从小到大放入open表的首部放入open表，为每个子节点设置指向父节点的指针，然后转2 - 特点：
- 代价树的广度优先搜索从open表的全体节点中选择代价最小的；代价树的深度优先搜索从扩展的子节点中选择代价最小的节点
1.2 状态空间的启发式搜索
盲目搜索与启发式搜索：
- 盲目搜索：扩展结点数目较多，效率低
- 启发式搜索：利用只是来引导搜索，减少搜索范围，降低问题复杂度
启发性信息：与具体问题求解过程有关的，并可知道搜索过程朝着最有希望方向前进的控制信息
- 扩展结点的选择，决定优先扩展哪个节点
- 生成节点的选择，决定应生成哪些节点
- 删除节点的选择，决定应删除哪些节点
启发性信息的强弱：
- 强：降低搜索工作量，但可能导致找不到解
- 弱：工作量较大，极限情况下变为盲目搜索，但可能找到最优解
估价函数：度量节点的“希望”程度
- 节点处在最佳路径上的概率
- 任意一个节点与目标节点集之间的距离或差异
- 根据格局（博弈问题）或状态的特点打分
有序搜索：
- 算法：
- 将初始节点放入open表，计算\(f(s)\)
- 如果open表为空，则问题无解，退出
- 将open表中\(f\)最小的节点取出并放入closed表
- 考察节点n是否为目标节点，如果是则结束
- 扩展节点n，对于每个子节点\(j\)：
- 如果\(j\)不在open表也不在closed表，则将其加入open表并设置父指针
- 如果\(j\)已在open表或closed表，则将新\(f\)值与原\(f\)值比较。如果新\(f\)值更小，则取代原\(f\)值，并更新父节点。如果\(j\)在closed表中，将其取出放入open表
- 转到2
- 特点：
- 代价树的广度优先搜索从open表的全体节点中选择代价最小的；代价树的深度优先搜索从扩展的子节点中选择代价最小的节点
A算法：
- 基本思想：估价函数\(f(n)=g(n)+h(n)\)，其中\(g(n)\)为从s到n的代价，\(h(n)\)为从n到g的代价/接近程度
- \(g(n)\)有利于搜索的横向发展
- \(h(x)\)有利于搜索的纵向发展
A*算法：如果对A算法限制估价函数，使其满足“对所有节点\(x\)，均有\(h(x)\leq h^*(x)\)，其中\(h^*(x)\)为从节点\(x\)到目标节点的最小启发值”，则这样的A算法称为A*算法
- 限制\(h(x)\leq h^*(x)\)是为了保证得到最优解
- A*算法也称为最佳图搜索算法
启发式搜索的特点：
- 搜索算法的可纳性：对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的
- 设计更接近于\(h^*(n)\)的\(h(n)\)
- A*算法的信息性（启发式函数的强弱）:
- 当\(h(n)<h^*(n)\)且两者差距较大 ，启发式信息过弱，导致OPEN表中节点排序的误差较大
- 当\(h(n)>h^*(n)\)，启发式信息过强，使A算法失去可采纳性，从而不能确保找到最短解答路径
- 当\(h(n)=h^*(n)\)时，不会去扩展多余的节点就可找到解
- 设计\(h(n)\)的实用考虑：\(f(n) = g(n) + w\cdot h(n)\)
- \(w\)取较大值，搜索图的浅层，突出启发式函数的作用，加速向纵深方向搜索
- \(w\)取较小值，搜索图的深层，引导搜索向横广方向发展，寻找到较短的解答路径