e第彐章图搜索与问题求解 线式搜索算法: ·不回溯的线式搜索 步1把初始节点S放入 CLOSED表中。蕌 步2令N=S。。蕌 步3若N是目标节点,则搜索成功,结束。蕌 步4若N不可扩展,则搜索失败,退出。蕌 步5扩展N,选取其一个未在 CLOSED表中出现 过的子节点N放入 CLOSED表中,令N=N1,转步3
第 3 章 图搜索与问题求解 线式搜索算法： · 不回溯的线式搜索 步1 把初始节点So放入CLOSED表中。 步2 令N＝So。 步3 若N是目标节点,则搜索成功,结束。 步4 若N不可扩展,则搜索失败,退出。 步5 扩展N,选取其一个未在CLOSED表中出现 过的子节点N1放入CLOSED表中, 令N＝N1 , 转步3
e第彐章图搜索与问题求解 可回溯的线式搜索湩 步1把初始节点S放入 CLOSED表中。蕌 步2令N=S 步3若N是目标节点,则搜索成功,结束。蕌 步4若N不可扩展,则移出 CLOSED表的末端节 点N若N。=Sn,则搜索失败,退出。否则,以 CLOSED 表新的末端节点N作为N,即令N=Ne,转步4。春 步5扩展N,选取其一个未在 CLOSED表用出现 过的子节点錞N1放入 CLOSED表中,令N=N,转步3
第 3 章 图搜索与问题求解 · 可回溯的线式搜索 步1 把初始节点So放入CLOSED表中。 步2令N＝So。 步3若N是目标节点, 则搜索成功, 结束。 步4 若N不可扩展, 则移出CLOSED表的末端节 点Ne ,若Ne ＝So ,则搜索失败, 退出。否则, 以CLOSED 表新的末端节点Ne作为N,即令N＝Ne , 转步4。 步5扩展N, 选取其一个未在CLOSED表用出现 过的子节点N1放入CLOSED表中, 令N＝N1 ,转步3
e第彐章图搜索与问题求解 31.3穷举式搜索 1.广度优先搜索 765 7 184 15 19 214 714 145 64 754 13 66图3-6八数码问题的广度优先搜索
第 3 章 图搜索与问题求解 3.1.3 穷举式搜索 1.广度优先搜索 图 3-6 八数码问题的广度优先搜索
e第彐章图搜索与问题求解 广度优先搜索算法: 步1把初始节点S放入OPEN表中。蕌 步2若OPEN表为空,则搜索失败,退出。蕌 步3取OPEN表中前面第一个节点N放在 CLOSED 表中,并冠以顺序编号n。蕌 步4若目标节点Sa=N,则搜索成功,结東。蕌 步5若N不可扩展,则转步2。蕌 步6扩展N,将其所有子节点配上指向N的指针依 次放入OPEN表尾部,转步2
第 3 章 图搜索与问题求解 广度优先搜索算法： 步1 把初始节点So放入OPEN表中。 步2 若OPEN表为空, 则搜索失败,退出。 步3 取OPEN表中前面第一个节点N放在CLOSED 表中, 并冠以顺序编号n。 步4 若目标节点Sg =N,则搜索成功, 结束。 步5 若N不可扩展, 则转步2。 步6 扩展N, 将其所有子节点配上指向N的指针依 次放入OPEN表尾部, 转步2
e第彐章图搜索与问题求解 2.深度优先搜索 要电“B学版 蕌 765 要电可 164 要电子大学出2 画要电子数
第 3 章 图搜索与问题求解 2 . 深 度 优 先 搜 索