盲目搜索启发式搜索.ppt

盲目搜索
按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。效率低、主要用于简单问题求解。
启发式搜索
在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。与图有关的术语扩展——求解父节点的所有子节点，叫做扩展。
路径——在一系列节点n1,n2,,nm中，从n1开始，ni总有分枝连接ni+1，称从n1到nm之间的分枝集合是路径。路径中不包含两个及以上相同的分枝，如果n1和nm是同一个节点，则称这种路径为闭路。不构成闭路的称为树。
在用状态空间图来表示问题时，对问题的求解就是求出从初始节点到目标节点的路径。图搜索策略2.CLOSED表的引入OPEN表的引入举例：八数码魔方例子中OPEN表变化过程CLOSED表变化过程图搜索的一般过程图搜索的一般过程开始一、盲目搜索1、宽度优先搜索宽度优先搜索示意图宽度优先搜索算法：(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。宽度优先搜索算法框图宽度优先搜索方法分析：例如：宽度优先搜索用于八数码难题。这个问题就是要把初始棋局变为如下目标棋局的问题：八数码难题的宽度优先搜索树对应动态演示图2、深度优先搜索深度优先搜索示意图在深度优先搜索中，首先扩展最新产生的(即最深的)节点（深度相等的节点可以任意排列）。其结果是搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。3.1.3深度优先搜索对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。含有深度界限的深度优先搜索算法：(1)把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。(2)如果OPEN为一空表，则失败退出。(3)把第一个节点(节点n)从OPEN表移到CLOSED表。(4)如果节点n的深度等于最大深度，则转向(2)。(5)扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。(6)如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。算法动态演示图八数码难题的深度优先搜索树二、启发式搜索二、启发式搜索二、启发式搜索1、启发式搜索策略2、估价函数2、估价函数3、有序搜索3、有序搜索有序状态空间搜索算法(6)扩展节点i生成其全部后继节点。对于i的每一个后继节点j：
(a)计算f(j)。
(b)如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。
(c)如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则
(i)以此新值取代旧值。
(ii)从j指向i，而不是指向它的父辈节点。
(iii)如果节点j在CLOSED表中，则把它移回OPEN表
(7)转向(2)，即GOTO(2)。
注释：
步骤（6.c）是一般搜索图所需要的，该图中可能有一个以上的父辈节点。具有最小估价函数f（j）的节点被选作父辈节点。但是，由于搜索树，它最多只有一个父辈节点，所以步骤（6.c）可以略去。有序搜索算法框图有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。有序搜索例子八数码难题的有序搜索树从图可见，这里所求得的解答路径和用其它搜索方法找到的解答路径相同。不过，估价函数的应用显著地减少了被扩展的节点数(如果我们只用估价函数f(n)=d(n)，那么我们就得到宽度优先搜索过程)。正确地选择估价函数对确定搜索结果具有决定性的作用。使用不能识别