搜索算法笔记

一、搜索的基本概念

搜索的基本概念

搜索的定义：根据已有的知识以及问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。图搜索一种在图中寻找路径的方法图中每个节点对应一个状态，每条连线对应一个操作符。图搜索是各种搜索策略的常见应用场景。

搜索的本质：从隐式的状态空间图中不断生成显示的搜索图和搜索树，最终找到路径的过程。 搜索的适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；没有现成的算法可供求解使用。

搜索的类型

按是否使用启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。

按问题的表示方式：状态空间搜索：用状态空间法求解问题进行的搜索 与或树搜索：用问题归约法求解问题进行的搜索

二、状态空间搜索

状态空间搜索的基本思想

先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点。然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。对一个节点进行“扩展”：对该节点用某个可用操作进行作用，生成该节点的一组子节点。

状态空间搜索算法的符号约定

OPEN表：待扩展节点表，用于存放待扩展的节点（下一步可以走哪些点）

CLOSED表：已扩展节点表，用于存放已经扩展的节点（记录哪些点已经走过了）

S：用表示问题的初始状态

G：表示搜索过程所得到的搜索图

M：表示当前扩展节点新生成的且不为自己先辈的子节点集

状态空间搜索算法的数据结构

STATE：节点所表示状态的基本信息

PARENT NODE：指针域，指向当前节点的父节点

ACTION：从父节点表示的状态转换为当前节点状态所使用的操作

DEPTH：当前节点在搜索树中的深度

PATH COST：从起始节点到当前节点的路径代价

图搜索的一般过程

(1) 把初始节点S放入未扩展节点表OPEN表，并建立目前仅包含S的图G；

(2) 检查OPEN表是否为空，若为空，则问题无解，失败退出；

(3) 把OPEN表的第一个节点取出放入已扩展节点表CLOSED表，并记该节点为节点n；

(4)考察节点n是否为目标节点。若是则得到了问题的解，成功退出。此时的解为追踪图G中沿着指针（步骤6中设置的指针）从n到初始节点S的路径。

(5) 扩展节点n，生成一组子节点。把这些子节点中不是节点n先辈 的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中

(6) 针对M中子节点的不同情况，分别作如下处理：

① 对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入OPEN表。（新生成的）

② 对那些原来已在G中出现过，但还没有被扩展的M成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）

③ 对于那些先前已在G中出现过，并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的） 寻找更优路径

(7) 按某种策略对OPEN表中的节点进行排序。

(8) 转第(2)步。

图搜索的一般过程的几点说明

各种搜索策略的主要区别在于对OPEN表中节点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。

在第(6)步如果发生当第②种情况，一般是看原始节点到该节点路径上所付出的代价，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。

如果发生第③种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其一般依据也是由原始节点到该节点的路径上的代价。

在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。

三、盲目搜索

盲目搜索的基本概念

按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。大多数情况下不需要对OPEN表进行重排

盲目搜索的分类

状态空间的广度优先搜索

广度优先搜索的基本思想：从初始节点S开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。未扩展节点表OPEN表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。

广度优先搜索算法流程：

(1) 把初始节点S放入OPEN表中；

(2) 如果OPEN表为空，则问题无解，失败退出；

(3) 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n

(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；

(5) 若节点n不可扩展，则转第(2)步；

(6) 扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。

可重复访问

状态空间的深度优先搜索

深度优先搜索的基本思想：

从初始节点S开始，在其子节点中选择一个最新生成的节点进行考察 如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察 依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。

深度优先搜索算法流程：

(1) 把初始节点S放入OPEN表中；

(2) 如果OPEN表为空，则问题无解 ，失败退出；

(3) 把OPEN表的第一个节点取出放入CLOSED表，并记该节点为n，将子节点（未访问过）加入OPEN表的首部，对子节点进行"放松"；

(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；

(5) 若节点n不可扩展，则转第(2)步；

(6) 扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点设置 指向父节点的指针，然后转第(2)步。

状态空间的等代价搜索

等代价搜索是广度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。

等代价搜索算法流程：

(1) 把初始节点S放入OPEN表中；

(2) 如果OPEN表为空，则问题无解 ，失败退出；

(3) 从OPEN表中选择一个节点i，使其g(i)最小。如果多个节点都符合，那么就选择一个目标节点作为节点i(要是有目标节点的话)；否则，就从中选一个作为节点i。把节点i从OPEN表移CLOSED表中；

(4) 考察节点i是否为目标节点。若是，则得到问题的解，成功退出；

(5) 若节点i不可扩展，则转第(2)步；

(6) 扩展节点i，对于节点i的每个后继节点j，计算g(j)=g(i)+c(i，j)，并把所有后继节点j放进OPEN表。提供回到节点i的指针，然后转第(2)步。

四、启发式搜索

启发式搜索的定义：在搜索过程中，使用有关具体问题领域特性的启发信息，将待扩展节点进行排序并对最有希望的节点加以扩展。该搜索也被称为有信息搜索。

启发式搜索的术语

启发信息：包括：

用于决定待扩展的节点（最常用）： 总是选择最有希望产生目标的节点（邻接点）优先扩展，即OPEN表按此希望值排序。

用于决定待产生的子节点： 扩展一个节点时，有选择的生成子节点（选择访问邻接点），有些明显无用或没有优势的子节点不让其产生出来。

用于决定从搜索图中被修剪或抛弃的节点 ：减小待搜索空间。搜索图中，不访问这些顶点，或直接删除掉这些顶点。

估价函数：用于评估节点重要性的函数；其一般形式为： f(x) = g(x)+h(x)

f(x) 决定节点在OPEN表中的次序

其中：g(x)为从S到x，已经走过的路径代价估计，通常为当前路径花费代价。

启发函数：上式中的h(x)是启发函数。h(x)是从x到达目标G代价的估值，这一段路径是没有走过的，必须根据问题特性，利用启发信息进行估算。

有序搜索

有序搜索的定义：在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为有序搜索算法。

有序搜索又叫最好优先搜索或A算法。

有序搜索的特点：有序搜索总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按估价函数f(x)的值来挑选的，一般估价函数的值越小它的希望程度越大。

局部择优搜索

局部择优搜索的特点：局部择优搜索是对深度优先搜索方法的一种改进。

局部择优搜索的基本思想：当一个节点被扩展以后，按f(x)对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点。

局部择优搜索过程

(1) 把初始节点S放入OPEN表，计算f(S)；

(2) 如果OPEN表为空，则问题无解，退出；

(3) 把OPEN表的第一个节点（记为节点n）取出放入CLOSE表；

(4) 考察节点n是否为目标节点。若是，则求得了问题的解，退出；

(5) 若节点n不可扩展，则转第2步；

(6) 扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值从小到大的顺序放到OPEN表中的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。

全局择优搜索

每当要选择下一个节点进行考察时，全局择优搜索每次总是从OPEN表的全体节点中选择一个估价值最小的节点。

全局择优搜索过程

(1) 把初始节点S0放入OPEN表，计算f(S0)；

(2) 如果OPEN表为空，则问题无解，退出；

(3) 把OPEN表的第一个节点（记为节点n）取出放入CLOSE表；

(4) 考察节点n是否为目标节点。若是，则求得了问题的解，退出；

(5) 若节点n不可扩展，则转第(2)步；

(6) 扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序，然后转第(2)步。

代价=从源点路径+h距目的点距离

A*算法

A*算法的限制条件：

f(n)=g(n) +h(n)

1）g(n)>0； 2）对任意节点n均有h(n)≤n到目标的实际代价；

A*算法的最优性：

h(n)的确定依赖于具体问题领域的启发性信息，其中h(n) ≤h*(n)的限制非常重要，它可以保证A*算法能找到问题的最优解。

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