南邮自动化人工智能3-确定性推理

《南邮自动化人工智能3-确定性推理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4消解原理3.5规则演绎系统1第三章搜索推理技术3.6产生式系统3.7非单调推理3.8小结问题：知识表示有那些方法？知识表示的目的是什么？构建智能系统的关键是什么？3.1图搜索策略思考：状态空间法的基本特点？基本推理方法？其求解结果是什么？简单回顾实例：猴子与香蕉。2用一个四元表列（W，x，Y，z）表示这个问题状态W猴子的水平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0算符：Goto（U），（W，0，Y，z）goto（U）（U，0，Y，z）P

2、ushbox（V），（W，0，W，z）pushbox（V）（V，0，V，z）Climbbox，（W，0，W，z）climbbox（W，1，W，z）Grasp，（c，1，c，0）grasp（c，1，c，1）33.1图搜索策略4(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）U=b，climbbox猴子和香蕉问题的状态空间图提问：人工搜索求解的解答？目标状态goto（U）goto（U）goto（U）U=b,pushbox（V）pushbox（V）goto（U）V≠c，clim

3、bboxV=c，climbbox3.1图搜索策略5猴子和香蕉问题自动演示：猴子香蕉箱子猴子香蕉箱子Ha!Ha!3.1图搜索策略思考：计算机的搜索策略？图搜索控制策略:一种在图中寻找路径的方法。图中每个节点对应一个状态;每条连线对应一个操作符。图搜索过程（GraphSearch）63.1图搜索策略7开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否3.1图搜索策略(1)(3)(4

4、)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)宽度优先图搜索的一般过程如下：1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。2）建立一个叫做CLOSED的已扩展节点表，其初始为空表.3）LOOP：若OPEN表是空表，则失败退出。4）选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。83.1图搜索策略6）扩展节点n，同时生成不是n的祖先的那些

5、后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。8）按某一任意方式或按某个探试值，重排OPEN表。9）GOLOOP。93.1图搜索策略图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：1，一个完整的搜索图G。2一个解路径，用指针表示的解路径。Procedu

6、reGraphSearch1G=G0(G0=s),open=(s)//s:初始状态2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先辈节点7open←add(open，mj)//mj不在open，closed中2021/7/2510标记mj每个到n节点指针确定是否需要修改已在open，closed中的每个节点到n的指针确定是否需要修改已

7、在closed中的每个节点的后继节点原来的指针。8按照某种方式排列open表中的节点，goloop2021/7/25112021/7/25122021/7/2513思考：（1）结果路径的形成中，为什么其节点顺序是明确的？（2）OPEN表中的节点具有什么特点？（3）CLOSED表中的节点具有什么特点？（4）对OPEN表节点的排序有何意义？提出：盲目搜索与启发式搜索。143.1图搜索策略3.2盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。特点：不需重排OPEN表；种类：宽度优先、深度优先、等代价搜索等。153.2.1宽度优先搜索（B

8、readth-first）定义：以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到