【人工智能课件】图搜索技术.ppt

《【人工智能课件】图搜索技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章图搜索技术根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。搜索实用于：结构不良问题，无成熟算法；或有算法，但问题复杂，如博弈。或图搜索；与或图搜索第4章图搜索技术----4.1状态图搜索4.1.1状态图例、八数码问题的状态图表示。状态是描述问题求解过程中任一时刻的状况，一般用一组变量的有序组合表示。引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作、规则、变换称为算符。问题求解就是寻找一个从初始状态到目标状态的算符序列的过程。问题求解过程可描述为一个

2、有向图，其中的节点代表状态，边表示状态转换之间的算符。第4章图搜索技术----4.1状态图搜索4.1.2状态图搜索1、搜索方式树式搜索：每次扩展所有子节点线式搜索：每次只扩展一个子节点可回溯（穷举式搜索）不可回溯（随机碰撞式搜索）2、搜索策略搜索分为盲目搜索和启发式搜索。盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略；启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。第4章图搜索技术----4.1状态图搜索3、搜索算法树式搜索

3、算法：步1把初始节点放入OPEN表；步2检查OPEN表，若为空，则问题无解，退出；步3移出OPEN表中第一个节点并放入CLOSED表中，并记该节点为n;步4考察节点n是否为目标节点，若是，则搜索成功，退出；步5若n不可扩展，则转步2；步6扩展节点n，生成所有子节点，对这组子节点作如下处理：（1）、如果有节点n的先辈节点，则删除之；（2）、如果有已存在于OPEN表的节点，也删除之；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原指向父节点的指针，使其指向新的父节点。第4章图搜索技术-

4、---4.1状态图搜索（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章图搜索技术----4.

5、1状态图搜索可回溯的线式搜索：步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章图搜索技术----4.1状态图搜索4.1.3穷举式搜索1、广度优先搜索又称宽度优先思索，优先在同一级节点中考察，只有当同一级节点扩展完以后，才扩展下一级

6、节点。例、解八数码问题。初始状态：（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章图搜索技术----4.1状态图搜索广度优先搜索的特点：完备、解是最优解、效率低。2、深度优先搜索在搜索的每一层，始终只扩

7、展一个节点，不断地向纵深前进，直到不能再前进时，才从当前节点返回到上一级节点，延另一节点又继续前进。例、八数码问题的深度优先搜索。第4章图搜索技术----4.1状态图搜索深度优先搜索算法：步1把初始节点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3取OPEN表中前面第一个节点N放入CLOSED表中；步4若目标节点Sg=N，则搜索成功，结束;步5若N不可扩展，则转步2。步6扩展N，将其所有子节点配上指向N的返回指针依次放入OPEN表的首部，转步2。深度优先搜索策略的特点：不完备、找到的解不一定是最优解。第4章图搜

8、索技术----4.1状态图搜索3、有界深度优先搜索搜索深度限制。当深度优先搜索到一定深度后，就不在向纵深搜索，而是改变方向继续搜索。有界深度搜索算法：步1把初始节点S0放入OPEN表中，置S0的深度d(S0)=0；步2若OPEN表为空，则搜索失败，