第五章 搜索求解策略

问题求解的基本方法有搜索法、归约法、归结法、推理法及产生式等。其中推理法、归结法、产生式在前面的章节已经介绍过。

一、搜索概述

• 数据驱动：从初始状态出发的正向搜索
• 目的驱动：从目的状态出发的逆向搜索

是否运用与问题有关的信息

• 启发式搜索：动态调用操作算子，有限选择较为合适的操作算子，尽量减少不必要的搜索
• 盲目搜索：按固定的步骤（依次或随机调用操作算子），能快速地调用一个操作算子

二、状态空间的搜索策略

状态空间四元组表示法：其中S表示状态集合，O表示操作算子的集合
表示问题的初始状态，G表示问题的目标状态，G可以是若干具体状态。
从S_0节点到G结点的路径称为求解路径，求解路径上的操作算子序列称为状态空间的一个解，当然解往往不是唯一的。

任何类型的数据结构都可以用来描述状态，字符串、向量、多维数组、树、表格等，所选用的数据结构形式要与状态所蕴含的某些特性具有相似性。例如对八数码问题，一个33的阵列便是一个合式的状态描述方式。

*状态空间的有向图表示

搜索策略的主要任务是确定选取操作算子的方式，它有两种基本方式：盲目搜索和启发式搜索。

三、盲目的图搜索策略

3.1 回溯策略

当遇到不可解结点时就回溯到路径中最近的父节点上，查看该结点是否还有其他的子节点未被扩展，若有则沿着这些子节点继续搜索。

• 路径状态表（PS）：保存当前搜索路径上的状态
• 新的路径状态表（NPS）：包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展

• 不可解状态表（NSS）：找不到解路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即删除，不必沿着继续搜索

  3.2 宽度优先搜索策略BFS

  类似于树的层次遍历。在实际搜索时，为了保存状态空间搜索的轨迹，用到了两个表，open表和closed表。

• open表：与回溯算法的NPS表相似，包含了已经生成出来但其子状态未被搜索的状态，open表中状态的排列次序就是搜索的次序。open表是一个队列结构

• closed表：记录了已被生成扩展过的状态，相当于回溯法中PS和NSS表的合并

由于宽度优先搜索总是在生成扩展完N层的所有结点之后才转向N+1层，所以其总能找到最优解（若有解情况下）

3.3 深度优先搜索策略DFS

深度优先搜索法不一定能找到最优解，并且可能由于深度的限制，会找不到解。

• open表：是一个堆栈结构，即先进后出

• 
  

  四、启发式图搜索策略

  必须针对具体问题具体分析，利用与问题有关的信息，从中得到启发来引导搜索，以达到减少搜索量的目的。

  启发式策略概述

  注意：启发式策略极易出错，在解决问题过程中启发仅仅是下一步将要采取措施的一个猜想，常常根据经验和直觉判断。一个启发式搜索可能得到一个次优解，也可能一无所获。这是启发式搜索固有的局限性，这种局限性不可能由所谓更好的启发式策略来彻底消除。
  在问题求解中，需要利用启发式知识来剪枝以减少状态空间，否则只能求解一些小规模的问题。
  利用启发信息设计估价函数，以估价函数计算待搜索节点的价值；估价函数的设计至关重要。

  启发信息和估价函数

  启发信息按运用的方法不同可以分为三种

• 陈述性启发信息：一般用于使问题的状态空间缩小，例如用棋盘的对称性减小搜索空间的大小

• 过程性启发信息：一般用于构造操作算子，
• 控制性启发信息：

估价函数综合考虑已经付出的代价和将要付出的代价。

其中g(n)越大，越倾向于宽度优先搜索，这有利于搜索的完备性，但会影响搜索的效率。

A

启发式图搜索算法使用两张表记录状态信息：

• open表保留所有已经生成但未扩展的状态
• closed表保留已经扩展的状态

有区别的是open表的排列，其既不是根据宽度优先使用的先进先出，也不同于深度优先使用的先进后出，而是根据估价函数的值的大小进行排列
估价函数也不是越大越好，估价函数值过大会使A算法不一定能搜索到最优解

A*

比A算法好，不仅能得到目标解，并且一定能找到最优解