《状态空间搜索策略》PPT课件

《《状态空间搜索策略》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、三、搜索策略3.1图搜索策略3.2盲目搜索3.3启发式搜索从问题表示到问题的解决，有一个求解的过程。常见的AI问题求解技术有两种，即“搜索”（Search）和“推理”（Reasoning）方法。逻辑推理，是通过构造一个逻辑系统，由它可以从已有的断言（公理）推导出新的断言。并用逻辑形式语言描述的一组公理来表达问题域。用这种方法来解决问题就是通过推理来积聚越来越多的断言，直到获得问题的解答。虽然问题求解可通过搜索方法，也可用逻辑推理，但二者的侧重点是不一样的。前者着重于寻求问题解答的过程，而后者强调前提（初始）问题空间（公理集合）与问题

2、解答间连接的逻辑正确性。或者简单地讲，搜索着重于发现（Discovery），而推理强调证明（Proof）。搜索在状态图中寻找目标或路径的基本方法从初始节点，沿着与之相连的边，寻找目标节点的过程搜索树搜索过程中经过的节点和边，按照原图的连接关系，便形成一个树形的有向图盲目搜索无向导搜索/穷举式搜索从初始节点，沿连接边逐一考察各个节点，或反向进行启发式(heuristic)搜索利用“启发性信息”引导的搜索启发式信息是与问题有关的有利于尽快找到问题解的信息或知识3.1图搜索策略图（状态图）搜索控制策略一种在图中寻找路径的方法。图中每个节

3、点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图组成节点有向边图分类或图（直接图、状态图）与或图图搜索过程图图（状态图）搜索策略CLOSED表：用来记录考察过的节点对树形搜索，存储的是搜索树对线式搜索，存储的是折线OPEN表：记录待考察的节点排序方式不同，对应的搜索算法不同节点父节点编号编号节点父节点编号CLOSED表OPEN表开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OP

4、EN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否3.2盲目搜索特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法广度（宽度）优先搜索(Breadth-firstsearch,BFS)优先在同一级节点中考察，只有当同一级节点考察完毕之后，才考察下一级节点自顶向下一层一层逐渐生成的宽度优先搜

5、索算法步1：把初始节点So放入OPEN表中。步2：若OPEN表为空,则搜索失败,退出。步3：取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。步4：若目标节点Sg=N,则搜索成功,结束。步5：若N不可扩展,则转步2。步6：扩展N,将mj子节点配上指向N的指针依次放入OPEN表尾部,转步2。注解：OPEN表是一个队列CLOSED表是一个顺序表，表中各节点按顺序标号，正在被考察的节点在表中编号最大如果问题有解，目标点Sg必出现在OPEN表中，算法结束根据返回指针，在CLOSED表中回溯，得到求解路径开始把S放入OPE

6、N表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2宽度优先算法框图是否是否例子八数码难题（8-puzzleproblem）1238456712384567（目标状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。123845671238412384567412385671238412384567123

7、845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567图3.4八数码难题的宽度优先搜索树宽度优先搜索算法宽度优先/横向搜索优点策略是完备的如果有解，肯定找

8、到解，且找到的解是最优解(最短路径)缺点效率低节点深度：根节点深度=0其它节点深度=父节点深度+13.2.2深度优先搜索3.2.2深度优先搜索定义首先扩展最新产生的(即最深的)节点。算法防止搜索过程沿着无益的路径扩展下去，往往给出一个