作业13：读书报告
A搜索算法
在讨论A搜索算法之前首先需要说一下什么是启发式图搜索策略。启发式（heuristic）策略就是利用与问题有关的启发信息引导搜索。我们需要在状态空间中搜索，启发式就是一些列操作算子，能从状态空间中选择最有希望达到问题解的路径。
我们之所以要用启发式策略是因为：①由于在问题陈述和数据获取方面存在模糊性，可能会使一个问题没有一个确定的解，这就要求系统能运用启发式厕所做出最有可能的解释；②虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。穷尽式搜索策略如宽度优先或深度优先搜索，在一个给定的较实际的时空内很可能得不到最终的解，而启发式策略则通过引导搜索向最有希望的方向来降低搜索复杂度。
我们一般把启发信息分为三种：①陈述性启发信息；②过程性启发信息；③控制性启发信息。在这里我们主要选用控制性启发信息。
控制性的启发式信息如果引入一些控制信息，就能提高搜索的效率。在这里我们需要引入一个估价函数（Evaluation Function）。一般来说，定义估价函数f（n）定义为从初始结点经过n结点到达目的结点的路径的最小代价估价值，一般形式为f（n）=g（n）+h（n）。其中g（n）时从初始节点到n结点的实际代价，而h（n）是从n结点到目的结点的最佳路径的估计代价。因为实际代价g（n）可以根据已生成的搜索树实际计算出来，而估计代价h（n）是对未生成的搜索路径作某种经验性的估计，所以两者对于搜索算法效率的提高都十分有用。
A搜索算法就是f（n）=g（n）+h（n）运用的典型例子。
我们在启发式图搜索算法中需要引入两张表记录状态信息：一张open表，用于记录所有已经生成但是没有扩展的状态；在closed表中记录已扩展的状态。简单地说，就是open表用于记录已经搜索过并且没有被选中的路径和当前能选择的所有路径，而closed表用于记录已经被选中过的路径。需要注意，我们排列open表的时候依据是他的估值大小进行牌列，每次从表中优先取出启发估价函数值最小的状态加以扩展。
算法步骤和伪代码在没有具体的样例之前就展现会让人觉得一头雾水，所以先针对A搜索算法一个比较典型的案例：八数码问题来进行思路的引入。
八数码问题是这样的：我有一个3*3的九宫格，里面有1——8八个数字和一个空格，随机排列，我们现在需要经过有限次地移动空格，来让这几个数码排列成1在左上，八在一下面，空格在中间的蛇形样式。
具体的样例和操作过程如下：
这里的ABCD代表的是顺序，没有其他意思，后面括号中的数字为当前矩阵和目标矩阵相比较，有几个数字不在目标矩阵的位置。通过空格的每一步移动，就可以得到每一步之后不同选择的不同估计代价。在进行下一步之前首先需要比较每一种情况的估计代价，以此来确定走那一步，如果两个估计代价相同，则分别走，比较下一层的估计代价的大小。以此类推，直到达到目的矩阵。
当然，我们之前也介绍了open表和closed表来记录这个过程，那么下面就是这两个表格：
填表规则就是上述的规则。其中需要注意，这里D(5)这条路径虽然最后没有被选择继续走下去，但是依然被记录进了closed表，理由是因为这条路被选中过。
有了样例，就可以说一说步骤和伪代码了。
A搜索算法
——读《人工智能导论》——蔡逸源2017210904042
在讨论A搜索算法之前首先需要说一下什么是启发式图搜索策略。启发式（heuristic）策略就是利用与问题有关的启发信息引导搜索。我们需要在状态空间中搜索，启发式就是一些列操作算子，能从状态空间中选择最有希望达到问题解的路径。
我们之所以要用启发式策略是因为：①由于在问题陈述和数据获取方面存在模糊性，可能会使一个问题没有一个确定的解，这就要求系统能运用启发式厕所做出最有可能的解释；②虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。穷尽式搜索策略如宽度优先或深度优先搜索，在一个给定的较实际的时空内很可能得不到最终的解，而启发式策略则通过引导搜索向最有希望的方向来降低搜索复杂度。
我们一般把启发信息分为三种：①陈述性启发信息；②过程性启发信息；③控制性启发信息。在这里我们主要选用控制性启发信息。
控制性的启发式信息如果引入一些控制信息，就能提高搜索的效率。在这里我们需要引入一个估价函数（Evaluation Function）。一般来说，定义估价函数f（n）定义为从初始结点经过n结点到达目的结点的路径的最小代价估价值，一般形式为f（n）=g（n）+h（n）。其中g（n）时从初始节点到n结点的实际代价，而h（n）是从n结点到目的结点的最佳路径的估计代价。因为实际代价g（n）可以根据已生成的搜索树实际计算出来，而估计代价h（n）是对未生成的搜索路径作某种经验性的估计，所以两者对于搜索算法效率的提高都十分有用。
A搜索算法就是f（n）=g（n）+h（n）运用的典型例子。
我们在启发式图搜索算法中需要引入两张表记录状态信息：一张open表，用于记录所有已经生成但是没有扩展的状态；在closed表中记录已扩展的状态。简单地说，就是open表用于记录已经搜索过并且没有被选中的路径和当前能选择的所有路径，而closed表用于记录已经被选中过的路径。需要注意，我们排列open表的时候依据是他的估值大小进行牌列，每次从表中优先取出启发估价函数值最小的状态加以扩展。
算法步骤和伪代码在没有具体的样例之前就展现会让人觉得一头雾水，所以先针对A搜索算法一个比较典型的案例：八数码问题来进行思路的引入。
八数码问题是这样的：我有一个3*3的九宫格，里面有1——8八个数字和一个空格，随机排列，我们现在需要经过有限次地移动空格，来让这几个数码排列成1在左上，八在一下面，空格在中间的蛇形样式。
具体的样例和操作过程如下：
这里的ABCD代表的是顺序，没有其他意思，后面括号中的数字为当前矩阵和目标矩阵相比较，有几个数字不在目标矩阵的位置。通过空格的每一步移动，就可以得到每一步之后不同选择的不同估计代价。在进行下一步之前首先需要比较每一种情况的估计代价，以此来确定走那一步，如果两个估计代价相同，则分别走，比较下一层的估计代价的大小。以此类推，直到达到目的矩阵。
当然，我们之前也介绍了open表和closed表来记录这个过程，那么下面就是这两个表格：
填表规则就是上述的规则。其中需要注意，这里D(5)这条路径虽然最后没有被选择继续走下去，但是依然被记录进了closed表，理由是因为这条路被选中过。
有了样例，就可以说一说步骤和伪代码了。
总得来说，A算法并不难理解，在我看来，A算法更像是回溯算法的一种变体。在引入估计代价函数之后，算法思路也就更加清晰明朗。另外，如果我们加一个定义，h*（n）为状态n到目的状态的最优路径的代价，当A搜索算法的启发函数h（n）小于等于h*（n）时，被称为A*搜索算法。当前，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。
总得来说，A算法并不难理解，在我看来，A算法更像是回溯算法的一种变体。在引入估计代价函数之后，算法思路也就更加清晰明朗。另外，如果我们加一个定义，h*（n）为状态n到目的状态的最优路径的代价，当A搜索算法的启发函数h（n）小于等于h*（n）时，被称为A*搜索算法。当前，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。