第3章囹搜索与问题求解 其中OEN表是一个队列, CLOSED表是一个顺序表,表中各节 点按顺序编号,正被考察的节点在表中编号最大。如果问题有 解,OPEN表中必出现目标节点S那么,当搜索到目标节点S2 时,算法结束,然后根据返回指针在CL0SED表中往回追溯,直至 初始节点,所得的路径即为问题的解。 广度优先搜索亦称为宽度优先或横向搜索。这种策略是完 备的,即如果问题的解存在,用它则一定能找到解,且找到的解 还是最优解(即最短的路径)。这是广度优先搜索的优点。但它 的缺点是搜索效率低
第 3 章 图搜索与问题求解 其中OPEN表是一个队列,CLOSED表是一个顺序表,表中各节 点按顺序编号, 正被考察的节点在表中编号最大。如果问题有 解, OPEN表中必出现目标节点Sg,那么, Sg 时,算法结束,然后根据返回指针在CLOSED表中往回追溯,直至 初始节点,所得的路径即为问题的解。 广度优先搜索亦称为宽度优先或横向搜索。这种策略是完 备的,即如果问题的解存在, 用它则一定能找到解,且找到的解 还是最优解(即最短的路径)。这是广度优先搜索的优点。但它 的缺点是搜索效率低
第3章囹搜索与问题求解 2.深度优先搜索 深度优先搜索就是在搜索树的每一层始终先只扩展一个 子节点,不断地向纵深前进,直到不能再前进(到达叶子节点 或受到深度限制)时,才从当前节点返回到上一级节点,沿另 方向又继续前进。这种方法的搜索树是从树根开始一枝 枝逐渐形成的
第 3 章 图搜索与问题求解 2. 深度优先搜索就是在搜索树的每一层始终先只扩展一个 子节点,不断地向纵深前进, 直到不能再前进(到达叶子节点 或受到深度限制)时, 才从当前节点返回到上一级节点, 沿另 一方向又继续前进。这种方法的搜索树是从树根开始一枝一 枝逐渐形成的
第3章囹搜索与问题求解 深度优先搜索算法: 步1把初始节点S放入OPEN表中。 步2若OEN表为空,则搜索失败,退出 步3取OPEN表中前面第一个节点M倣入 CLOSEDE表中,并冠以 顺序编号n 步4若目标节点S=M,则搜索成功,结束。 步5若M可扩展,则转步2。 步6扩展N,将其所有子节点配上指向M返回指针依次放 入OEN表的首部,转步2
第 3 章 图搜索与问题求解 深度优先搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败, 退出。 步3 取OPEN表中前面第一个节点N放入CLOSED表中,并冠以 顺序编号n。 步4 若目标节点Sg =N, 则搜索成功,结束。 步5 若N不可扩展, 则转步2。 步6扩展N, 将其所有子节点配上指向N的返回指针依次放 入OPEN表的首部, 转步2
ξ例3.4对于八数码问题,应用深度优先搜索策略,可得 如图3-7所示的搜索树。 765 要电啊 164 164 要学 754 163 图37八数码问题的深度优先搜索
第 3 章 图搜索与问题求解 图 3-7 八数码问题的深度优先搜索 例3.4 对于八数码问题, 应用深度优先搜索策略, 可得 如图3-7所示的搜索树
第3章囹搜索与问题求解 深度优先搜索亦称为纵向搜索。由于一个有解的问题树 能含有无穷分枝,深度优先搜索如果误入无穷分枝(即深度 无限),则不可能找到目标节点。所以,深度优先搜索策略是 不完备的。另外,应用此策略得到的解不一定是最佳解(最短路 径)
第 3 章 图搜索与问题求解 深度优先搜索亦称为纵向搜索。由于一个有解的问题树 可能含有无穷分枝, 深度优先搜索如果误入无穷分枝(即深度 无限), 则不可能找到目标节点。所以, 深度优先搜索策略是 不完备的。另外, 应用此策略得到的解不一定是最佳解(最短路 径)