《人工智能导论》第三章：通过搜索对问题求解(笔记二)
第三章通过搜索对问题求解一.问题求解Agent二.问题实例三.树搜索算法四.无信息搜索策略（必考知识）4.1宽度优先搜索4.2一致代价搜索！！！4.3深度优先搜索4.4深度受限搜索！！！4.5迭代加深的深度优先搜索！！！五.有信息(启发式)的搜索策略5.1最佳优先搜索!!!5.2一致代价搜索-分支定界法5.3A搜索5.4A*搜索三个感叹！表重点一.问题求解Agent搜索为一种求解问题的一般方法。搜索问题：已知一个问题的初始状态和目标状态，找到一个操作序列，使得问题的状态能从初始状态转移到目标状态。最优搜索问题：获得的操作序列不仅是问题的解，而且使得总代价最低。搜索问题特点：（1）初始状态确定（2）当前状态是否为目标转态是可检测的（3）状态空间离散（4）每个状态可以采取的合法行动和相应后继状态是确定的（5）环境是静态的（6）路径代价函数是已知的典序搜索问题（1）八数码难题（2）旅行售货员问题搜索问题四个要素：（1）初始状态（2）后继函数：某个行动输入给定状态，可以输出相应的后继状态（3）目标测试：给定状态是否为目标状态（4）路径代价函数：状态转移所需的代价搜索中需要解决的基本问题：（1）是否一定能找到一个解。（2）找到的解是否是最佳解。（3）时间与空间复杂性如何。（4）是否终止运行了或是否会陷入一个死循环。搜索的主要过程：（1）从初始或目的状态出发，并将它作为当前状态。（2）扫描操作的算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针。（3）检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出解答的路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。搜索策略盲目搜索启发式搜索在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。按搜索方向进行分类：(1)数据驱动：从初始状态出发的正向搜索。正向搜索——从问题给出的条件出发。(2)目的驱动：从目的状态出发的逆向搜索。逆向搜索：从想达到的目的入手，看哪些操作算子能产生该目的，以及应用这些操作算子产生目的时需要哪些条件。(3)双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。二.问题实例实例：Romania（1）已知条件：一个agent在罗马尼亚度假，目前位于Arad城市，Agent明天有航班从Bucharest起飞，不能改签退票（2）（3）真空吸尘器三.树搜索算法基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败)。树表示（1）根节点：初始状态（2）连线：行动（3）结点：状态空间中的状态算法性能评价标准（1）完备性：如果问题有解时，这个算法是否能保证找到解？（2）最优性：能否找到最优解（3）时间复杂度：找到解需要花费多长时间（4）空间复杂度：在执行搜索的过程中需要多少内存时间空间复杂度的度量：（1）时间由搜索过程中产生的结点数目来度量（2）空间由内存中存储的最多结点数量来度量（通常小于状态空间数量|V|+|E|）四.无信息搜索策略（必考知识）无信息搜索：除了问题定义中提供的状态信息外没有任何附加信息，算法只能区分状态是不是目标状态，无法比较非目标状态的好坏。
4.1宽度优先搜索思想：先扩展根结点，再扩展根结点的所有后继，然后再扩展它们的后继。实现：FIFO队列缺点：内存需求大，时间复杂度高4.2一致代价搜索！！！定义：扩展未扩展结点中代价最小的实现：队列按照代价从小到大排列4.3深度优先搜索思想：首先扩展最深的为扩展结点实现：用LIFO队列(栈)来存储结点4.4深度受限搜索！！！对于深度为d+1，分支数为b的情况，深度受限的搜索算法产生的结点数为：N(DLS)=b0+b1+…+bd4.5迭代加深的深度优先搜索！！！1.结合了宽度优先和深度优先的优点2.对于深度为d+1，分支数为b的情况，迭代加深的深度优先算法产生的结点数为：N(IDS)=(d+1)+(d)b+(d-1)*b2+….+(1)bd
五.有信息(启发式)的搜索策略无信息搜索的缺点：（1）广度优先搜索在进一步深入搜索之前先检查了靠近跟的节点，存储空间需求过高，很容易就被中等大小的分支因子给压垮了，例如分支因子=4（一个节点有四个孩子），则k层总共（4^k-1）/3个节点。（2）深度优先搜索（3）在求解"组合爆炸"的问题时，搜索空间增长太快(如从9！变成16！,！为阶乘)，以至于盲目搜索方法无法成功。启发法：一种解决问题的方法，这种方法通过尝试来证明结果，是**“凭经验"或"试错法”**的学习方式。（1）是一个提高复杂问题解决效率的实用策略，它引导程序沿着一条最可能的路径到达解，忽略最没有希望的路径，能避免去检查死角。（2）只使用已收集的数据。（3）可以减少结点数目，适合组合复杂度快速增长的问题（4）好的启发式方法不能保证获得解，但是它们经常有助于引导人们达到解的路径。5.1最佳优先搜索!!!基本思路：通过对每一个结点计算评价函数f(n)值,找到一个f(n)最低的未扩散的结点实现：在队列中，结点按照评价函数值从低到高排序。（大多数评价函数由启发函数h构成，h(n):结点n到目标结点的最小代价估计值）最佳优先搜索实现需要open表和closed表，open表中节点按照节点接近目标状态的启发式估计值进行顺序排列，过程中不保留重复状态。伪代码//最佳优先搜索BestFirstSearch(Root_Node,goal){建open表，将根节点插入open表;while(open表不为空){从open表中取出最前节点放在节点G中(同时加入closed表);if(G是目标节点)return从根节点到G节点一条路径;while(G是子节点){if(子节点不在open表中)将子节点插入open表;else将具有最小估计值的子节点放入open表，删除其他节点;}将open表中节点按值排序;//最小值节点在最前}return失败;}分类：贪婪最佳优先搜索罗马尼亚问题首先扩展与目标结点估测距离最近的结点使用两点之间的直线距离来估测两点之间的实际距离罗马尼亚问题例子:5.2一致代价搜索-分支定界法是不采用剩余距离的启发式搜索，只计算已经走过的部分，h(n)处处为0。按照递增的代价制定搜索路径，搜索的估计成本为：f(n)=g(n)结束条件：其它路径（未到达目标节点）的代价大于or等于当前最优的路径代价。伪代码//分支定界搜索Branch_Bound(Root_Node,goal){创建open表;将根节点插入open表;while(open表不为空){取出open表中第一个元素放入结点G;if(G是目标结点)return到G的路径else将G结点子节点插入open表;按照从根节点到当前节点的路径长度对open表排序;}return失败;}例子：一致代价搜索和最佳优先搜索都是通过启发函数排最优值，它们的区别如下最佳优先搜索一致代价搜索优先值为结点到终点的估计值优先值为结点到起点的真实值估价函数为h(n)估价函数为g(n)5.3A搜索是最佳搜索和一致优先的混合搜索算法，既考虑与源点的真实距离又兼顾与目标点距离的预估值。评价函数f(n)=g(n)+h(n)g(n)=到达结点n已经花费的代价h(n)=结点n到目标节点的评估代价f(n)=通过结点n到达目标结点的总评估代价伪代码B_B_Estimata(Root_Node,goal){创建open表;将根节点插入open表;while(open表不为空){取出open表中第一个元素放入结点G;if(G是目标结点)return到G的路径else将每个子节点的估计距离加到当前距离;将节点G的子节点插入open表按照路径长度对open表排序;}return失败;}例子最佳优先搜索、一致搜索及A算法均****没有对估价函数f(n)做任何限制**5.4A*搜索1.A*算法是最优A搜索算法，其是对估价函数加上一些限制后得到的一种启发式搜索算法。2.伪代码
A*Search(Root_Node,goal){创建open表;将根节点插入open表;while(open表不为空){取出open表中第一个元素放入结点G,并标记G已被访问;if(G是目标结点)return到G的路径else将每个子节点的估计距离加到当前距离;将节点G的子节点中之前未访问过的节点插入open表按照路径长度对open表排序;}return失败;}人工智能搜索策略：A*算法
人工智能搜索策略：A*算法目录人工智能搜索策略：A*算法A算法1.全局择优搜索2.局部择优搜索A*算法1.A*算法的可纳性2.A*算法的最优性3.h(n)的单调限制A*算法应用举例对A*算法的一点思考熟练掌握A*算法的性质A*算法的性质A*算法的最优性h(n)的单调限制A算法在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法又称为启发式搜索算法。对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。
1.全局择优搜索在全局择优搜索中，每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可能描述如下：
（1）把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；（2）如果Open表为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，并记该节点为n；（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；（5）若节点n不可扩展，则转到第(2)步；（6）扩展节点n，生成子节点ni(i=1,2,……)，计算每一个子节点的估价值f(ni)(i=1,2,……)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；（8）转第(2)步。
由于上述算法的第(7)步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第(3)步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。对上述算法进一步分析还可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。
例1：八数码难题。设问题的初始状态S0和目标状态Sg如图所示，估价函数与请用全局择优搜索解决该题。
解：这个问题的全局择优搜索树如图1所示。在图1中，每个节点旁边的数字是该节点的估价函数值。例如，对节点S2，其估价函数的计算为f(S2)=d(S2)+W(S2)=2+2=4从图1还可以看出，该问题的解为S0→S1→S2→S3→Sg
图1八数码难题的全局择优搜索树
2.局部择优搜索在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：
(1)把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；(2)如果Open表为空，则问题无解，失败退出；(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；(4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；(5)若节点n不可扩展，则转到第(2)步；(6)扩展节点n，生成子节点ni(i=1,2,……)，计算每一个子节点的估价值f(ni)(i=1,2,……)，并按估价值从小到大的顺序依次放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。
由于这一算法的第六步仅仅是把刚生成的子节点按其估价函数值从小到大放入Open表中，这样在算法第(3)步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的深度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。
A*算法上一节讨论的启发式搜索算法，都没有对估价函数f(n)做任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。假设f*(n)为从初始节点S0出发，约束经过节点n到达目标节点的最小代价值。估价函数f(n)则是f*(n)的估计值。显然，f*(n)应由以下两部分所组成：
一部分是从初始节点S0到节点n的最小代价，记为g*(n)；另一部分是从节点n到目标节点的最小代价，记为h*(n)，当问题有多个目标节点时，应选取其中代价最小的一个。因此有f*(n)=g*(n)+h*(n)把估价函数f(n)与f*(n)相比
g(n)是对g*(n)的一个估计h(n)是对h*(n)的一个估计。在这两个估计中，尽管g(n)的值容易计算，但它不一定就是从初始节点S0到节点n的真正最小代价，很有可能从初始节点S0到节点n的真正最小代价还没有找到，故有有了g*(n)和h*(n)的定义，如果我们对A算法（全局择优的启发式搜索算法）中的g(n)和h(n)分别提出如下限制：•g(n)是对g*(n)的估计，且g(n)>0；•h(n)是对h*(n)的下界，即对任意节点n均有则称得到的算法为A*算法。
1.A*算法的可纳性一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。A*算法是可采纳的。下面我们分三步来证明这一结论。
定理1对有限图，如果从初始节点S0到目标节点Sg有路径存在，则算法A*一定成功结束。定理1证明：首先证明算法必定会结束。由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此，A*算法必然会结束。然后证明算法一定会成功结束。由于至少存在一条由初始节点到目标节点的路径，设此路径S0=n0，n1，…，nk=Sg算法开始时，节点n0在Open表中，而且路径中任一节点ni离开Open表后，其后继节点ni+1必然进入Open表，这样，在Open表变为空之前，目标节点必然出现在Open表中。因此，算法必定会成功结束。
引理0在最佳路径上的所有节点n的f值都应相等，即f(n)=f*(S0)
引理1对无限图，如果从初始节点S0到目标节点Sg有路径存在，且A*算法不终止的话，则从Open表中选出的节点必将具有任意大的f值。引理1证明：设d*(n)是A生成的从初始节点S0到节点n的最短路径长度，由于搜索图中每条边的代价都是一个正数，令这些正数中最小的一个数是e,则有因为是最佳路径的代价，故有又因为h(n)>=0,故有如果A算法不终止的话，从Open表中选出的节点必将具有任意大的d*(n)值，因此，也将具有任意大的f值。引理2在A*算法终止前的任何时刻，Open表中总存在节点n’，它是从初始节点S0到目标节点的最佳路径上的一个节点，且满足。引理2证明：设从初始节点S0到目标节点t的最佳路径序列为S0=n0，n1，…，nk=Sg算法开始时，节点S0在Open表中，当节点S0离开Open进入Closed表时，节点n1进入Open表。因此，A没有结束以前，在Open表中必存在最佳路径上的节点。设这些节点排在最前面的节点为n’,则有由于n’在最佳路径上，故有从而又由于A算法满足故有因为在最佳路径上的所有节点的f*值都应相等，因此有
定理2对无限图，若从初始节点S0到目标节点t有路径存在，则A*算法必然会结束。证明：（反证法）假设A算法不结束，又引理5.1知Open表中的节点有任意大的f值，这与引理2的结论相矛盾，因此，A算法只能成功结束。
推论1Open表中任一具有的节点n，最终都被A*算法选作为扩展节点。
定理3A算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A算法必能结束在最佳路径上。证明：证明过程分以下两步进行：先证明A*算法一定能够终止在某个目标节点上。由定理1和定理2可知，无论是对有限图还是无限图，A算法都能够找到某个目标节点而结束。**再证明A算法只能终止在最佳路径上（反证法）。**假设A算法未能终止在最佳路径上，而是终止在某个目标节点t处，则有但由引理2可知，在A算法结束前，必有最佳路径上的一个节点n’在Open表中，且有这时，A算法一定会选择n’来扩展，而不可能选择t，从而也不会去测试目标节点t，这就与假设A算法终止在目标节点t相矛盾。因此，A*算法只能终止在最佳路径上。
在A*算法中，对任何被扩展的任一节点n，都有证明：令n是由A*选作扩展的任一节点，因此n不会是目标节点，且搜索没有结束。由引理2可知，在Open表中有满足的节点n’。若n=n’，则有否则，算法既然选择n扩展，那就必有，所以有
2.A*算法的最优性A算法的搜索效率很大程度上取决于估价函数h(n)。一般说来，在满足**h(n)≤h(n)**的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A算法搜索时扩展的节点就越少，搜索的效率就越高?A算法的这一特性也称为信息性。下面通过一个定理来描述这一特性。
定理4设有两个A算法A1和A2*，它们有A1*：f1(n)=g1(n)+h1(n)A2*：f2(n)=g2(n)+h2(n)如果A2比A1有更多的启发性信息，即对所有非目标节点均有h2(n)>h1(n)则在搜索过程中，被A2扩展的节点也必然被A1扩展，即A1扩展的节点不会比A2扩展的节点少，亦即A2扩展的节点集是A1扩展的节点集的子集。证明：（用数学归纳法）(1)对深度d(n)=0的节点，即n为初始节点S0，如果n为目标节点，则A1和A2都不扩展n；如果n不是目标节点，则A1和A2都要扩展n。(2)假设对A2搜索树中d(n)=k的任意节点n，结论成立，即A1也扩展了这些节点。(3)证明A2搜索树中d(n)=k+1的任意节点n，也要由A1扩展（用反证法）。假设A2搜索树上有一个满足d(n)=k+1的节点n,A2扩展了该节点，但A1没有扩展它。根据第(2)条的假设，知道A1扩展了节点n的父节点。因此，n必定在A1的Open表中。既然节点n没有被A1扩展，则有f1(n)≥f*(S0)即g1(n)+h1(n)≥f*(S0)但由于d=k时，A2扩展的节点A1也一定扩展，故有g1(n)≤g2(n)因此有-g1(n)≥-g2(n)因此有h1(n)≥f*(S0)-g1(n)≥f*(S0)-g2(n)h1(n)≥f*(S0)-g2(n)另一方面，由于A2扩展了n，因此有f2(n)≤f(S0)即g2(n)+h2(n)≤f*(S0)亦即h2(n)≤f*(S0)-g2(n)f*(S0)-g2(n)≥h2(n)所以有h1(n)≥h2(n)这与我们最初假设的h1(n)h1(n)则在搜索过程中，被A2扩展的节点也必然被A1扩展，即A1扩展的节点不会比A2扩展的节点少，亦即A2扩展的节点集是A1扩展的节点集的子集。
h(n)的单调限制•如果启发函数满足以下两个条件：•（1）h(Sg)=0；•（2）对任意节点ni及其任意子节点nj,都有其中c(ni,nj)是节点ni到其子节点nj的边代价，则称h(n)满足单调限制•如果h满足单调条件，则当A*算法扩展节点n时，该节点就找到了通往它的最佳路径，即
人工智能之搜索方法
人工智能之搜索方法人工智能课程复习笔记专题人工智能绪论人工智能之知识表示人工智能之搜索方法人工智能之经典逻辑推理人工智能之专家系统人工智能之不确定推理方法人工智能之机器学习
一、搜索的基本概念1、搜索的含义根据问题实际情况，不断寻找可利用的知识，构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。
搜索类型按是否使用启发式信息：盲目搜索、启发式搜索按问题的表示方式：状态空间搜索、与或树搜索
2、问题表示法2.1状态空间表示法状态空间表示法用“状态”和“算符”来表示问题
状态：描述问题求解过程不同时刻的状态算符：表示对状态的操作状态空间：由初始状态集合，算符集合、目标状态集合构成的三元组。状态空间图：状态空间的图表示，节点为状态、有向边为算符
解：初始状态到目标状态所使用的算符序列
例子：二阶“梵塔”问题状态空间方法1)状态的表示柱的编号用i,j来代表(i,j)表示问题的状态其中:i代表A所在的柱子j代表B所在的柱子状态集合(9种可能的状态)s0=(1,1),s1=(1,2),s2=(1,3)s3=(2,1),s4=(2,2),s5=(2,3)s6=(3,1),s7=(3,2),s8=(3,3)
2)操作（算符）的定义定义操作A(i,j)表示把A从i移到j；B(i,j)表示把B从i移到j。操作集合(共12个算符）：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)
3）状态空间图
2.1与或树表示法与或树表示方法也称问题归约方法。把复杂问题转换为若干个需要处理的子问题后再加以分别求解的策略，可以递归的进行，直到问题转换为本原问题的集合。
分解将问题归约为一组子问题，当子问题都有解，原问题才有解。即子问题的“与”同原问题等价
等价变换将原问题归约为一组子问题，当子问题其中一个有解，原问题就有解。即子问题的“或”同原问题等价
本原问题不能再分解或变换，而且可以直接求解的问题。
端节点与终止节点在与/或树中，没有子节点的节点称为端节点；若该端节点是本原问题，则为终止节点。
可解节点满足一下条件之一：1）它是一个终止节点2）它是一个或节点，且其子节点至少有一个是可解节点。3）它是一个与节点，且其子节点均为可解节点
不可解节点可解节点的条件均不满足
解树可推出初始节点为可解节点的所有可解节点构成的子树
例子
二、状态空间树的搜索方法1、状态空间的盲目搜索方法特点1）按规定路线搜索，不使用启发式信息2）适用于状态空间图为树结构的问题搜索过程OPEN表：待考查节点CLOSED表：已考察节点结束标志目标状态出现
1.1宽度优先搜索1）把起始节点放入OPEN表中2）若OPEN表为空表则没有解，失败退出，否则继续。3）把OPEN表的第一节点N放入CLOSED表中4）考察节点N是否为目标节点，如果是则得到了解，否则继续5）如果N不可扩展，转至2），否则继续。6）取出N的所有节点放入OPEN表末尾，并为其配置父节点指针，然后转至2）例子
宽度优先改进判断其子节点是否为目标节点，这样可以减少一层
1.2深度优先搜索与宽度优先方法相同，只是第3）步从OPEN表取的是最后一个节点。例子
有界深度优先搜索固定深度：到一定深度没有则搜索兄弟节点可变深度：先小深度，再变大可变深度改进：搜到解后该深度为最大深度，继续搜索，深度只能减小，直至找到最优解
1.3代价树边上标有代价的树称为代价树。在代价树中，若用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有：g(x2)=g(x1)+c(x1,x2)
代价树的宽度优先搜索每次扩展时总是从OPEN表中选取全部代价最小的节点进行扩展。代价树的深度优先搜索每次扩展时总是选取刚扩展出来的节点中代价最小的节点进行扩展。
2、状态空间的启发式搜索在搜索过程中，关键的一步是如何确定下一个要考察的节点，确定的方法不同就形成了不同的搜索策略。如果在确定节点时能充分利用与问题求解有关的控制信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以利于求得最优解。
估计函数f(x)=g(x)+h(x)其中g(x)为从初始节点S0到节点x已经实际付出的代价；h(x)是从节点x到目标节点Sg的最优路径的估计代价，h(x)称为启发函数，它体现了问题的启发性信息。
局部择优搜索当一个节点被扩展以后，按f(x)对每一个子节点计算估价值，并选择最小者作为下一个要考察的节点。
深度优先搜索：f(x)=d(x)代价树的深度优先搜索：f(x)=g(x)局部择优搜索：f(x)=g(x)+h(x)
全局择优搜索每次总是从OPEN表的全体节点中选择一个估价值最小的节点。
宽度优先搜索：f(x)=d(x)代价树的宽度优先搜索：f(x)=g(x)全局择优搜索：f(x)=g(x)+h(x)
有序搜索当搜索过程生成一个节点i时，需要把节点i的状态与已生成的所有节点的状态进行比较，若节点i是一个已生成的节点，则表示找到一条通过节点i的新路径。若新路径使节点i的估价值更小，则修改节点i指向父节点的指针，使之指向新的父节点；否则，不修改节点i原有的父节点指针，即保留节点i原有的路径。
(1)把初始节点S0放入OPEN表，f(S0)。(2)如果OPEN表为空，则问题无解，退出。(3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。(4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。(5)若节点n不可扩展，则转第(2)步。(6)扩展节点n，生成其全部子节点。对节点n的每个子节点i，计算f(i)。考察节点i是否为已生成过的节点。①如果节点i既不在OPEN表中，又不在CLOSED表中，则节点i是一个新节点。为节点i配置指向父节点n的指针，把节点I放入OPEN表中，然后对OPEN表中的全部节点按估价值从小到大的顺序进行排序。②如果节点i已在OPEN表中或在CLOSED表中，则节点i是一个已生成过的节点。比较节点i刚计算的f(i)新值与表中记载的f(i)旧值，若新的f(i)值较小则：(a)对表中节点i的有关记载进行下述修改：用f(i)的新值代替旧值，修改节点i指向父节点的指针，使之指向新的父节点n。(b)若节点i在CLOSED表中，则把节点i移回OPEN表。(7)然后转第(2)步A*算法
我们希望估价函数f是f*的一个估计，此估计可由下式给出：f(n)=g(n)+h(n)其中：g是g*的估计；h是h*的估计。对于g(n)来说。很显然g(n)≥g*(n)。对于h*(n)估计h(n)，它依赖于有关问题的领域的启发信息。
定义1：在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义2：在A算法中，如果对所有的x，h(x)≤h*(x)成立,则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3：采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。
三、与或树的搜索算法基本思想：扩展（自上而下）标示（自下而上）结束条件：初始节点为可解或不可解
搜索过程：（1）把原始问题作为初始节点S0,并将其作为当前节点。（2）应用分解或等价变换算符对当前节点进行扩展。（3）为每个子节点设置指向父节点的指针（4）选择合适的子节点作为当前节点,反复应用（2）（3）步，在此期间要多次应用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点。可解标示过程：由可解子节点来确定父节点，祖父节点等为可解节点的过程‘与’节点只有当其子节点全为可解节点时，才为可解节点；‘或’节点只要有一个子节点为可解节点，它就是可解节点。不可解标示过程：由不可解子节点来确定父节点，祖父节点等为不可解节点的过程‘与’节点只要其子节点有一个为不可解节点，它就是不可解节点；‘或’节点只有当其子节点都为不可解节点，它才是不可解节点。
1、与或树的盲目搜索1.1与或树的宽度优先搜索按照“先产生的节点先扩展”的原则进行搜索。与/或树的宽度优先搜索与状态空间的宽度优先搜索的主要差别是，需要在搜索过程中需要多次调用可解标识过程或不可解标识过程.
1.2与或树的深度优先搜索与/或树的深度优先搜索和与/或树的宽度优先搜索过程基本相同，其主要区别在于OPEN表中节点的排列顺序不同。在扩展节点时，与/或树的深度优先搜索过程总是把刚生成的节点放在OPEN表的首部。
2、与或树的启发式搜索2.1与或树的有序搜索解树的代价终止节点：h(x)=0或节点：h(x)=min{c(x,yi)+h(yi)}与节点：h(x)=∑(c(x,yi)+h(yi))或h(x)=max{c(x,yi)+h(yi)}不可扩展的非终止节点：h(x)=∝例子
希望树搜索过程中最有可能成为最优解的那棵树(1)初始节点S0在希望树T(2)如果n是具有子节点n1,n2,…,nk的或节点，则n的某个子节点ni在希望树T中的充分必要条件是h(ni)=min{c(n,ni)+h(ni)}
(3)如果n是与节点，则n的全部子节点都在希望树T中。例子
2.2博弈树在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。把上述博弈过程用图表示出来，则得到的是一棵“与或树”。
博弈树的特点
博弈的初始格局是初始节点。在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流地扩展节点。所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。极大极小分析法
为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。
当端节点的估值计算出来后，再推算出父节点的得分。推算的方法是：
对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。或取大，与取小
如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。
α－ß剪枝技术
或节点取大，可以实时获得下确界；与节点取小，可以实时获得上确界
α剪枝：对于一个与节点MIN,若能估计出其倒推值的上确界β,并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α,即α≥β,则就不必再扩展该MIN节点的其余子节点了
因为或取大，或的子节点是与节点，与节点取小。所以与节点的一个子节点出来后就知道该与节点的最大值β(与节点取小，后面只能把该值调小而已)。该与节点的父节点是或节点，取大，所以当β无法大于此时父节点的值时，后面就无法再大与了，所以该与节点没必要在扩展节点了。
ß剪枝对于一个或节点max，若能估算其下确界α，并且这个α不小于其父节点（与节点）的上确界β，即α≥β，则不必再扩展max的子节点了。
或节点取大，所以可以估算下确界α，后面再扩再扩展只节点，都不可能变小了，而其父节点是与节点，与节点取小有上确界β，不能再变大了，所以α≥β，α对β是没影响的，所以不用再扩展了。
人工智能笔记之搜索算法（盲目搜索、启发式搜索）
1.搜索算法是很多优化和规划问题问题的基础，很多问题的解决都依赖于搜索策略。2.把一个问题转化为搜索问题（即问题的形式化）需要：将问题表示为状态（STATES）和操作算子（OPERATORS）的集合，操作算子可以将问题由一个状态转化为另一种状态。利用不同的操作算子将问题从初始状态转化到目标状态，所有这些操作算子的序列即为问题的一个解。因此，我们要想找到一个问题的解就是在状态空间中找到连接初始状态和目标状态操作算子序列。
盲目搜索（UninformedSearch、BlindSearch）深度优先搜索（Depth-firstsearch）：按照深度优先方式遍历搜索空间，但是这种方式可能会使遍历一直在非目标状态方向上深度遍历，导致找不到解。广度优先搜索（Breadth-firstsearch）：广度优先搜索始终可以保证找到问题的解，但时间和空间消耗较大。迭代搜索（Iterativedeepeningsearch）：考虑到深度优先搜索不一定可以找到问题的解，但是可以将深度优先和广度优先向结合，即为其添加深度限制。当深度遍历到一定的深度还是找不到解时使搜索方向转到其他状态分支继续深度遍历，使受限制的层数不断增加直到找到问题的解。
启发式搜索（HeuristicSearch、Best-firstSearch）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)为当前状态的深度：各搜索算法对比：
由上表对比数据可知：
广度优先搜索虽然可以保证一定找到解，但是时间复杂度和空间复杂度很高。增加了深度限制的深度优先搜索比广度优先搜索扩展步数更少、耗时更短。为搜索增加评估函数的A*算法可以使搜索更有方向性，极大的减少了扩展步数，节约了待扩展序列的存储空间；时间效率也大大提高。加强A*算法的评估函数的条件，继续避免一些不必要的扩展，可以进一步提高搜索效率。人工智能 —— 搜索的含义
一、概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索
二、适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。
三、搜索的类型：（1）按是否使用启发式信息：
盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。（2）按问题的表示方式：
状态空间搜索：用状态空间法来求解问题所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索