人工智能笔记之搜索算法（盲目搜索、启发式搜索）

1.搜索算法是很多优化和规划问题问题的基础，很多问题的解决都依赖于搜索策略。 2.把一个问题转化为搜索问题（即问题的形式化）需要： 将问题表示为状态（STATES）和操作算子（OPERATORS）的集合，操作算子可以将问题由一个状态转化为另一种状态。利用不同的操作算子将问题从初始状态转化到目标状态，所有这些操作算子的序列即为问题的一个解。因此，我们要想找到一个问题的解就是在状态空间中找到连接初始状态和目标状态操作算子序列。

深度优先搜索（Depth-first search）： 按照深度优先方式遍历搜索空间，但是这种方式可能会使遍历一直在非目标状态方向上深度遍历，导致找不到解。 广度优先搜索（Breadth-first search）： 广度优先搜索始终可以保证找到问题的解，但时间和空间消耗较大。 迭代搜索（Iterative deepening search）： 考虑到深度优先搜索不一定可以找到问题的解，但是可以将深度优先和广度优先向结合，即为其添加深度限制。当深度遍历到一定的深度还是找不到解时使搜索方向转到其他状态分支继续深度遍历，使受限制的层数不断增加直到找到问题的解。

A*算法： 为搜索提供一些可知信息（knowledge），可使搜索的方向性更强，避免一些不必要的状态的扩展，节约时间和空间。考虑当当前状态与目标状态相似度最高时，可以更快找到解，因此引入评估函数f(n)=h(n)+g(n)，其中h(n)为当前状态和目标状态不同棋子的个数，g(n)为当前状态的深度。f(n)值最小的是和目标状态最接近的状态，因此优先扩展。 加强评估函数的A*算法： 考虑到棋子移动的步数也是可知的并且会影响扩展序列个数的因素，因此设f(n)=h(n)+g(n)，其中h(n)为每个棋子当前状态到达目标状态的步数和，g(n)为当前状态的深度。这样可以进一步减少不必要的扩展。

为使各搜索算法更便于实现，将这些算法整合为一般图搜索算法 创建open表（存储待扩展序列）和close表（存储已扩展序列），几种算法的不同只在于入表和出表的方式和排序方法

实现代码 1.盲目搜索（广度优先搜索算法） 按照广度优先遍历九宫格的所有可能状态：

2.盲目搜索（深度优先搜索算法） 按照普通深度优先遍历九宫格的所有可能状态：

如图所示，深度优先遍历不一定能找到正确的结果，因为搜索可能会在非目标状态的分支里一直深度遍历。因此考虑增加层数限制，使得在搜索某分支的固定层数后无解时可以返回继续遍历其他分支 3.盲目搜索（迭代搜索算法） 规定层数为10：

规定层数为50：

4.启发式搜索（A*搜索算法） 规定评估函数f(n)=h(n)+g(n)， 其中h(n)为当前状态和目标状态不同棋子的个数，g(n)为当前状态的深度：

5.启发式搜索（加强启发条件的A*搜索算法） 规定评估函数f(n)=h(n)+g(n)， 其中h(n)为每个棋子当前状态到达目标状态的步数和，g(n)为当前状态的深度： 各搜索算法对比：

由上表对比数据可知：