第二章 3-6代价树搜索.ppt

3.6 代价树搜索 基本思想 代价树广度优先搜索 代价树深度优先搜索 * 1) 基本思想 特点： 节点间有向边的代价不同 * 简化的罗马尼亚地图how many routes? Which is best?time,length,cost E.G. 1 Arad—Bucharest * 2) 代价树广度优先搜索 (1）把初始节点S0放入OPEN，令g(S0)=0。 (2）检查OPEN是否为空，是，无解，退出。 (3）把OPEN第一个节点（并记该节点为n ）取出放入CLOSED。 (4）考察节点n是否为目标节点，是，得解，退出。 (5）考察节点n是否可扩展，否，则转2）。 (6）扩展节点n ，将其子节点放入OPEN，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，并按各节点的代价进行排序（从小到大），然后转2）。 * 宽度代价树优先搜索 * 1.配指向父节点的指针NEW NODES 2计算各子节点的代价NEW NODES 3按各节点的代价进行排序（从小到大)ALL NODES 分支界限法 最小代价法 * 例2 ： 求下图所示的旅行问题中，费用最小的路线，设出发地是A城，目的地是E城，图中各边上的数字代表交通费用。 * 例2-1 宽度搜索树： 4 5 6 7 * 3) 代价树深度优先搜索 (1）把初始节点S0放入OPEN，令g(S0)=0。 (2）检查OPEN是否为空，是，无解，退出。 (3）把OPEN第一个节点（并记该节点为n ）取出放入CLOSED。 (4）考察节点n是否为目标节点，是，得解，退出。 (5）考察节点n是否可扩展，否，则转2）。 (6）扩展节点n ，将其子节点按边代价从小到大进行排序放入OPEN首部，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，然后转2）。 * 深度代价树优先搜索 * * 1.配指向父节点的指针NEW NODES 2计算各子节点的代价NEW NODES 3按各节点的代价进行排序（从小到大)放入OPEN首部NEW NODES 最近择优法 爬山法 * 例2-2 深度优先搜索树： 3 6 * * 例3 城市交通费用图-1 若从A出发，最后到达E，要求把每个城市都访问一遍。 试找一条费用最少线路。 Analysis Width first 70 120 55 B C A E D 60 140 110 110 100 75 50 * Homework 城市交通费用图 70 120 55 B C A E D 60 140 110 110 100 75 50 * 若从A出发，最后到达E. 要求 1)Climb mountain。 试找一条线路,count 费用。 2) Width first,找一条线路, 费用最少 3) 对两种方法的解进行比较 1. 宽度优先、深度优先搜索主要差别是待扩展节点的顺序。 2.宽度优先、深度优先搜索属于盲目搜索（按规定的路线搜索）。盲目搜索效率低，耗费过多的计算空间与时间。 3. 若选择最有希望的节点加以扩展，则搜索效率将会大为提高。　　 小结 * 首部 EFCD dm=1 OPEN CLOSED JIHDGCFEBA dm=dm+?d(?d=1) OPEN EFGHIJ CLOSED JIHFLKE * 首部 EFCD I R表 * * * * *