1、通过搜索进行问题求解

一个问题由5部分组成：初始状态，行动集合，转移模型，目标测试函数，路径代价函数。问题的环境用状态空间表示。状态空间中从初始状态到达目标状态的路径是一个解。
可以从完备性、最优性、时间复杂度和空间复杂度等方面来评价一个搜索算法。
主要分为：无信息搜索策略（盲搜）、有信息搜索策略（启发式搜索）
无信息搜索策略（盲搜）：
- 　　宽度优先
- 　　一致代价搜素（借助一个最小堆，每次选择代价最小的状态前进），类似dijkstra
- 深度优先搜索
- 迭代加深搜索（加一个深度限制）
- 双向搜索（在起点和终点分别进行宽度优先或者迭代加深的深度优先，直到两个圆相交）
　　有信息的搜索（一般的最佳优先搜索，需要访问启发式函数 h(n) 来估算从n到目标的解代价）
- 　　贪婪最佳优先搜索选择扩展 h(n)最小的结点（比如旅行问题中，每一步选择各个临结点中距离目标结点最近的结点），可能不是最优解。
- A*搜索：扩展 f(n) = g(n) + h(n)最小的结点。
  - 　　h(n)的选择，保证是最优解：1）可采纳性 2）一致性（单调性）。
  - 例如：旅行问题中： f(n) = g(n) + h(n)，在一致代价搜索的基础上，加了一个更快接近目标的启发函数，来缩短找到问题解的时间。
  - f(n) = 经过结点 n 的最小代价解的估计代价；g(n) = 从开始结点到结点n的路径代价，而h(n) = 从结点n到目标结点的最新代价路径的估计值（在这里采用直线距离）　
  - 在这里，f(n+1) >= f(n)

- 递归最佳优先搜索RBFS，只保留最新的可能要回退的结点，所以占用内存为线性空间
　　总结：启发式搜索算法的性能取决于启发式函数的质量，好的启发式有时可以通过松弛问题的定义来构造，将子问题的解代价记录在模式数据库中，或者通过对问题类似的经验学习得到。
例如：