一．数据驱动和目标驱动搜索
（1）目标或假设是在问题陈述中给出的。例如定理的证明，目标就是定理。
（2）与问题数据匹配的规则非常多，会产生大量分支。
（3）问题数据不是给定的，目标驱动搜索可以引导如何获取数据。
以下情况建议使用数据驱动搜索：
（1）问题的初始陈述给出了所有或大部分数据。
（2）潜在目标的数量非常庞大。
（3）难以组成目标或假设。
总而言之，要考虑的主要因素就是分支因子（即每个方向新状态的平均数量）。
二．盲目搜索
1.回溯搜索
回溯搜索就是从起始状态出发沿一条路径前进，要么达到目标，要么到达死端。如果到达死端，它便回溯到路径上含有尚未分析过兄弟的最近节点。这种回溯思想被应用到其他算法。
2.宽度优先搜索
（1）把起始节点放到OPEN表中；
（2）如果OPEN表是个空表，则失败退出，否则继续；
（3）把第一个节点n从OPEN表中取出，放入CLOSE表中；
（4）扩展节点n，如果没有后继节点，则转向（2）；
（5）把n的后继节点中不在OPEN和CLOSE表中的放到OPEN表的末端，这些后继节点要有指向父节点n的指针；
（6）如果n的任意一个后继节点是一个目标节点，成功推出；否则，转向（2）。
显而易见，宽度优先搜索方法能够保证找到一条到目标节点的最短路径。
递归形式的宽度优先搜索略。
3.深度优先搜索
含有深度界限的深度优先搜索：
（1）把起始节点放到OPEN表中；
（2）如果OPEN表是个空表，则失败退出，否则继续；
（3）把第一个节点n从OPEN表中取出，放入CLOSE表中；
（4）扩展节点n，如果节点n的深度等于最大深度，或者n没有后继节点，则转向（2）；
（5）把n的后继节点中不在OPEN和CLOSE表中的放到OPEN表的首端，这些后继节点要有指向父节点n的指针；
（6）如果n的任意一个后继节点是一个目标节点，成功推出；否则，转向（2）。
可以看出，与宽度优先的唯一区别就是新节点放在open表的开始还是结尾。
分支过程：如果含有多条路径，要找最优，则可以简单地利用分支过程降低复杂度。找到目标后，记录下路径长度为MIN，若搜索到的节点路径大于MIN，则放弃搜索，回溯到其他节点；如果小于MIN，这把较小值赋给MIN。
递归形式的深度优先搜索算法：
OPEN和CLOSE为全局变量；
Depthsearch（）{
如果OPEN表为空，return fail；
current=OPEN中的第一个值；
If(current==goal) return success;
else{
从OPEN表中移除current，放入CLOSE表中；
把current的孩子节点中的不是OPEN和CLOSE表中的添加到OPEN的开头；
}
Depthsearch（）；
}
还可以进一步简化这个过程：用递归本身来组织状态空间中的状态和路径，而不用显式的OPEN表，用全局变量CLOSE来探测重复状态并防止死循环：
CLOSE为全局变量；
Depthsearch（）{
if (current==goal) return success;
Add current to CLOSE;
While(current has unexamined child){
Child =next unexamined child;
If (child not a member of closed){
If(depthsearch(child)==success) return success;
}
}
Return fail;
}
4.等代价搜索
寻找具有最小代价的解答路径，是宽度优先搜索的推广：
（1）把起始节点放入OPEN表中，如果是目标节点，则成功退出，否则令g(s)=0；
（2）如果OPEN是空表，则失败退出；
（3）从OPEN表中选择一个g(i)最小的节点，如果几个节点都合格，有目标节点就选目标节点成功退出，否则选一个节点i从OPEN表中移出放入CLOSE表中；
（4）扩展节点i，如果没有后继节点，则转向第（2）步；
（5）对于节点i的每个后继节点j，计算g(j)=g(i)+c(i,j)，并把所有后继节点j放入OPEN表中，提供回到节点i的指针；
（6）转向第（2）步。
5.与或图搜索
与常规的图搜索相比，与或图搜索需要多保存一些记录。检查或后继节点的方法与回溯中一样：一旦找到了沿或节点把目标连接到起始节点的一条路径，那么这个问题就解决了。如果一条路径失败，那么算法可以回溯并试验另一个分支。在检查与节点时，要证明与节点为真就必须证明这个节点的所有与后继都为真。
下面给出目标驱动的深度优先的与或图搜索算法：
先定义节点：
class Node{
Node Parent; //指向父节点指针
Int Value; //False=0,True=1,不确定=2
Int type; //当前节点类型，与=0，或=1
Int child_number; //子节点数目
Int child_check; //已检查子节点数目
}
在建立图时，把节点转换成纯粹的与节点或者或节点，例如：
（1）把头结点放入OPEN表中，如果头结点为真或假，则成功退出；
（2）如果OPEN为空则失败退出，如果头结点为真或假，则成功退出；
（3）移出OPEN中第一个元素i，放入CLOSE中，current=i；
（4）如果current为真：
a.父节点是与，把父节点已检查子节点数目加一，如果父节点已检查数目等于父节 点的子节点数目，则current=父节点，返回（2）；
b.父节点是或，父节点为真，current=父节点，并删除current在OPEN表中的所有 子节点，返回（2）；
(5)如果current为假：
a.父节点是与，父节点为假，current=父节点，并删除current在OPEN表中的所有子节点，返回（2）；
b.父节点是或，把父节点已检查子节点数目加一，如果父节点已检查数目等于父节点的子节点数目，则父节点为假，current=父节点，返回（2）；
（6）如果current不确定：
a.如果还有子节点，把子节点放入OPEN表中，返回（2）；
b.如果没有子节点，则让current为假，返回（5）；
三．启发式搜索
1.估价函数f(n)
f(n)=g(n)+h(n)
其中，g(n)是从任意状态n到起始状态的路径长度，h(n)是状态n到目标距离的启发性估计。估价函数的g(n)分量是这种搜索带有更多的宽度优先性，这防止了搜索被错误的评估所误导：如果启发对一条无法到达目标的路径上的状态连续给出“好的”评估，那么g值会上升来控制f，从而迫使搜索返回一条较短的解路径，这保证算法不会永久迷失。
当然，也可以让g(n)=0,来更快地找到目标；或则让h(n)=0，就是宽度优先搜索。
2.A算法
算法如下：
与宽度优先搜索不同之处就是：要对对OPEN表中的所有元素按照f进行排序，如果某个节点已经存在于OPEN或CLOSE表中，如果f值较小，则修改已存在节点的f值。还可以把OPEN和CLOSE表维护为堆或左撇子树来提高效率。
3.A星算法
我们定义一个估价函数：f星(n)=g星(n)+h星(n)
其中：g星(n)是从起始节点到节点n的最短路径代价，h星(n)是从n到目标的最短路径的实际代价。这样f星(n)就是从起始节点经过节点n到达目标的最优路径的实际代价。
可采纳的算法：如果在任何图中只要存在从起始节点到达目标状态的最优路径，搜索算法就可以找到这样的路径，那么这个算法就是可采纳的算法。
算法：如果在A算法中使用的评估函数满足h(n)<=h星(n)，这种算法就称为A星算法。
所有的S星算法都是可采纳的。
四．博弈中的启发式搜索
1.可穷举搜索的极小极大过程
在状态可以穷举的博弈中，主要难点是如何考虑对手的动作。一简单方式是假定对手具有相同的关于状态空间的知识。MAX代表棋手，MIN代表对手，MAX总是最大化他的优势，MIN总是使MAX的优势最小。
如下图所示，每个叶子节点有一个0和1的值，代表MIN取胜或MAX取胜。极小极大搜索根据下面的规则沿连续的父节点向上传播这些值：
如果父节点是一个MAX节点，那么把孩子中的最大值赋给它；如果父节点是一个MIN节点，那么把孩子中的最小值赋给它。于是赋给每个状态的值表示了这个棋手可以期望达到的最佳状态值，算法就按此值来选择移动方法。
2.固定层深的极小极大过程
即探索到n层，然后给每个叶子节点赋一个启发值。
3.a-b过程
即对固定层深的极小极大搜索过程进行修剪。
它与分支过程思想类似：先沿着一条路径搜索到底，比如搜索完A,B,E,K,L后，E的值为3，由于F最小为5，故F的另一个分支就不用再搜索。同样，由于B的值为3，而C的值最大为0，故C的另一个分支也不用再搜索，D的另一个分支也不用再搜索。
