人工智能重点总结ciqe.docx

《人工智能重点总结ciqe.docx》由会员分享，可在线阅读，更多相关《人工智能重点总结ciqe.docx（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、人工智能重点总结第一章：发展简史（此处为简答题）1.人工智能的萌芽（1956年以前）1936年，图灵创立了自动机理论（后人称为图灵机），提出一个理论计算机模型，为电子计算机设计奠定了基础，促进了人工智能，特别是思维机器的研究。麦克洛克和皮茨于1943年提出“拟脑模型”是世界上第一个神经网络模型（MP模型），开创了从结构上研究人类大脑的途径。1948年维纳发表控制论关于动物与机器中的控制与通信的科学，不但开创了近代控制论，而且为人工智能的控制学派树立了里程碑。1、 古希腊伟大的哲学家思想家亚里士多德的主要贡献是为形式逻辑奠定了基础。形式逻辑是一切推理活动的最基本的出发点。在他的代表作工具论中，就

2、给出了形式逻辑的一些基本规律，如矛盾律、排中律，并且实际上已经提到了同一律和充足理由律。此外亚里士多得还研究了概念、判断问题，以及概念的分类和概念之间的关系判断问题的分类和它们之间的关系。其最著名的创造就是提出人人熟知的三段论。2、 英国的哲学家、自然科学家 Bacon（培根）（1561-1626），他的主要贡献是系统地给出了归纳法，成为和 Aristotle 的演绎法相辅相成的思维法则。Bacon 另一个功绩是强调了知识的作用。 Bacon 的著名警句是知识就是力量。3、 德国数学家、哲学家 Leibnitz（莱布尼茨）（1646-1716），他提出了关于数理逻辑的思想，把形式逻辑符号化，从

3、而能对人的思维进行运算和推理。他曾经做出了能进行四则运算的手摇计算机4、 英国数学家、逻辑学家 Boole（布尔）（1815-1864），他初步实现了布莱尼茨的思维符号化和数学化的思想，提出了一种崭新的代数系统-布尔代数。5、 美籍奥地利数理逻辑学家Godel（哥德尔）（1906-1978），他证明了一阶谓词的完备性定理；任何包含初等数论的形式系统，如果它是无矛盾的，那么一定是不完备的。此定理的意义在于，人的思维形式化和机械化的某种极限，在理论上证明了有些事是做不到的。6、 英国数学家 Turing(图灵)（1912-1954）,1936 年提出了一种理想计算机的数学模型（图灵机），1950

4、年提出了图灵试验，发表了计算机与智能的论文。当今世界上计算机科学最高荣誉奖励为图灵奖。名词解释：名词解释：图灵试验。当一个人与一个封闭房间里的人或者机器交谈时，如果他不能分辨自己问题的回答是计算机还是人给出时，则称该机器是具有智能的。以往该试验几乎是衡量机器人工智能的唯一标准，但是从九十年代开始，现代人工智能领域的科学家开始对此试验提出异议：反对封闭式的，机器完全自主的智能；提出与外界交流的，人机交互的智能。7、 美国数学家Mauchly，1946 发明了电子数字计算机 ENIAC 8、 美国神经生理学家 McCulloch，建立了第一个神经网络数学模型。从某种意义上可以说近代人工智能的发展，

5、 首先是从人工神 经网络研究开始的。但是由于某种原因，神经网络的研究一度进 入低潮。详细内容参见第六章人工神经元网络 9、 美国数学家 Shannon（香农）,1948 年发表了通讯的数 学理论 ，标志着信息论的诞生。10、 美国数学家、计算机科学家 McCarthy，人工智能的早期 研究者。1956 年，他和其他一些学者联合发起召开了世界上第 一次人工智能学术大会，在他的提议下，会上正式决定使用人工 智能这个词来概括这个研究方向。 参加大会的有 Minsky, Rochester, Shannon, Moore, Samuel, Selfridge, Solomonff, Simon, Ne

6、well 等数学家、 心理学家、 神经生 理学家、计算机科学家。McCarthy 也被尊为人工智能之父。2.人工智能的形成（1956-1969年）费根鲍姆于1968年研究成功第一个专家系统DENDRAL，用于质谱仪分析有机化合物的分子结构。1969年召开了第一届国际人工智能会议，标志着人工智能作为一门独立学科登上国际学术舞台。1970年人工智能国际杂志创刊。 50年代初开始有了符号处理，搜索法产生。人工智能的基本方法是逻辑法和搜索法。最初的搜索应用于机器翻译、机器定理证明、跳棋程序等。 60年代Simon由试验得到结论：人类问题的求解是一个搜索的过程，效果与启发式函数有关。叙述了智能系统的特点

7、：智能表示、智能推理、智能搜索。 Nilson发表了A* 算法（搜索方法） McCarthy建立了人工智能程序设计语言Lisp 1965年Robinson提出了归结原理。 1968年Quillian提出了语义网络的知识表示方法 1969年Minsky出了一本书感知机，给当时的神经网络研究结果判了死刑3.人工智能的发展（1970年以后）费根鲍姆1972-1976年成功开发MYCIN医疗专家系统，用于抗生素药物治疗1987年在美国召开第一届神经网络国际会议，并发起成立国际神经网络学会（INNS）1989年首次召开了中国人工控制联合会议（CJCAI） 70年代，人工智能开始从理论走向实践，解决一些实

8、际问题。同时很快就发现问题：归结法费时、下棋赢不了全国冠军、机器翻译一团糟。此时，以Feigenbaum为首的一批年轻科学家改变了战略思想，1977年提出了知识工程的概念，开展了以知识为基础的专家咨询系统研究与应用。著名的专家系统有：DENDRAL化学分析专家系统（斯坦福大学1968）；MACSYMA符号数学专家系统（麻省理工1971）；MYCIN诊断和治疗细菌感染性血液病的专家咨询系统（斯坦福大学1973）；CASNET(Causal ASsciational Network)诊断和治疗青光眼的专家咨询系统（拉特格尔斯（Rutgers）大学70年代中）；CADUCEUS(原名INTERNIS

9、T)医疗咨询系统（匹兹堡大学）；HEARSAY I 和II语音理解系统（卡内基-梅隆大学）；PROSPECTOR地质勘探专家系统（斯坦福大学1976）；XCON计算机配置专家系统（卡内基-梅隆大学1978）。应该说，知识工程和专家系统是近十余年来人工智能研究中最有成就的分支之一。 80年代，人工智能发展达到阶段性的顶峰。87,89年世界大会有67千人参加。硬件公司有上千个。Lisp硬件、Lisp机形成产品。同时，在专家系统及其工具越来越商品化的过程中，国际软件市场上形成了一门旨在生产和加工知识的新产业-知识产业。 同年代，1986年Rumlhart领导的并行分布处理研究小组提出了神经元网络的反

10、向传播学习算法，解决了神经网络分类能力有限这一根本问题。从此，神经网络的研究进入新的高潮。 90年代，计算机发展趋势为小型化、并行化、网络化、智能化。人工智能技术逐渐与数据库、多媒体等主流技术相结合，并融合在主流技术之中，旨在使计算机更聪明、更有效、与人更接近。二、三大学派：1、符号主义(Symbolicism)，又称为逻辑主义(Logicism)、心理学派(Psychlogism)或计算机学派(Computerism)，其原理主要为物理符号系统(即符号操作系统)假设和有限合理性原理。符号主义学派认为： 人工智能源于数学逻辑。代表性成果： 是启发式程序LT逻辑理论家，证明了38条数学定理，表明

11、我们可以应用计算机研究人的思维过程，模拟人类智能活动。代表人物：纽厄尔、肖西蒙和尼尔逊。2、联结主义(Connectionism)，又称为仿生学派(Bionicsism)或生理学派(Physiologism)，其原理主要为神经网络及神经网络间的连接机制与学习算法。这一学派认为： 人工智能源于仿生学，特别是人脑模型的研究代表性成果： 1943年由麦克洛奇和皮兹提出的形式化神经元模型，即M-P模型代表人物： 麦克洛奇、皮兹、霍普菲尔特、鲁梅尔哈特3、行为主义(Actionism)，又称进化主义(Evolutionism)或控制论学派(Cyberneticsism)，其原理为控制论。这一学派认为：

12、人工智能源于控制论代表性成果： 布鲁克斯的六足机器人，它被看做新一代的“控制论动物”，是一个基于感知动作模式的模拟昆虫行为的控制系统。代表人物： 布鲁克斯第二章 知识表示1. 状态空间（在搜索那里考一个大题）了解个三元状态（S，F，G），其中S:初始状态集, F：操作符集合G：目标状态集合（这里只用了解个大概就可以了，详细在搜索部分介绍）2. 问题归约（只考一个名词解释）解树：由可解节点构成，并且由这些可解节点可推出初始节点（对应初始问题）为可解节点的子树称为解树3. 谓词表示法（会在第二道大题中考4-5个应用）用谓词公式表示知识时，需要首先定义谓词，然后再用连接词把有关的谓词连接起来，形成一

13、个谓词公式表达一个完整的意义。例题 设有下列知识： 刘欢比他父亲出名。 高扬是计算机系的一名学生，但他不喜欢编程 。 为了用谓词公式表示上述知识，首先需要定义谓词： BIGGER(x,y) : x比y出名 COMPUTER ( x ) : x 是计算机系的 LIKE (x, y ) : x 喜欢 y解答：此时可用谓词公式把上述知识表示为: BIGGER ( liuhuan, father ( liuhuan )（个人觉得那个father函数最好也定义下，保险一点） COMPUTER(gaoyang)LIKE(gaoyang, programing)总结：（上面的例题应该就是考试的形式）A) 首

14、先必须知道什么是合取、析取、蕴含、否定以及两种量词的用法B) 全称量词后面跟蕴含，存在量词后面跟合取C) 必须先定义（切记），再表示。一般步骤为1提取谓词，使用类似于 P（x，y）：谓词内容 的格式定义谓词2用连接词和量词加以表示D)置换和合一那会用就OK了。只会在归结演绎推理那块最后的证明时用一下，不理解的话看那个“黄书”P81中那个反演树里用到的置换。4. 语义网络（会考画图题）只考二元关系网络例题 小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。”注意：A） 语义网络中不会考量词、继承、匹配B） 就根据题目所描述的写，不要蛋疼的写什么小明 ISA 人 ISA 动物 ISA

15、 生物 题目上怎么说怎么写就可以（老师原话） 5. 框架表示（只有概念题）1框架：我们无法把过去的经验一一都存在脑子里，而只能以一个通 用的数据结构的形式存储以往的经验。这样的数据结构称为 框架2框架的构成：框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干个侧面，而每个侧面又可拥有若干个值。一个框架的一般结构如下： 3一个框架系统（我觉得应该不会考这个，保险起见所以放上来了）下图所示为表示立方 体的一个视图的框架。图中，最高层的框架，用isa槽说明它是一个立方体，并由region槽指示出它所拥有的3个可见面A、B、E。而A、B、E又分别用3个框架来具体描述。用must be槽指示出它们

16、必须是一个平行四边形。为了能从各个不同的角度来描述物体，可以对不同角度的视图分别建立框架，然后再把它们联系起来组成一个框架系统。下图所示的就是从3个不同的角度来研究一个立方体的例子 6.过程、剧本表示不考第三章经典逻辑推理3.1归结演绎推理（问题求解&证明）定理证明即证明PQ(PQ)的永真性。根据反证法，只要证明其否定(PQ) 不可满足性即可。海伯伦(Herbrand)定理为自动定理证明奠定了理论基础；鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。在谓词逻辑中，把原子谓词公式及其否定统称为文字。如：P(x)， P(x,f(x)， Q(x,g(x) ，任何文字的析取式称为子句，

17、不包含任何文字的子句称为空子句。 3.1.1化简子句集(1) 合取范式：C1 C2 C3 Cn (2) 子句集: S= C1 ,C2 ,C3 ,Cn(3)任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S。u 子句集的性质：(1)子句集中子句之间是合取关系。(2)子句集中的变元受全称量词的约束。u 把谓词公式化成子句集的步骤：1) 利用等价关系消去“”和“” 例如公式可等价变换成2) 利用等价关系把“”移到紧靠谓词的位置上上式经等价变换后 3) 重新命名变元，使不同量词约束的变元有不同的名字上式经变换后4) 消去存在量词a.存在量词不出现在全称量词的辖域内，则只要用一个新的个体常量替换

18、受该量词约束的变元。b.存在量词位于一个或者多个全称量词的辖域内，此时要用Skolem函数f(x1,x2,xn)替换受该存在量词约束的变元。上式中存在量词($y)及($z)都位于(x)的辖域内，所以需要用Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，则替换后得到5) 把全称量词全部移到公式的左边6) 利用等价关系把公式化为Skolem标准形Skolem标准形的一般形式是其中，M是子句的合取式，称为Skolem标准形的母式。上式化为Skolem标准形后得到：7) 消去全称量词8) 对变元更名，使不同子句中的变元不同名.上式化为9) 消去合取词，就得到子句集3.1.

19、2替换的定义推论1 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即：S1的不可满足性S的不可满足性推论2 设C1与C2是子句集S中的两个子句，C12是它们的归结式。若把C12加入S中得到新子句集S2，则S与S2在不可满足的意义上是等价的，即：S2的不可满足性S的不可满足性推论1及推论2保证了我们可以用归结的方法来证明子句集S的不可满足性。为了要证明子句集S的不可满足性，只要对其中可进行归结的子句进行归结，并把归结式加入子句集S，或者用归结式替换它的亲本子句，然后对新子句集(S1或者S2)

20、证明不可满足性就可以了。如果经过归结能得到空子句，则立即可得原子句集S是不可满足的结论。在命题逻辑中，对不可满足的子句集S，归结原理是完备的。即，若子句集不可满足，则必然存在一个从S到空子句的归结演绎；若存在一个从S到空子句的归结演绎，则S一定是不可满足的。3.1.3归结u 命题逻辑中的归结原理定义4.9 若P是原子谓词公式，则称P与P为互补文字。在命题逻辑中，P为命题。定义4.10 设C1与C2是子句集中的任意两个子句。如果C1中的文字L1与C2中文字L2互补，那么从C1和C2中分别消去L1和L2，并将两个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结。称C12为C1和C2的

21、归结式，C1和C2为C12的亲本子句。例4.9 设C1=PQ, C2=QR, C3=PC1与C2归结得到：C12=PRC12与C3归结得到：C123=Ru 谓词逻辑中的归结原理在谓词逻辑中，由于子句中含有变元，所以不能像命题逻辑那样直接消去互补文字，而需要先用最一般合一对变元进行代换，然后才能进行归结。例如,设有两个子句C1=P(x)Q(x), C2= P(a)R(y)由于P(x)与P(a)不同，所以C1与C2不能直接进行归结。但是若用最一般合一=a/x对两个子句分别进行代换：C1 =P(a)Q(a) C2 = P(a)R(y)就可对它们进行归结，得到归结式：Q(a)R(y)u 归结反演及其示

22、例*如欲证明Q为P1,P2,Pn的逻辑结论，只需证(P1P2Pn)Q是不可满足的，或证明其子句集是不可满足的。而子句集的不可满足性可用归结原理来证明。 应用归结原理证明定理的过程称为归结反演。 设F为已知前提的公式集，Q为目标公式(结论)，用归结反演证明Q为真的步骤是：a) 否定Q，得到Q；b) 把Q并入到公式集F中，得到F, Q;c) 把公式集F, Q化为子句集S;d) 应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。例4.12 已知求证：G是F的逻辑结论。证明：首先把F和G化为子句集：然后进行归结：(

23、6)A(x,y)B(y)由(1)与(3)归结，f(x)/z(7)B(b)由(4)与(6)归结，a/x,b/y(8)NIL由(5)与(7)归结所以G是F的逻辑结论。上述归结过程如下图归结树所示。u 应用归结原理求取问题的答案及其示例 归结时，并不要求把子句集中所有的子句都用到。 在归结过程中，一个子句可以多次被用来进行归结。求解的步骤：1. 把已知前提用谓词公式表示出来，并且化为相应的子句集。设该子句集的名字为S。2. 把待求解的问题也用谓词公式表示出来，然后把它否定并与谓词Answer构成析取式。Answer是一个为了求解问题而专设的谓词。3. 把此析取式化为子句集，并且把该子句集并入到子句集

24、S中，得到子句集S。4. 对S应用归结原理进行归结。5. 若得到归结式Answer，则答案就在Answer中。例4.16 设A,B,C三人中有人从不说真话，也有人从不说假话。某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者？解：设用T(x)表示x说真话。T(C)T(A)T(B)T(C)T(A)T(B)T(A)T(B)T(C)T(A)T(B)T(C)T(B)T(A)T(C)T(B)T(A)T(C)T(C)T(A)T(B)T(C)T(A)T(B)把上述公式化成子句集，得到S：(1)T(

25、A)T(B)(2)T(A)T(C)(3)T(C)T(A)T(B)(4)T(B)T(C)(5)T(C)T(A)T(B)(6) T(A)T(C)(7)T(B)T(C)下面先求谁是老实人。把T(x)Ansewer(x)并入S得到S1。即多一个子句：(8)T(x)Ansewer(x)应用归结原理对S1进行归结：(9)T(A)T(C)(1)和(7)归结(10)T(C) (6)和(9)归结(11)Ansewer(C)(8)和(10)归结所以C是老实人，即C从不说假话。下面证明A不是老实人，即证明T(A)。对T(A)进行否定，并入S中，得到子句集S2，即S2比S多如下子句：(8)(T(A), 即T(A)应用

26、归结原理对S2进行归结：(9)T(A)T(C) (1)和(7)归结(10)T(A) (2)和(9)归结(11)NIL (8)和(10)归结所以A不是老实人。同样可以证明B也不是老实人。u 应用归结原理的练习1. 设已知： （1）如果x是y的父亲，y是z的父亲，则x是z的祖父； （2）每个人都有一个父亲。 试用归结演绎推理证明：对于某人u，一定存在一个人v，v是u的祖父。 2. 张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员 A 说“赵与钱中至少有一人作案”；侦察员 B 说“钱与孙中至少有一人作案”；侦察员 C 说“孙与李中至少有一人作案”；侦察员 D 说“赵与孙中至少有一人与此案无关

27、”；侦察员 E 说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都是可信的，试用归结演绎推理求出谁是盗窃犯。3.2不确定性-只考模糊理论u 简单模糊推理知识中只含有简单条件，且不带可信度因子的模糊推理称为简单模糊推理。合成推理规则：对于知识IF x is A THEN y is B首先构造出A与B之间的模糊关系R，然后通过R与证据的合成求出结论。如果已知证据是x is A且A与A可以模糊匹配，则通过下述合成运算求取B：B=AR如果已知证据是y is B且B与B可以模糊匹配，则通过下述合成运算求出A：A=RBu 模糊集的运算模糊集上的运算主要有：包含、交、并、补等等。1. 包含运算定义2

28、.14 设A，BF(U)，若对任意uU，都有B(u)A(u)成立，则称A包含B，记为 。2. 交、并、补运算定义2.15 设A，BF(U)，以下为扎德算子例2.9 设U=u1,u2,u3，A=0.3/u1+0.8/u2+0.6/u3B=0.6/u1+0.4/u2+0.7/u3则：AB=(0.30.6)/u1+(0.80.4)/u2+(0.60.7)/u3 =0.3/u1+0.4/u2+0.6/u3 AB=(0.30.6)/u1+(0.80.4)/u2+(0.60.7)/u3 =0.6/u1+0.8/u2+0.7/u3 A=(1-0.3)/u1+(1-0.8)/u2+(1-0.6)/u3 =0.

29、7/u1+0.2/u2+0.4/u33.3搜索-广度优先、深度优先、全局择优三选一u 状态空间的一些基本概念1) 很多问题的求解过程都可以看作是一个搜索过程。问题及其求解过程可以用状态空间表示法来表示。2) 状态空间用“状态”和“算符”来表示问题。状态状态用以描述问题在求解过程中不同时刻的状态，一般用一个向量表示：SK=(Sk0,Sk1,)算符使问题从一个状态转变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。状态空间由所有可能出现的状态及一切可用算符所构成的集合称为问题的状态空间。3) 采用状态空间求解问题，可以用下面的一个三元组表示：(S,F,G)其中S是问题初始状

30、态的集合；F是算符的集合；G是目标状态的集合。采用状态空间表示方法，首先要把问题的一切状态都表示出来，其次要定义一组算符。问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解就是从初始状态到目标状态所采用算符的序列。使用算符最少的解称为最优解。对任何一个状态，可使用的算符可能不止一个。这样由一个状态所生成的后继状态就可能有多个。此时首先对哪一个状态进行操作，就取决于搜索策略。u OPEN表和CLOSE表OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。CLOSE表用于存放将要扩展的节点。

31、对一个节点的扩展是指：用所有可适用的算符对该节点进行操作，生成一组子节点u 搜索的一般过程1. 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；2. 检查OPEN表是否为空，若为空则问题无解，退出；3. 把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；4. 考察节点n是否为目标节点。若是，则求得了问题的解，退出；5. 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；6. 针对M中子节点的不同情况，分别进行如下处理：1) 对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放

32、入OPEN表；（不在OPEN表）2) 对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中）3) 对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中）7. 按某种搜索策略对OPEN表中的节点进行排序；8. 转第2步。u 一些说明 一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。 一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作

33、为其它节点的子节点被生成过，当前又作为另一个节点的子节点被再次生成。此时，它究竟应选择哪个节点作为父节点？一般由原始节点到该节点的代价来决定，处于代价小的路途上的那个节点就作为该节点的父节点。 在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。 如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败。 通过搜索得到的图称为搜索图，搜索图是状态空间图的一个子集。由搜索图中的所有节点及反向指针所构成的集合是一棵树，称为搜索树。根据搜索树可给出问题的解。u 盲目搜索 广度优先搜索广度优先搜索按照“先扩展出的节点先被考

34、察”的原则进行搜索；n 基本思想从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n1层的节点进行扩展。n OPEN表中节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。n 广度优先搜索过程1) 把初始节点S0放入OPEN表。2) 如果OPEN表为空，则问题无解，退出。3) 把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4) 考察节点n是否为目标节点。若是，则求得了问题的解，退出。5) 若节点n不可扩展，则转第2步。6) 扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针

35、，然后转第2步。n 广度优先搜索的本质是，以初始节点为根节点，在状态空间图中按照广度优先的原则，生成一棵搜索树n 优点：总可以得到解，且是路径最短的解。缺点：盲目、效率低。n 重排九宫的广度优先搜索 深度优先搜索-考有界深度优先搜索的可能性很大深度优先搜索按照“后扩展出的节点先被考察”的原则进行搜索；n 深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。 n 深度优先搜索过程1) 把初始节点S0放入OPEN表。2) 如果OPEN表为空，则问题无解，退出。3) 把OPEN表的第一个节点（记为节点n

36、）取出放入CLOSE表。4) 考察节点n是否为目标节点。若是，则求得了问题的解，退出。5) 若节点n不可扩展，则转第2步。6) 扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。n 深度优先搜索的本质：以初始节点为根节点，在状态空间图中按照深度优先的原则，生成一棵搜索树。n 重排九宫的深度优先搜索 有界深度优先搜索：n 基本思想对深度优先搜索引入搜索深度的界限（设为dm），当搜索深度达到了深度界限，而仍未出现目标节点时，就换一个分支进行搜索。n 搜索过程1) 把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。2) 如果OPEN表为空，则

37、问题无解，退出。3) 把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4) 考察节点n是否为目标节点。若是，则求得了问题的解，退出。5) 若节点n的深度d(n)=dm，则转第2步（此时节点n位于CLOSE表，但并未进行扩展）。 6) 若节点n不可扩展，则转第2步。7) 扩展节点n，将其子节点放入OPEN表的首部，为每一个子节点都配置指向父节点的指针，将每一个子节点的深度设置为d(n)+1，然后转第2步。n 重排九宫的有界深度优先搜索（设深度界限dm=4）u 启发式搜索启发式搜索采用问题自身的特性信息，以指导搜索朝着最有希望的方向前进。这种搜索针对性较强，因而效率较高。 启发性信息与

38、估价函数：n 可用于指导搜索过程，且与具体问题有关的信息称为启发性信息。n 用于评估节点重要性的函数称为估价函数。其一般形式为：f(x) = g(x)+h(x)n 其中g(x)表示从初始节点S0到节点x的代价；h(x)是从节点x到目标节点Sg的最优路径的代价的估计，它体现了问题的启发性信息。h(x)称为启发函数。n g(x) 有利于搜索的完备性，但影响搜索的效率。h(x)有利于提高搜索的效率，但影响搜索的完备性。 全局择优搜索全局择优搜索按照“哪个节点到目标节点的估计代价小就先考察哪个节点”的原则进行搜索；广度优先搜索、代价树的广度优先搜索是全局择优搜索的特例。 n 基本思想每当要选择下一个节

39、点进行考察时，全局择优搜索每次总是从OPEN表的全体节点中选择一个估价值最小的节点。n 搜索过程1) 把初始节点S0放入OPEN表，计算f(S0)。2) 如果OPEN表为空，则问题无解，退出。3) 把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4) 考察节点n是否为目标节点。若是，则求得了问题的解，退出。5) 若节点n不可扩展，则转第2步。6) 扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序，然后转第2步。n 重排九宫问题的全局择优搜索树设估价

40、函数为：f(x)=d(x)+h(x)其中，d(x)表示节点x的深度，h(x)表示节点x的格局与目标节点格局不相同的牌数。第四章 神经网络与遗传计算1. 神经网络（只考概念）*此处老师重点为：神经元的工作特性。但无奈两个课本+ppt均找不到原话。所以按下边的内容自己总结一下吧。1） 生物神经元的基本工作机制一个神经元有两种状态-兴奋和抑制。平时处于抑制状态的神经元，其树突和胞体接受其它神经元经由突触传来的兴奋电位，多个输入在神经元中以代数和的方式叠加；如输入兴奋总量超过阈值，神经元被激发进入兴奋状态，发出输出脉冲，由轴突的突触传递给其它神经元。2） 生物神经特性（1） 并行分布处理的工作模式（2

41、） 神经系统的可塑性和自组织性。（3） 信息处理与信息存贮合二为一。（4） 信息处理的系统性（5） 能接受和处理模糊的、模拟的、随机的信息。（6） 求满意解而不是精确解.人类处理日常行为时，往往都不是一定要按最优或最精确的方式去求解，而是以能解决问题为原则，即求得满意解就行了。 （7） 系统具有鲁棒性和容错性3） 人工神经元模型 2. 遗传计算（此处为简答题，但老师没有给简答题的范围，所以看着重要的背）1） 进化计算包括:l 遗传算法(genetic algorithms，GA) l 进化策略(evolution strategies) l 进化编程(evolutionary programm

42、ing) l 遗传编程(genetic programming)。2） 遗传操作简单遗传算法的遗传操作主要有三种：选择（selection）、交叉（crossover）、变异（mutation）。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。交叉操作的简单方式是将选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。变异操作的简单方式是改变数码串的某个位置上的数码。3） 遗传算法的特点6. 遗传算法是对参数集合的编码而非针对参数本身进行变化；7. 遗传算法是从问题解的编码组开始而非

43、从单个解开始搜索；8. 遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；9. 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。4） 算法停止条件：D) 完成了预先给定的进化代数则停止；E) 种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。5） 遗传算法流程6） 遗传算法的基本机理一般的遗传算法由四个部分组成:编码机制、控制参数、适应度函数、遗传算子第五章 机器学习此处只考概念，若11班学了这一章，就考；若11班没学，则不考。C） 类比学习类比学习是利用二个不同领域（源域、目标域）中的知识相似性，可以通过类比，从源域的

44、知识（包括相似的特征和其它性质）推导出目标域的相应知识，从而实现学习。所以，类比学习系统可以使一个已有的计算机应用系统转变为适应于新的领域，来完成原先没有设计的相类似的功能。D） 解释学习 解释学习兴起于20世纪80年代中期，根据任务所在领域知识和正在学习的概念知识，对当前实例进行分析和求解，得出一个表征求解过程的因果解释树，以获取新的知识。E） 机械学习 又称为记忆学习或死记硬背式的学习。这种学习方法直接记忆或存储环境提供的新知识，并在以后通过对知识库的检索来直接使用这些知识，而不再需要进行任何的计算和推导。感谢lee年复一年月复一月日复一日的拷ppt，感谢One Piece牺牲自习室看妹子的机会回来整理重点，感谢Armo对重点中最为复杂的一章的总结。1. ：lee 第二章：One Piece第三章 ：Armo 第四、五章：大雪无痕我想说的是，重点不是万能的，概念题简答题肯定有意想不到的，抛开课本背重点是犯傻的，两手都要抓两手都要硬才是无敌的。 来自#10 I-226