e第彐章图搜索与问题求解 2.分支界限法(最小代价优先法)蕌 ●基本思想是:每次从OPE表中选出g(x)值最 小的节点进行考察,而不管这个节点在搜索树的 什么位置上。 ●算法与前面的“全局择优法”仅有引导搜 索的函数不同,前者为启发函数h(x),后者为代价 g(x) 蕌●但注意:代价值g(x)是从初始节点So方向计 算而来的,而启发函数值h(x)则是朝目标节点方向 计算的
第 3 章 图搜索与问题求解 2.分支界限法(最小代价优先法) ●基本思想是：每次从OPEN表中选出g(x)值最 小的节点进行考察, 而不管这个节点在搜索树的 什么位置上。 ●算法与前面的“全局择优法” 仅有引导搜 索的函数不同，前者为启发函数h(x)，后者为代价 g(x)。 ●但注意：代价值g(x)是从初始节点So方向计 算而来的,而启发函数值h(x)则是朝目标节点方向 计算的
e第彐章图搜索与问题求解 3.最近择优法(瞎子爬山法蕌 把局部择优法算法中的h(x)换成g(x)就可得最 近择优法的算法。蕌 例:用代价树搜索求解例3.6中给出的问题。 用分支界限法得到的路径为蕌 A→C→D-E湩 这是一条最小费用路径(费用为8)
第 3 章 图搜索与问题求解 3. 最近择优法(瞎子爬山法) 把局部择优法算法中的h(x)换成g(x)就可得最 近择优法的算法。 例：用代价树搜索求解例3.6中给出的问题。 用分支界限法得到的路径为 A→C→D→E 这是一条最小费用路径(费用为8)
e第彐章图搜索与问题求解 3.1.6A算法和A*算法 1.估价函数蕌 f(x) =g(x)th(x)
第 3 章 图搜索与问题求解 3.1.6 A算法和A *算法 1.估价函数 f(x)＝g(x)＋h(x)
e第彐章图搜索与问题求解 2.A算法 錞A算法是基于估价函数(x)的一种加权状态图启 发式搜索算法。其具体步骤如下: 步1把附有八S)的初始节点S放入OPEN表。 步2若OPEN表为空,则搜索失败,退出 步3移出OPEN表中第一个节点N放入 CLOSED表 中,并冠以顺序编号n。蕌 步4若目标节点S=N,则搜索成功,结束。蕌 步5若N不可扩展,则转步2
第 3 章 图搜索与问题求解 2. A算法 A 算法是基于估价函数f(x)的一种加权状态图启 发式搜索算法。其具体步骤如下： 步1 把附有f(So)的初始节点So放入OPEN表。 步2 若OPEN表为空, 则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表 中, 并冠以顺序编号n。 步4 若目标节点Sg =N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2
e第彐章图搜索与问题求解 步6扩展N,生成一组附有八x)的子节点,对这组子节 点做如下处理:蕌 (1)考察是否有已在OPEN表或 CLOSED表中存在的节点; 若有则再考察其中有无N的先辈节点,若有则删除之;对于其余 节点,也删除之,但由于它们又被第二次生成,因而需考虑是否 修改已经存在于OPEN表或 CLOSED表中的这些节点及其后裔 的返回指针和八(x)值,修改原则是“抄(x)值小的垬路走”。珈 蕌 (2)对其余子节点配上指向N的返回指针后放入OPEN表中, 并对OPEN表按x)值以升序排序,转步2
第 3 章 图搜索与问题求解 步6 扩展N,生成一组附有f(x)的子节点,对这组子节 点做如下处理： (1)考察是否有已在OPEN表或CLOSED表中存在的节点； 若有则再考察其中有无N的先辈节点,若有则删除之；对于其余 节点, 也删除之,但由于它们又被第二次生成, 因而需考虑是否 修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔 的返回指针和f(x)值, 修改原则是“抄f(x)值小的路走” 。 (2)对其余子节点配上指向N的返回指针后放入OPEN表中, 并对OPEN表按f(x)值以升序排序, 转步2