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