简介
搜索是人工智能中的一个基本问题，并与推理密切相关。搜索策略的优劣，将直接影响到智能系统的性能与推理效率。
什么是搜索
根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索
包括两个方面：
找到从初始事实到问题最终答案的一条推理路径
找到的这条路径在时间和空间上复杂度最小
搜索的分类
按是否使用启发信息
（1）盲目搜索(Uninformed search)
盲目搜索按预定的控制策略进行搜索，搜索过程中获得的中间信息不用来改变搜索策略。搜索总是按预定的路线进行，不考虑问题本身的特性，这种搜索有盲目性，效率不高，不利于求解复杂问题。
（2）启发式搜索(Heuristic search, Informed search)
启发式搜索中利用问题领域相关的信息作为启发信息，用来指导搜索朝着最有希望的方向前进，提高搜索效率并力图找到最优解。
启发式搜索需要利用问题领域相关的信息帮助搜索，但并不是对每一类问题都容易抽取出启发信息，所以在很多情况下仍然需要盲目搜索。
适用情况
不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。
问题的形式化表示
搜索时首先要将问题进行形式化表示，常用的形式化表示方法有状态空间法、与或树（问题归约法）表示法等
搜索策略常用评价指标：
①完备性（Completeness）
如果问题有解，算法就能找到，称此搜索方法是完备的。
②最优性（Optimality）
如果解存在，总能找到最优解。
③时间复杂度（Time Complexity）
④空间复杂度（Space Complexity）
问题的状态空间表示
1.状态(state)
事物是运动、变化的，为描述问题的运动、变化，定义一组变量描述问题的变化特征和属性。
2.形式化表示：
(s1,s2,..si,…,sn)
当对每一个分量都给以确定的值时，就得到了一个具体的状态。
2.操作符(Operator)
也称为算符，它是把问题从一种状态变换为另一种状态的手段。
操作可以是一个机械步骤，一个运算，一条规则或一个过程。
操作可理解为状态集合上的一个函数，它描述了状态之间的关系。
3.状态空间(State space)
- 用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：
(S, F, G) 其中：
- S为问题的所有初始状态的集合；
- F为操作（函数、规则等）的集合；
- G为目标状态的集合。
- (3,3,1)è(0,0,0)
4.状态空间的有向图表示：
- 结点（节点）：节点表示问题的状态
- 弧（有向边）：标记操作符；可能的路径代价。
5.状态空间法求解问题的基本过程：
首先为问题选择适当的“状态”及“操作”的形式化描述方法；
然后从某个初始状态出发，每次使用一个满足前提条件的“操作”，且此操作产生了新的状态，递增地建立起操作序列，直到达到目标状态为止；
此时，由初始状态到目标状态所使用的算符（操作符）序列就是该问题的一个解。
状态空间搜索的基本思想
先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。
基本概念
- 1.扩展(Expanding)节点
- 对某一节点（状态），选择合适的操作符作用在节点上，使产生后继状态（子节点）的操作。
- 类似数据结构中的寻找邻接点，但这里的邻接点是选择操作后产生的。
- 2. Open和Closed表
- 这两个表用来存放节点，Open表存放未扩展节点，Closed表存放已扩展节点和待扩展结点。两个表的结构可以相同，大致如下表：
- 可根据需要扩展表的结构，比如加入代价字段等。
- 在数据结构中，常用数组visited[ ]标记结点是否已经访问。
- 图搜索（graph search）一般过程：
- 建立一个只含初始状态节点S的搜索图G，建立一个OPEN表，用来存放未扩展节点，将S放入OPEN表中；
- 建立一个CLOSED表，用来存放已扩展和待扩展节点，初始为空；
- LOOP：若OPEN为空，则失败、退出；
- 选择OPEN表中的第一个节点，将其移到CLOSED表中，称此节点为n节点；
- 若n为目标节点，则成功、退出；
扩展n节点，生成n的后继节点集合M=M1+M2+M3，其中n的后继结点分为3种情况。设M1表示图G中新结点（最新生成的）；M2在图G中已经存在，处于OPEN表中；M3在图G中已经存在，且已经在CLOSED表中：
（1）对M1型结点，加入到图G中，并放入OPEN表中，设置一个指向父节点n的指针；（DS中的未访问邻接点）
（2）对M2型结点，已经在OPEN中，确定是否需要修改父节点指针；（DS中已访问邻接点，但这个顶点的邻接点未搜索）
（3）对M3型结点，已经在CLOSED表中，确定是否修改其父结点指针；是否修改其后裔节点的指针；（DS中已访问邻接点，且这个顶点的邻接点都已经搜索过）
启发性信息和估价函数
- 1.启发信息
- 关于问题领域的，用来帮助搜索的信息。
- 2.启发信息按用途分类
1) 用于决定下一个要扩展的节点
总是选择最有希望产生目标的节点（邻接点）优先扩展，即OPEN表按此希望值排序。这类启发信息使用最为广泛。
2) 用于决定产生哪些子节点
扩展一个节点时，有选择的生成子节点（选择访问邻接点），有些明显无用或没有优势的子节点不让其产生出来。
3) 用于决定从搜索图中修剪或抛弃哪些节点
减小待搜索空间。
搜索图中，不访问这些顶点，或直接删除掉这些顶点。
A算法描述：
(1)把初始节点S放入Open表中，f(S)=g(S)+h(S)；
(2)如果Open表为空，则问题无解 ，失败退出；
(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；
(5)若节点n不可扩展，则转第(2)步；
(6)扩展节点n，生成其子节点ni(i=1, 2, …)，计算每一个子节点的估价值f(ni)(i=1, 2, …)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；
(7)根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；
(8)转第(2)步。
