e第彐章图搜索与问题求解 深度优先搜索算法: 步1把初始节点S放入OPEN表中。蕌 步2若OPEN表为空,则搜索失败,退出。蕌 步3取OPEN表中前面第一个节点N放入 CLOSED 表中,并冠以顺序编号n。蕌 步4若目标节点Sg=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第彐章图搜索与问题求解 3.有界深度优先搜索 步1把S放入OPEN表中,置S的深度d(S=0。 步2若OPEN表为空,则失败,退出。蕌 步3取OPEN表中前面第一个节点N,放入 CLOSED表中,并冠以顺序编号n。蕌 步4若目标节点S=N,则成功,结束。蕌 步5若N的深度(N=dm(深度限制值),或者若N 无子节点,则转步2。蕌 步6扩展N,将其所有子节点N配上指向N的返回 指针后依次放入OPEN表中前部,置d(N)=d(N)+1,转 步2。一
第 3 章 图搜索与问题求解 3. 有界深度优先搜索 步1 把So放入OPEN表中,置So的深度d(So)=0。 步2 若OPEN表为空, 则失败, 退出。 步 3 取 O P E N 表 中 前 面 第 一 个 节 点 N , 放 入 CLOSED表中, 并冠以顺序编号n。 步4 若目标节点Sg =N, 则成功, 结束。 步5 若N的深度d(N)=dm(深度限制值), 或者若N 无子节点, 则转步2。 步6 扩展N, 将其所有子节点Ni配上指向N的返回 指针后依次放入OPEN表中前部, 置d(Ni)=d(N)+1,转 步2
e第彐章图搜索与问题求解 3.1.4启发式搜索 1.问题的提出 2.启发性信息蕌 按其用途划分,启发性信息可分为以下三类: (1)用于扩展节点的选择,即用于决定应先扩展 哪一个节点,以免盲目扩展。蕌 (2)用于生成节点的选择,即用于决定应生成哪 些后续节点,以免盲目地生成过多无用节点。蕌 (3)用于删除节点的选择,即用于决定应删除哪 些无用节点,以免造成进一步的时空浪费
第 3 章 图搜索与问题求解 3.1.4 启发式搜索 1. 问题的提出 2. 启发性信息 按其用途划分, 启发性信息可分为以下三类： (1) 用于扩展节点的选择, 即用于决定应先扩展 哪一个节点, 以免盲目扩展。 (2) 用于生成节点的选择,即用于决定应生成哪 些后续节点,以免盲目地生成过多无用节点。 (3) 用于删除节点的选择,即用于决定应删除哪 些无用节点, 以免造成进一步的时空浪费
e第彐章图搜索与问题求解 3.启发函数蕌 启发函数是用来估计搜索树上节点x与目标节点 S接近程度的一种函数,通常记为h(x) 4.启发式搜索算法蕌 1)全局择优搜索蕌 2)局部择优搜索
第 3 章 图搜索与问题求解 3.启发函数 启发函数是用来估计搜索树上节点x与目标节点 Sg接近程度的一种函数, 通常记为h(x)。 4.启发式搜索算法 1) 全局择优搜索 2) 局部择优搜索
e第彐章图搜索与问题求解 全局择优搜索算法: 步1把初始节点S放入OPEN表中,计算h(S)。蕌 步2若OPEN表为空,则搜索失败,退出。蕌 步3移出OPEN表中第一个节点N放入 CLOSED表中,并冠 以序号n。蕌 步4若目标节点S2=N,则搜索成功,结束。蕌 步5若N不可扩展,则转步2。蕌 步6扩展N,计算每个子节点x的函数值h(x)并将所有子节 点配以指向N的返回指针后放入OPEN表中,再对OPEN表中的所 有子节点按其函数值大小以升序排序,转步2
第 3 章 图搜索与问题求解 全局择优搜索算法： 步1 把初始节点So放入OPEN表中,计算h(So)。 步2 若OPEN表为空,则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠 以序号n。 步4 若目标节点Sg =N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2。 步6 扩展N, 计算每个子节点x的函数值h(x), 并将所有子节 点配以指向N的返回指针后放入OPEN表中, 再对OPEN表中的所 有子节点按其函数值大小以升序排序,转步2