单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 绪论,AI的概念,AI的历史,AI的应用,AI 争论领域,AI 争论方法,其次章 产生式系统,产生系统根本构造,综合数据库、产生式规章、掌握系统,产生系统根本过程,匹配、选择、执行,其次章 产生式系统,问题的表示,综合数据库和规章集的描述,状态空间法(S,O,G)、问题归约法(S0,O,P),掌握策略,不行撤回方式,摸索方式,回溯方式,图搜寻方式,第三章 产生式系统的搜寻策略,“状态空间”的图描述,图的节点表示问题的状态,图的弧表示求解问题的步骤应用的规章,初始状态对应问题的信息，是图的根节点,掌握策略,回溯策略,图搜寻策略,盲目的图搜寻过程,启发式图搜寻过程,第三章 产生式系统的搜寻策略,盲目的图搜寻过程,宽度优先搜寻,深度优先搜寻,启发式图搜寻过程,启发式图搜寻算法A,最正确图搜寻算法A*,第三章 产生式系统的搜寻策略,启发式图搜寻算法A,对结点n定义评价函数f(n)=g(n)+h(n),g0，f=h爬山法,h0，f=g分支限界法,f=g=d，宽度优先搜寻,分支限界法中只考虑f值最小的一条局部路径，动态规划法,第三章 产生式系统的搜寻策略,最正确图搜寻算法A*,评价函数f(n)=g(n)+h(n)满足条件h(n)h*(n)的启发式图搜寻算法A,A*算法的改进,针对节点重复扩展问题，改进方法：,定义单调的启发函数h,待扩展节点的选择：已扩展节点的最大f值记为fm，扩展f值小于fm的节点，且选择满足条件的节点中g值最小者进展扩展。,第四章 与或图搜寻,“问题归约”对应的与或图,原始问题描述对应根节点,本原问题对应叶节点,图中的弧是1-连接符或k-连接符,与或图搜寻,查找解图,AO*算法,第四章 与或图搜寻,博弈树搜寻,二人完备博弈,目的是给出最好走步,博弈树的极大微小搜寻法,-搜寻过程,极大值层的下界值记为，微小值层的上界值记为,-剪枝,在一个分支上进展-剪枝的规章描述如下：,1 剪枝：假设任一微小值层节点的值小于或等于它任一先辈极大值层节点的值，即先辈层后继层，则可以终止该微小值层中这个MIN节点以下的搜寻，并设置这个MIN节点的最终的倒推值为。(微小值层节点的剪枝),2 剪枝：假设任一极大值层节点的值大于或等于它任一先辈微小值层节点的值，即后继层先辈层，则可以终止该极大值层中这个MAX节点以下的搜寻过程，并设置这个MAX节点的最终倒推值为。(极大值层节点的剪枝),第五章高级搜寻,局部搜寻算法,遗传算法,第五章高级搜寻,局部搜寻算法,改进1：针对陷入局部最优，依肯定概率选择邻域内的点；,改进2：针对等步长跳过全局最优，改固定步长搜寻为变步长搜寻；,改进：针对初始点可能距离局部最优点近，随机选择多个初始点。,第五章高级搜寻,遗传算法,问题解的编码,定义适应函数,交配规章,变异规章,第六章 基于规律的问题求解方法,一阶谓词规律,谓词规律演算公式,谓词演算的根本等价式及推理规章,谓词公式的标准化,前束范式,SKOLEM范式,谓词公式化为子句集,第六章 基于规律的问题求解方法,谓词规律公式化为子句集的步骤：,1.消去多余的前束量词，即在母式中无相应变量的量词。,利用蕴涵等价式消去蕴涵符号；,利用摩根律内移否认词的辖区范围，使其仅作用于原子公式。,4.变量标准化。将各约束变量换成不同的名字以免混淆。在一量词的辖区内，受该量词约束的变量名可任意设定只要没消失过，该过程不影响合式公式的真值。,5.利用量词辖区变换律把量词的辖区范围扩大至整个WFF，得到一个前束范式。即把全部的量词都集中在公式的左边，移动时不要转变其相对挨次。,6.消去存在量词，把所得的前束范式化为S范式。,7.把母式化成合取范式。反复使用结合律和安排律，将母式表达成合取范式的标准式即用连接的公式)。,8.略去全称量词。由于母式的变量均受全称量词的约束，可省略掉全称量词不显式地受全称量词量化。,9用子句集表示母式。把母式中每一个合取元称为一个子句，省去合取连接词，这样就可把母式写成集合的形式表示，每个元素就是一个子句。,10子句变量标准化。将子句集合中的变量作分别标准化，即对某些变量重新命名，使任意两个子句不会有一样的变量消失。,第六章 基于规律的问题求解方法,归结法,命题规律的归结,谓词规律的归结,置换,合一,求最一般合一mgu,第六章 基于规律的问题求解方法,归结反演产生式系统,根本算法归结反演树,搜寻策略,宽度优先策略,支持集策略,单元子句优先策略,线性输入策略,祖先过滤形策略,第六章 基于规律的问题求解方法,基于归结法的问题解答系统,提取问答的方法,归结反演树：证明目标公式是前提公式集的规律推论；,修改证明树：归结反演树中目标公式的否认式用“目标公式的否认与目标公式的析取”替代，找出目标公式中变量的例。,第七章 根本推理技术,基于规章的演绎推理,正向演绎推理,逆向演绎推理,双向演绎推理,表达式化为标准与或形,正向系统,逆向系统,skolem,函数消去事实表达式中的存在量词，化简的公式受全称量词约束。,skolem,函数（对偶形）消去目标公式中的全称量词，化简的公式受存在量词约束。,对规则的处理同上。,对规则的处理同下。,skolem,函数（对偶形）消去目标公式中的全称量词，化简的公式受存在量词约束。,skolem,函数消去事实表达式中的存在量词，化简的公式受全称量词约束。,表达式化为与或图,正向系统,逆向系统,根节点表示事实表达式；,叶节点表示单文字；,n,连接符连接具有析取关系的子表达式；,连接符连接具有合取关系的子表达式；,根节点表示目标表达式；,叶节点表示单文字；,n,连接符连接具有合取关系的子表达式；,连接符连接具有析取关系的子表达式；,演绎推理过程,正向系统,逆向系统,规则的左部和与或图的叶节点匹配；,匹配成功的规则的结论加入与或图；,直到产生一个含有以目标节点作为终止节点的解图为止。,规则的右部和与或图的叶节点匹配；,匹配成功的规则的前提加入与或图；,直到产生一个含有已知事实节点作为终止节点的解图为止。,第七章 根本推理技术,双向演绎推理,分别从正反两个方向进展推理，两个与或图分别扩展；,当正反两个方向的与或图对应的叶节点都可合一时，推理完毕。,第七章 根本推理技术,不确定性推理,概率方法,条件概率、全概率公式、,Bayes,公式,概率推理,复习要点及思考题,其次章 产生式系统:,通过八数码玩耍，了解产生式系统的问题描述(综合数据库、产生式规章、掌握系统)。,思考习题：N=3时梵塔问题的产生式系统的描述(参考P55页1.1题),第三章 产生式系统的搜寻策略,在深刻理解图搜寻算法的根底上，通过八数码问题、传教士和野人问题把握启发式图搜寻算法A和A*算法。,思考习题：,1.P55页，1.3：旅行商问题中启发式函数定义及A算法求解过程.通过列出OPEN、CLOSED表确定扩展挨次,2.P55页，1.2：滑动积木块玩耍的A算法求解：,B,B,W,W,E,B,W,E,W,B,初始状态,目标状态,第四章 与或图搜寻,理解能解节点的定义，通过实例把握AO*搜寻过程；了解博弈问题的产生式描述；把握博弈树的极大微小、-搜寻过程。,思考习题:,1.P75页 2.5题。,2.P75页 2.6题。,第五章 高级搜寻,理解组合优化问题的特点，领域的概念。,了解局部搜寻算法和遗传算法的原理、过程、和特点。,第六章 基于规律的问题求解方法,清晰一阶谓词规律的根本定义;深入理解归结原理,通过实例把握谓词规律的归结过程(包括置换和合一)；并能利用归结反演系统证明和求解一些简洁的实际问题。,思考习题：,思考习题：,1.P123页 题。,2.P124页 3.24题。,第七章 根本推理技术,能够将事实或目标表达式用与或图表达，使用F规章或B规章对与或图进展转换，利用基于规章的演绎推理对命题规律或谓词规律表示的问题进展证明。,能够对应用问题中学问建立概率表达，基于概率推理求解简洁的实际问题。,