智能控制-第三章搜索推理技术

《智能控制-第三章搜索推理技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章搜索推理技术3.6产生式系统3.7系统组织技术3.8小结3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4消解原理3.5规则演绎系统3.1图搜索策略图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。图搜索过程中南大学智能系统与智能软件研究所图搜索的一般过程如下：1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。2）建立一个叫做CLOSED的已扩展节点表，其初始为空表。3

2、）LOOP：若OPEN表是空表，则失败退出。4）选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。3.1图搜索策略中南大学智能系统与智能软件研究所6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需更改通到n的指针方向。对已在CLO

3、SED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。8）按某一任意方式或按某个探试值，重排OPEN表。9）GOLOOP。3.1图搜索策略中南大学智能系统与智能软件研究所开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否3.1图搜索策略(1)(3)(4)(5)(6)(7)(7)’(8)(9)OPENCLOSED(1)(2)中南大学智能系统与智能软件研究所3.2盲目搜索盲目搜索又叫做无

4、信息搜索，一般只适用于求解比较简单的问题。特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法中南大学智能系统与智能软件研究所1）把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。2）如果OPEN是个空表，则没有解，失败退出；否则继续。3）把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。4）扩展节点n。如果没有后继节点，则转向上述第(2)步。5）把n的所有后继节点放到OPEN表的末端，并提供

5、从这些后继节点回到n的指针。6）如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。3.2盲目搜索中南大学智能系统与智能软件研究所开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2宽度优先算法框图是否是否3.2盲目搜索中南大学智能系统与智能软件研究所例子八数码难题（8-puzzleproblem）1238456712384567（目标状态）（初始状态）规定：将棋子移入空格的顺序为：从空格左边开始顺时针旋转。

6、不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。3.2盲目搜索中南大学智能系统与智能软件研究所1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图3.4八数码难题的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671

7、2384567123845671238456712384567123845671415161718192021123845673.2盲目搜索中南大学智能系统与智能软件研究所3.2.2深度优先搜索定义首先扩展最新产生的(即最深的)节点。算法防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。3.2盲目搜索中南大学智能系统与智能软件研究所深度优先搜索示意图SLOMFPQNFFF中南大学智能系统与