第3章图搜索与问题求解
《第3章图搜索与问题求解》由会员分享，可在线阅读，更多相关《第3章图搜索与问题求解（106页珍藏版）》请在文档大全上搜索。
1、第 3 章 图搜索与问题求解 第 3 章 图搜索与问题求解 3.1 状态图搜索状态图搜索 3.2 状态图搜索问题求解状态图搜索问题求解 3.3 与或图搜索与或图搜索 3.4 与或图搜索问题求解与或图搜索问题求解 第 3 章 图搜索与问题求解 3.1 状态图搜索 3.1.1 状态图例例3.1 迷宫问题。第 3 章 图搜索与问题求解 图 3-2 迷宫的有向图表示 第 3 章 图搜索与问题求解 图 3-3 八数码问题示例 例例 3.2 3.2 八数码问题。第 3 章 图搜索与问题求解 3.1.2 状态图搜索1. 1. 搜索方式搜索方式树式搜索 线式搜索 2. 2. 搜索策略搜索策略 盲目搜索 启发式
2、(heuristic)搜索 第 3 章 图搜索与问题求解 图 3-4 OPEN表与CLOSED表示例 3. 3. 搜索算法搜索算法第 3 章 图搜索与问题求解 树式搜索算法：树式搜索算法： 步1 把初始节点So放入OPEN表中。步2 若OPEN表为空, 则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n。步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转步2。 步6 扩展N, 生成一组子节点, 对这组子节点做如下处理：第 3 章 图搜索与问题求解 (1) 删除N的先辈节点(如果有的话)。 (2)对已存在于OPEN表的节点(
3、如果有的话)也删除之；但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”, 则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示 )。 (3)对已存在于CLOSED表的节点(如果有的话), 做与(2)同样的处理, 并且再将其移出CLOSED表, 放入OPEN表重新扩展(为了重新计算代价)。 (4)对其余子节点配上指向N的返回指针后放入OPEN表中某处, 或对OPEN表进行重新排序, 转步2。 第 3 章 图搜索与问题求解 图 3-5 修改返回指针示例 第 3 章 图搜索与问题求解 说明： (1) 这里的返回指针也就是父节点在CLOSED表中的编号。 (2) 步
4、6中修改返回指针的原因是, 因为这些节点又被第二次生成, 所以它们返回初始节点的路径已有两条, 但这两条路径的“长度”可能不同。 那么, 当新路短时自然要走新路。(3) 这里对路径的长短是按路径上的节点数来衡量的, 后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量, 则在需修改返回指针的同时还要修改相应的代价值, 或者不修改返回指针也要修改代价值(为了实现代价小者优先扩展)。 第 3 章 图搜索与问题求解 线式搜索算法： 不回溯的线式搜索不回溯的线式搜索 步1 把初始节点So放入CLOSED表中。步2 令NSo。步3 若N是目标节点,则搜索成功,结束。 步
5、4 若N不可扩展,则搜索失败,退出。 步5 扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入CLOSED表中, 令NN1, 转步3。 第 3 章 图搜索与问题求解 可回溯的线式搜索可回溯的线式搜索 步1 把初始节点So放入CLOSED表中。步2令NSo。步3若N是目标节点, 则搜索成功, 结束。 步4 若N不可扩展, 则移出CLOSED表的末端节点Ne,若NeSo,则搜索失败, 退出。否则, 以CLOSED表新的末端节点Ne作为N,即令NNe, 转步4。步5扩展N, 选取其一个未在CLOSED表用出现过的子节点N1放入CLOSED表中, 令NN1,转步3。 第 3 章 图搜索与问题
6、求解 3.1.3 穷举式搜索1.1.广度优先搜索广度优先搜索图 3-6 八数码问题的广度优先搜索第 3 章 图搜索与问题求解 广度优先搜索算法：广度优先搜索算法： 步1 把初始节点So放入OPEN表中。步2 若OPEN表为空, 则搜索失败,退出。 步3 取OPEN表中前面第一个节点N放在CLOSED表中, 并冠以顺序编号n。步4 若目标节点Sg=N,则搜索成功, 结束。 步5 若N不可扩展, 则转步2。步6 扩展N, 将其所有子节点配上指向N的指针依次放入OPEN表尾部, 转步2。 第 3 章 图搜索与问题求解 2 .2 . 深 度 优 先 搜 索深 度 优 先 搜 索第 3 章 图搜索与问题
7、求解 深度优先搜索算法：深度优先搜索算法： 步1 把初始节点So放入OPEN表中。步2 若OPEN表为空, 则搜索失败, 退出。 步3 取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。步4 若目标节点Sg=N, 则搜索成功,结束。 步5 若N不可扩展, 则转步2。步6扩展N, 将其所有子节点配上指向N的返回指针依次放入OPEN表的首部, 转步2。 第 3 章 图搜索与问题求解 3. 有界深度优先搜索有界深度优先搜索 步1 把So放入OPEN表中,置So的深度d(So)=0。 步2 若OPEN表为空, 则失败, 退出。 步3 取OPEN表中前面第一个节点N,放入CLOSED
8、表中, 并冠以顺序编号n。步4 若目标节点Sg=N, 则成功, 结束。 步5 若N的深度d(N)=dm(深度限制值), 或者若N无子节点, 则转步2。步6 扩展N, 将其所有子节点Ni配上指向N的返回指针后依次放入OPEN表中前部, 置d(Ni)=d(N)+1,转步2。 第 3 章 图搜索与问题求解 3.1.4 启发式搜索1. 1. 问题的提出问题的提出 2. 2. 启发性信息启发性信息按其用途划分, 启发性信息可分为以下三类： (1) 用于扩展节点的选择, 即用于决定应先扩展哪一个节点, 以免盲目扩展。 (2) 用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。
9、(3) 用于删除节点的选择,即用于决定应删除哪些无用节点, 以免造成进一步的时空浪费。 第 3 章 图搜索与问题求解 3.3.启发函数启发函数启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数, 通常记为h(x)。4.4.启发式搜索算法启发式搜索算法1) 全局择优搜索2) 局部择优搜索 第 3 章 图搜索与问题求解 全局择优搜索算法： 步1 把初始节点So放入OPEN表中,计算h(So)。步2 若OPEN表为空,则搜索失败, 退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以序号n。步4 若目标节点Sg=N, 则搜索成功, 结束。 步5 若N不可扩展, 则转
10、步2。步6 扩展N, 计算每个子节点x的函数值h(x), 并将所有子节点配以指向N的返回指针后放入OPEN表中, 再对OPEN表中的所有子节点按其函数值大小以升序排序,转步2。 第 3 章 图搜索与问题求解 图 3-8 八数码问题的全局择优搜索 第 3 章 图搜索与问题求解 例例 3.53.5 用全局择优搜索法解八数码难题。初始棋局和目标棋局同例3。 解解设启发函数h(x)为节点x的格局与目标格局相比数码不同的位置个数。以这个函数制导的搜索树如图3-8所示。此八数问题的解为：So, S1, S2, S3, Sg。 第 3 章 图搜索与问题求解 3.1.5 加权状态图搜索1.1.加权状态图与代价
11、树加权状态图与代价树例例3.63.6 图3-9(a)是一个交通图,设A城是出发地,E城是目的地, 边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。 第 3 章 图搜索与问题求解 图 3-9 交通图及其代价树 第 3 章 图搜索与问题求解 代价树的搜索。所谓代价,可以是两点之间的距离、交通费用或所需时间等等。通常用g(x)表示从初始节点So到节点x的代价, 用c(xi,xj)表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有 g(xj)g(xi)c(xi, xj) 而 g(So)0 第 3 章 图搜索与问题求解 2.2.分支界限法分支界限法( (最小代价优先法最小
