# 1. 搜索概念
搜索中需要解决的基本问题：
（1）是否一定能找到一个解。
（2）找到的解是否是最佳解。
（3）时间与空间复杂性如何。
（4）是否终止运行或是否会陷入一个死循环。
搜索的主要过程：
(1) 从初始或目的状态出发，并将它作为当前状态。
(2) 扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针 。
(3) 检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第 (2) 步再进行搜索。
依据搜索方向：
(1) 数据驱动：从初始状态出发的正向搜索
正向搜索 —— 从问题给出的条件出发
(2) 目的驱动：从目的状态出发的逆向搜索。
逆向搜索：从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。
(3) 双向搜索
双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。
依据搜索算法：
- 盲目搜索
按固定方式依次进行 - 启发式搜索
根据启发函数优先选择合适的操作算子
# 2. 状态空间表示法
状态：表示系统状态、事实等叙述型知识的一组变量或数组
操作：表示引起状态变化的过程型知识的一组关系或函数
利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：(S,O,S0,G)
S: 状态集合
O: 操作算子集合
S0: 包含问题的初始状态为 S 的子集
G: 若干具体状态或满足某些性质的路径信息描述。
# 3. 盲目搜索策略
# 1. 回溯搜索 Traceback
从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或 “不可解结点”，即 “死胡同” 为止。
若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。
(1) PS（path states）表：保存当前搜索路径上的状态。如果找到了目的，PS 就是解路径上的状态有序集。
(2) NPS（new path states）表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展 。
(3) NSS（no solvable states）表：不可解状态集，列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。
（1）用未处理状态表（NPS）使算法能返回（回溯）到其 中任一状态.
（2）用一张 “死胡同” 状态表（NSS）来避免算法重新搜索无解的路径.
（3）在 PS 表中记录当前搜索路径的状态，当满足目的时可以将它作为结果返回.
（4）为避免陷入死循环必须对新生成的子状态进行检查，看它是否在该三张表中.
# 2. 宽度优先搜索 BFS
逐层进行搜索，一种高价搜索，但是若解存在，则必定能找到
OPEN 表 (NPS) 保存已经生成出来但子状态未拓展的状态，先进先出
CLOSED 表 (PS 和 NSS) 记录已经被生成拓展的状态
# 3. 深度优先搜索 DFS
扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；仅当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径。
防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度 —— 深度界限；
与宽度优先搜索算法最根本的不同：将扩展的后继节点放在 OPEN 表的前端。
深度优先搜索算法的 OPEN 表后进先出。
# 4. 启发式搜索
用来简化搜索过程有关具体问题领域的特性的信息叫做启发信息
启发式图搜索策略（利用启发信息的搜索方法）的特点：重排 OPEN 表，选择最有希望的节点加以扩展。
运用启发式策略的两种基本情况：
- 一个问题由于存在问题陈述和数据获取的模糊性，可能会使它没有一个确定的解。
- 虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。
估价函数（evaluation function）：估算节点 “希望” 程度的量度。
估价函数值 f (n) ：从初始节点经过 n 节点到达目标节点的路径的最小代价估计值，其一般形式是
g (n): 从初始节点 S0 到节点 n 的实际代价
h (n): 从节点 n 到目标节点 Sg 的最优路径的估计代价，称为启发函数。
# 1. A 搜索算法 (未必找到解)
利用了估价函数的最佳优先搜索策略，根据 f (n) 来进行拓展结点
# 2. A * 算法 (一定找到解)
在 A 算法基础上，对于 h (n) 启发函数进行优化，采用单调启发函数，且目的状态的启发函数为 0
