人工智能
搜索问题在状态空间中，如何利用知识，通过一些搜索方式（盲目搜索或者启发式搜索）尽可能有效地找到问题的解，即找到最优解的问题。比如地图路径问题，华容道问题等。
盲目搜索盲目搜索一般分为两类，深度优先搜索和广度优先搜索。
深度优先搜索深度优先搜索的性质：
一般不能保证找到最优解深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况，搜索空间等同于穷举节省内存，之存储从初始节点到当前节点的路径广度优先搜索当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低存储量比较大启发式图搜索优先扩展“最佳”节点利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。
启发式搜索算法A/A*算法定义评价函数f(n)=g(n)+h(n)f(n)=g(n)+h(n)f(n)=g(n)+h(n)f∗(n)=g∗(n)+h∗(n)f^{*}(n)=g^{*}(n)+h^{*}(n)f∗(n)=g∗(n)+h∗(n)
g∗(n)g^{*}(n)g∗(n)从开始节点s到n的最短路径的消耗值。g(n)g(n)g(n)是g∗(n)g^{*}(n)g∗(n)的估计值h∗(n)h^{*}(n)h∗(n)启发函数。从指定区域n到目的地g的最短路径消耗值。h(n)h(n)h(n)是h∗(n)h^{*}(n)h∗(n)的估计值f∗(n)f^{*}(n)f∗(n)评价函数.从起点s经过n到目的地g的最短路径消耗值。f(n)f(n)f(n)是对f∗(n)f^{*}(n)f∗(n)的估计值用f(n)f(n)f(n)对扩展节点进行评价
openlist：从节点s开始，先把它加入到待计算的表(openlist).c从出发点起，与它相接的所有可以达到的节点，也加入到open表中closedlist：封闭列表。起点s从closedlist中移除。上一步的节点和不可行的节点，在close表中。
最佳图搜索算法A∗A^{*}A∗算法在A算法中，如果满足条件：h(n)≪h∗(n)h(n)llh^{*}(n)h(n)≪h∗(n)则A算法称为A∗A^{*}A∗算法
A算法步骤的总结(SummaryoftheAMethod)
把起点加入openlist。重复如下过程：a.遍历openlist，查找F值最小的节点，把它作为当前要处理的节点。b.把这个节点移到closelist。c.对当前方格的8个相邻方格的每一个方格？◆如果它是不可抵达的或者它在closelist中，忽略它。否则，做如下操作。◆如果它不在openlist中，把它加入openlist，并且把当前方格设置为它的父亲，记录该方格的F，G和H值。◆如果它已经在openlist中，检查这条路径(即经由当前方格到达它那里)是否更好，用G值作参考。更小的G值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的G和F值。如果你的openlist是按F值排序的话，改变后你可能需要重新排序。d.停止，当你◆把终点加入到了openlist中，此时路径已经找到了，或者◆查找终点失败，并且openlist是空的，此时没有路径。保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。上述步骤来自Colin丶的CSDN博客，全文地址请点击：https://blog.csdn.net/hitwhylz/article/details/23089415?utm_source=copy
对启发函数hhh的评价方法平均分叉数设共扩展了d层节点，共搜索了N个节点，则：N=(1−b∗(d+1))1−b∗b∗称为平均分叉数N=frac{(1-b^{*(d+1)})}{1-b^{*}}quadb^*称为平均分叉数N=1−b∗(1−b∗(d+1))b∗称为平均分叉数b∗b^*b∗越小，说明评价函数hhh效果越好。实验表明，b∗b^*b∗是一个比较稳定的常数，同一个问题基本不随问题规模发生变化。
随机搜索算法动态规划算法对于任何的n，当h(n)=0h(n)=0h(n)=0时，A*算法就成为了动态规划算法。
参考：清华大学计算机系马少平老师《人工智能》课程PPT课件