问题求解过程是 搜索答案（目标） 的过程，所以问题求解技术也叫做搜索技术——通过对 状态空间 的搜索而求解问题的技术。
问题可形式化地定义成四个组成部分
在解题过程中 达到过的所有状态 的集合。不同于状态空间，搜索空间是其中一部分。状态空间和搜索空间都属于 过程性知识表示 。
八数码问题详解
两种搜索技术
无信息搜索策略也称 盲目搜索 ：没有任何附加信息，只有生成后继和区分目标和非目标状态。
五种盲目搜索策略有：广度优先搜索，代价一直搜索，深度优先搜索，深度有限搜索，迭代深入深度优先搜索。
从四种度量来评价广度优先搜索
性能：通常使用递归函数实现，一次对当前节点的子节点调用该函数。相比广度优先，内存需求少(分支因子 * 最大深度+1)。但 不是完备的也不是最优的 *。
深度优先搜索的无边界问题可以通过提供一个 预先设定的深度限制I 来解决。深度=I的节点当作无后继节点看待；虽然解决了无边界问题，但 有可能无解 ； 如果选择I>d则深度优先原则也不是最优解 。
每次改变限制深度 ，多次调用深度有限搜索，当 搜索到达最浅的目标节点深度 时就可以发现目标节点，称为迭代深入深度优先搜索。这种搜索结合了广度优先和深度优先两种搜索方式的优势。 解决了深度优先的完备性问题 。空间需求是(b * d),时间需求是(b d )。当搜索空间很大且深度未知时，迭代深入深度优先搜索 是首选的无信息搜索方式 。
迭代深入搜索中因为多次重复搜索上层节点，使部分状态反复生成，看起来很浪费内存空间和时间。但是因为 在分支因子比较均衡的搜索树 中， 多数节点都是叶子节点 *（叶子节点数远大于上层节点总和），所以上层节点多次生成的影响并不大，与广度优先相比，效率还是很高。
用于目标状态已知，求解过程的问题。通常通过 广度优先搜索 实现。从 起始节点和目标状态两个方向 开始扩展，当 两个OPEN表出现交集 时表明搜索到了一条从起始到结果的一条路径。 缺点 ：算法编写难。但一旦实现，效率要远高于其他盲目搜索。
评价函数 ：f ( n ) = h ( n ) ；评价函数等于启发函数
解释：贪婪最佳优先搜索中 无条件选择 当前离目标最近（代价最小）的结点进行扩展。但是 局部最佳不是全局最佳，即非最优。 其中h（ n ）称为 启发函数 ，是从节点n到目标节点的最低代价的 估计值 。
评价函数 ：f ( n ) = g ( n ) + h ( n )；评价函数等于启发函数加路径耗散函数
解释：
另，对于有向图的搜索还可以采用图搜索方式。详情： 图搜索和树搜索详解
称启发函数是可采纳的，如果h( n ) 满足 h( n ) ≤ h * ( n ) ，其中 h * ( n )是从当前节点 n到达目标的最低真实代价 ，即h( n )的估值永远小于真实耗散值；因为f ( n ) = g ( n ) + h ( n )，且g（n）为已知常数，所以 f（n）永远不会高估经过结点n的解的实际代价 ，所以是最优解。
如果采用 A* 图搜索算法，则不一定返回最优解 。因为如果最优路径不是第一个生成的，可能因为有重复状态而被丢弃了。见上个链接： 图搜索和树搜索详解
如果对于每个结点n，以及n的行为a产生的后继结点n'满足如下公式： h ( n ) ≤ c ( n, n', a) + h( n ') （c ( n, n', a)可以理解为g（n'）），则称这个h ( n )启发函数是一致的。
A* 搜索由初始结点出发开始搜索，以同心带状增长f（n）耗散值的方式扩展结点。如果h（n）= 0 意味着只按g（n）值排序，即同心带为“圆形”。使用启发函数则同心带向目标节点拉伸（椭圆越来越扁）。
如果C*是最优路径的耗散值，则：
A* 搜索的关键就是 设计可采纳的或一致的（单调的）启发函数 。
绝不高估 到达目标的耗散值，尽可能的接近真实耗散值
子问题的解耗散是完整问题的 耗散下界 。
从实例中学习，每个实例包含了解路径上各状态及其到达解的耗散值。每个最优解实例提供了可学习h(n)的实例，由此产生可预测其他状态解消耗的启发函数。
联机搜索智能体需要行动和感知，然后扩展当前状态的环境地图
智能体初始位置在S，其已知信息为：
A* 搜索在不同子空间结点的跳跃式扩展， 模拟而非实际行动 ；联机搜索只扩展实际占据的结点——采用深度优先。 联机搜索必须维护一个回溯表
博弈搜索是智能体之间的对抗，每个智能体的目的是冲突的。本节需要解决两个问题：如何搜索到取胜的 路径 /如何提高搜索 效率 。相应的办法是 极大极小决策和α-β剪枝 。
两个智能体博弈时，可令一方为MAX，一方为MIN。MAX希望终局得分高，MIN希望终局得分低。
博弈搜索中，最优解是导致取胜的终止状态的一系列招数。MAX制定取胜策略时，必须不断考虑MIN应对条件下如何取胜。
如果博弈双方 都按照最优策略 进行，则一个结点的 极大极小值就是对应状态的效用值
简单的递归算法——按照定义计算每个后继结点的极大极小值/搜索是从目标到初始结点的 反向推导
如果博弈树最大深度为m，每个节点的合法招数为b，则
剪掉那些不可能影响最后决策的分支，返回和极大极小值相同的结果。
α-β剪枝可以应用树的任何深度。
如果在结点n的父节点或更上层有一个更好的选择m，则在搜索中永远不会到达n。
很大程度上取决于检查后继节点的次序—— 应先检查那些可能更好的后继 。如果能先检查那些最好的后继，则 时间复杂度为O(b (d/2) ) 。优于极大极小算法的O(b d )
许多问题中 路径是无关紧要的 。从当前状态出发，通常 只移动到相邻状态 ，且路径不保留。
内存消耗少，通常是一个常数。
向目标函数值增加的方向持续移动，直到相邻状态没有比它更高的值。 取到一个局部最优则终止 。
使新状态估计值优于当前状态值和其他所有候补结点值，则取新状态放弃其他状态。
将 爬山法 （停留在局部最优）和 随机行走 （下山）以某种方式结合，同时拥有 完备性和效率 。
技巧是，概率足够大可以弹出局部最优；但概率不能太大而弹出全局最优。
按照模拟退火的思想， T随时间逐渐减小 。如果 T下降的足够慢 ，则找到全局最优解是 完备的 。
随机移动，如果评价值改善则采纳； 否则以小于一的概率接受 。
从 k个随机生成的状态开始 ，每步生成k个结点的所有后继状态。如果其中之一是目标状态则停止算法；否则从全部后继状态中选择最佳的k个状态继续搜索。
有用的信息 在k个并行的 搜索线程之间传递 ，算法会很快放弃没有成果的搜索，而把资源放在取得最大进展的搜索上。
局部剪枝搜索的变种。因为局部剪枝搜索搜索是贪婪的，因而用随机剪枝搜索代替。不是选择最好的k个后代，而是按照一定概率选取k个后继状态。
类似于自然界的选择过程。状态对应个体，其 值对应适应性 ，后代就是状态。因此如果k个状态缺乏多样性，则局部搜索会受影响。
局部剪枝算法已有 群体进化 （优胜劣汰）的趋势。遗传算法是随机剪枝的变种。
包括选择，交叉和变异
又称繁殖，按照一定的概率选择两对个体生成后继状态
计算每个个体i被选中的概率： pi = f(i) / [f(1)+...+f(n)] .然后根据概率将圆盘分为n个扇形，每个扇形大小为 2Πpi 。
繁殖过程中，后代是父串在杂交点上进行杂交得来的。这样一来，后代子串保留了父串的优良特性又与父串不同。
首先以概率p随机在种群中选择pa和pb两个个体，再从{1,2,...,m}中（可以按一定概率，如两边概率小于中间概率）选择一个数i，作为交叉点。而后将两个个体的交叉点后面的部分交换。
在新生成的后继状态中各个位置都会按照一个 独立的很小的概率 随机变异。
变异时要做到 一致变异 ；即相同概率地变异所有个体的每一位。
结合了“上山”和随机行走，并在并行搜索线程之间交换信息。遗传算法的 最大优点在于杂交 。因为杂交可以 将独立发展的若干个砖块组合起来 ，提高搜索的粒度。
个体编码某些位置上数字仍未确定的一个状态子串。
如果 一个模式的实例的平均适应值超过均值 ，则种群内这个模式的实例数量会随时间而增长（优胜）；反之则减少（劣汰）
长度较短，高于平均适应度的模式在遗传算子的作用下， 相互结合 ，能生成长度较长、适应度较高的 模式 。
Constraint Satisfying Problem，CSP。
由一个 变量集合{X1~Xn} 和一个 约束集合{C1~Cn} ；每个变量都有一个 非空可能的值域Di 。每个约束指定了 若干变量的一个子集内各变量的赋值范围 。
CSP的一个状态是，对一些或每个变量赋值
一组既是 相容赋值 又是 完全赋值 的对变量的赋值就是CSP的解。
提前考虑某些约束，以减少搜索空间
若X被赋值，检查与X相连的Y，判断是否满足约束，去掉Y中不满足约束的赋值。（进行某种检验，可以不为有问题的Y集合赋值 ）