人工智能复习大纲 (1)

复习的基本内容绪论一、人工智能的研究途径与方法二、人工智能的研究目标和策略三、人工智能的研究内容四、人工智能的前景趋势第3章图搜索与问题求解一、什么是状态图二、熟悉常用的搜索策略的特点、步骤，能够解决一些简单的问题？1、广度优先搜索2、深度优先搜索3、有界深度优先搜索4、不回溯线式搜索5、可回溯线式搜索三、什么是启发式搜索、盲目搜索四、熟悉常用的启发式搜索算法特点、步骤，能够解决一般的简单问题1、全局择优搜索2、局部择优搜索五、如何将加权状态图转换成代价树？六、加权状态图搜索算法1、分支界限法（最小代价优先法)2、最近择优法（瞎子爬山法)3、A算法七、如何表示一个问题的状态图？八、极大极小算法的计算第4章基于遗传算法的随机优化搜索一、什么是遗传算法？以及适合解决哪一类问题二、举例说明遗传算法的三种遗传操作三、基本的遗传算法步骤及流程框图四、遗传操作的特点与优势第5章基于谓词逻辑的机器推理一、掌握一些基本概念：谓词公式、子句集、归结式、替换、合一算法二、能够对一些简单的问题，运用自然演绎推理进行推理。三、熟练掌握谓词公式转化为子句集的过程。四、能够运用命题逻辑中的（或谓词逻辑中的）归结原理进行一些逻辑推理。第8章不确定性知识的表示与推理一、不确定性知识的类型二、什么是贝叶斯网络三、能够运用贝叶斯网络进行推理四、什么是模糊集合?五、熟悉模糊规则的表示以及模糊推理六、熟悉模糊关系与模糊运算第6章产生式规则的机器推理一、什么是产生式规则二、产生式系统的结构三、产生式系统的推理方式第12章专家系统一、什么是专家系统二、专家系统的特点三、专家系统的系统结构及各个组成部分的功能四、什么是快速原型法第9章机器学习与知识发现一、理解机器学习的概念二、能够运用ID3算法进行决策数学习三、了解神经网络的拓扑结构类型、神经网络的基本功能、学习规则等第10章模式识别一、什么是模式识别及模式的表示方法二、掌握统计模式识别的基本方法1、广度优先搜索：以初始节点为根节点，向下逐级扩展搜索树，即同级考察结束后，才考虑下一级接点。也称为宽度优先或横向搜索。属于树式搜索E1E2E3E4E5C4E6D1D3D2D4C3C2C1B1B2A特点：•一种高代价搜索。•策略完备。即若有解存在，则必能找到它，且找到的解还是最优解。搜索路径：A-B1-B2-C1-C2-C3-C4-D1-D2-D3广度优先搜索框图2、深度优先搜索：在搜索树的每一层始终只扩展一个子节点，不断向纵深前进，只有不能前进时，才从当前节点返回上一级接点，沿另一方向前进。E1E2E3E4E5C4E6D1D3D2D4C3C2C1B1B2A搜索顺序：A-B1-C1-C2-D1-E1-E2-E3特点：•首先扩展最新产生的节点。•如果问题树不包含无穷分支，则能够找到问题解，但不一定是最优解。•如果问题树包含无穷分支，则有可能误入无穷分支。深度优先搜索框图3.启发函数•启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)。•启发函数无固定模式。考虑思路：节点x到目标节点的某种测度度量。如对八数码问题，h(x)可以表示x与目标节点相比数码不同的位置个数。4、全局择优搜索（最好优先搜索）实质：对OPEN表中未考察的所有节点，用h(x)对其估价，选择最优的节点进行扩展。5、局部择优搜索•与全局择优的区别是:扩展节点N后仅对N的子节点按启发函数值以升序排列，放入OPEN表首部。示例2831476581324765？S0Sg3283147652831476523184765283164754545832147652837146535832147652813247658321476503E1E2E3E4E5C4E6D1D3D2D4C3C2C1B1B2A204331330545224搜索顺序：A-B1-C2-D1-E32搜索顺序：A-B1-C2-D2-E4-E5-D1-E36、加权状态图转换成代价树的方法：从初始节点起，先把每一个与初始节点相邻的节点作为该节点的子节点；然后对其他节点依次类推，但对其他节点x，不能将其父节点及祖先再作为x的子节点。图3-9交通图及其代价树7、分支界限法（最小代价优先法)思想是：每次从OPEN表中选出g(x)值最小的节点进行考察,而不管这个节点在搜索树的什么位置上。8)最近择优法（瞎子爬山法)•类似局部择优，区别在于扩展节点的标准是代价函数g(x)谓词公式转化为子句集的步骤①消去联结词“”和“”。BABA)()(ABBABA②缩小否定联结词的作用范围，使其仅作用于原子公式。AA)(BABA)(BABA)()()(xPxxxP)()(xPxxxP③重新命名变元名，使不同量词约束的变元有不同的名字。④消去存在量词消去存在量词时，变元替换分两种情况：若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数：)))(,()(()),()((xsxBxAxyxyBxAx关于x的Skolem函数若该存在量词不在任何全称量词的辖域内，则用一个常量符号代替该存在量词辖域中的相应约束变元，这样的常量符号称为Skolem常量。),()(),()(cxBxAyxyBxASkolem常量⑤消去所有全称量词。⑥化公式为合取范式)()()(CABACBA⑦适当改名，使子句间无同名变元。⑧消去合取词，以子句为元素组成的集合称为谓词公式的子句集)),(),(),()()()((zxRyxQyxPzyx)),(),(),()()()((zxRyxQyxPzyx))),(,(),(),()()((yxfxRyxQyxPyx)),(,(),(),(yxfxRyxQyxP求得子句集为)),(,(),(),(yxfxRyxQyxP。()()((,)((,)(,)))xyPxyQxyRxy))),(),((),()()((yxRyxQyxPyx)))(,())(,())(,()((xfxRxfxQxfxPx))(,())(,())(,(xfxRxfxQxfxP求得子句集为))(,())(,())(,(xfxRxfxQxfxP示例:命题逻辑中的归结原理设C1=L∨C1′,C2=﹁L∨C2′,C1′、C2′都是文字的析取式，则C1、C2的归结式为C1′∨C2′即C1∧C2=(C1-｛L1｝)∪(C2-｛L2｝归结原理分析1:怎样利用归结定理证明AB永真?即证明A⇒B?分析：①AB⇔¬A∨B永真②¬(¬A∨B)=A¬B永假③证明A¬B永假=证明A¬B的子句集不可满足)()(CACBBA证明:即证下式不可满足:)]()[()(CACBBACACBBACACBBACACBBACACBBACACBBA)()()()()()]()[()()]()([)()]()[()(CACBBA)()()(BACB)(CAACC)()()(CACBBACACACBBACBBA)()()()(解:CACBBACACBBA)()()()]()[(解:)(BACB)(CAACC谓词逻辑中的归结原理归结反演：应用归结原理证明定理的过程称为归结反演。若F为已知前提的公式集，Q为结论，用归结反演证明F⇒Q的步骤是：（1）否定Q，得到Q；（2）证明F∧¬Q不可满足（3）求F∧¬Q的子句集S；（4）应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，直到出现空子句，就证明了Q为真。1:()(()()(()(,)))FxPxyQyLxy2:()(()()(()(,)))FxPxyRyLxy:()(()())GxRxQxP1254(3)解：首先将F1，F2和G化为子句集：),()()(yxLyQxPF1：F2：)(aP),()(zaLzRG)(bR)(bQ),()(yaLyQ),(baL)(bQ图2:用贝叶斯网络表示医学知识P(S)0.4表1P(C)0.8表2SCP(T/S,C)TT0.35FT0.25TF0.011FF0.002表3表4TP(O/T)T0.85F0.15TP(A/T)T0.50F0.10表5基于贝叶斯网络的概率推理已知某人吸烟（S）,计算它患气管炎（T）的概率4.0)()()()/(TSPSPTSPSTP①011.02.04.035.08.04.0)()()()()()()(CSTPCSPSCTPSCPCSTPTCSPTSP②2822.0)/(STP已知某人患气管炎（T），计算此人吸烟（S）的概率)(2822.04.0)()/()()/(TPTPSTPSPTSP)(011.02.04.035.08.04.0)()()(STPSTPTSPTP002.06.02.025.06.08.0),(),(),(),(),,(),,()(CSTPSCPSCTPSCPSCTPSCTPSTP3.ID3算法•ID3算法是一个经典的决策树学习算法。由Quinlan于1979年提出。•基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变成最小的属性，以构造一棵熵值下降最快的决策树，到叶子节点处的熵值为0。},,,{21nsssS•计算公式：设表示样本空间，其信息熵为：niiispspSH12)(log)()(•含义：①变量的不确定性越大，熵也就越大，即熵作为一个随机事件的不确定性的量度；②一个系统越是混乱，信息熵就越高。即熵也可以说是系统有序化程度的一个度量。信息熵和条件熵设S是一个实例集(S也可以是子实例集),A为S中实例的一个属性。H(S)和H(S|A)分别称为实例集S的信息熵和条件熵,其计算公式如下:niiiPPSH1)(lb)()(其中,μi(i=1,2,…,n)为S中各实例所有可能的结论；lb即log2。mkaakkSHSSASH1)()|(其中,ak(k=1,2,…,m)为属性A的取值,Sak为按属性A对实例集S进行分类时所得诸子类中与属性值ak对应的那个子类。保险类别性别ABC男082女222)(性别SH求7219.0)51(log51-)54(log54(22男）H5850.1)3(log3)]31(log31[(22女）H0456.15850.11667219.01610)(性别SH