文档介绍：第4章图搜索技术
根据问题的实际情况不断寻找可利用的知识,从而构造一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索。搜索实用于:结构不良问题,无成熟算法;或有算法,但问题复杂,如博弈。
或图搜索;与或图搜索
第4章图搜索技术---- 状态图搜索
状态图
例、八数码问题的状态图表示。
状态是描述问题求解过程中任一时刻的状况,一般用一组变量的有序组合表示。引起状态中某些分量发生变化,从而使问题从一个状态变为另一个状态的操作、规则、变换称为算符。问题求解就是寻找一个从初始状态到目标状态的算符序列的过程。问题求解过程可描述为一个有向图,其中的节点代表状态,边表示状态转换之间的算符。
第4章图搜索技术---- 状态图搜索
状态图搜索
1、搜索方式
树式搜索:每次扩展所有子节点
线式搜索:每次只扩展一个子节点
可回溯(穷举式搜索) 不可回溯(随机碰
撞式搜索)
2、搜索策略
搜索分为盲目搜索和启发式搜索。盲目搜索:按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略;启发式搜索:在搜索过程中加入了与问题有关的启发性信息,用以指导搜索朝着最有希望的方向前进,加速问题的求解过程并找到最优解。
第4章图搜索技术---- 状态图搜索
3、搜索算法
树式搜索算法:
步1 把初始节点放入OPEN表;
步2 检查OPEN表,若为空,则问题无解,退出;
步3 移出OPEN表中第一个节点并放入CLOSED表中,并记该节点为n;
步4 考察节点n是否为目标节点,若是,则搜索成功,退出;
步5 若n不可扩展,则转步2;
步6 扩展节点n,生成所有子节点,对这组子节点作如下处理:
(1)、如果有节点n的先辈节点,则删除之;
(2)、如果有已存在于OPEN表的节点,也删除之;但删除之前要比较其返回初始节点的新路径与原路径,如果新路径“短”,则修改这些节点在OPEN表中的原指向父节点的指针,使其指向新的父节点。
第4章图搜索技术---- 状态图搜索
(3)、如果有已存在于CLOSED表中的节点,则作与(2)同样的处理,并且再将其移出CLOSED表,放入OPEN表重新扩展;
(4)、对其余子节点,配上指向父节点n的指针后放入OPEN表,对OPEN表按某种搜索策略排序后转步2。
线式搜索算法
不可回溯的线式搜索:
步1 把初始节点S0放入CLOSED表中;
步2 令N= S0 ;
步3 若N是目标节点,则搜索成功,结束;
步4 若N不可扩展,则搜索失败,退出。
步5 扩展N,选取一个未在CLOSED表中出现的子节点N1放入CLOSED表中,令N=N1,转步3。
第4章图搜索技术---- 状态图搜索
可回溯的线式搜索: 步1 把初始节点S0放入CLOSED表中; 步2 令N= S0 ; 步3 若N是目标节点,则搜索成功,结束; 步4 若N不可扩展,则移出CLOSED表的末端节点Ne,若Ne =S0 ,则搜索失败,退出。否则,以CLOSED表新的末端节点Ne作为N,即令N=Ne,转步4 步5 扩展N,选取一个未在CLOSED表中出现的子节点N1放入CLOSED表中,令N=N1,转步3。
第4章图搜索技术---- 状态图搜索
穷举式搜索
1、广度优先搜索
又称宽度优先思索,优先在同一级节点中考察,只有当同一级节点扩展完以后,才扩展下一级节点。
例、解八数码问题。初始状态: (2,8,3,4,5,6,7,1),目标状态: (1,2,3,4,5,6,7,8)
广度优先搜索算法:
步1 把初始节点S0放入OPEN表中;
步2 若OPEN表为空,则搜索失败,退出;
步3 取OPEN表中前面第一个节点N放入CLOSED表中;
步4 若目标节点Sg =N,则搜索成功,结束;
步5 若N不可扩展,则转步2。
步6 扩展N,将其所有子节点配上指向N的指针依次放入OPEN表的尾部,转步2。
第4章图搜索技术---- 状态图搜索
广度优先搜索的特点:完备、解是最优解、效率低。
2、深度优先搜索
在搜索的每一层,始终只扩展一个节点,不断地向纵深前进,直到不能再前进时,才从当前节点返回到上一级节点,延另一节点又继续前进。
例、八数码问题的深度优先搜索。
第4章图搜索技术---- 状态图搜索
深度优先搜索算法:
步1 把初始节点S0放入OPEN表中;
步2 若OPEN表为空,则搜索失败,退出;
步3 取OPEN表中前面第一个节点N放入CLOSED表中;
步4 若目标节点Sg =N,则搜索成功,结束;
步5 若N不可扩展,则转步2。
步6 扩展N,将其所有子节点配上指向N的返回指针依次放入OPEN表的首部,转步2。
深度优先搜索策