《西工大计算智能知识点整理研究生考试专业课_研究生考试-专业课.pdf》由会员分享，可在线阅读，更多相关《西工大计算智能知识点整理研究生考试专业课_研究生考试-专业课.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章 绪 论 1.图灵测试 一组人类裁判以敲击键盘的形式与电脑“对话”。如果裁判认定电脑为人的比例超过 30%，则电脑通过测试。2.人类智能活动的能力是人类在认识世界和改造世界的活动中，由脑力劳动表现出来的能力。认识和理解世界环境的能力 提出概念、建立方法、进行演绎和归纳推理、做出决策的能力 学习取得经验、积累知识的能力 自我适应的能力 联想、推理、判断、决策的能力 3.智能的本质 感知能力、记忆和思维能力、学习能力、自适应能力、行为能力 4.思维种类 逻辑思维、形象思维、顿悟思维 5.人工智能的含义 用计算机来完成能表现出人类智能的任务学科 模仿人脑所从事的推理、学习、思考、规划等思维活动
2、 关于知识的科学 执行拟人的任务 6.没有计算机的出现，人工智能就无法得到应用 7.人类智能与人工智能 本质区别:物质载体、逻辑模拟、活动规律、目的性、能动性、适应性 8.研究方法 符号主义、联结主义、行为主义 9.计算智能是人工智能的深化与发展 人工智能是以知识库为基础、那么计算智能则是以模型为基础、以分步、并行、仿生计算为特征含数据、算法和实现的信息系统。前者强调规则的形式和表示，后者强调模型的建立和构成；前者依赖专家知识，后者强调系统的自组织、自学习和自适应。10.计算智能的主要方法有人工神经网络、遗传算法、遗传程序、演化程序、局部搜索、模拟退火等等 11.计算智能的特征与应用 智能性：
3、包括算法的自适应性，自组织性，算法不依赖于问题本身的特点，具有通用性 并行性：算法基本上是群体协作的方式对问题进行优化求解，非常适合大规模并行处理 鲁棒性:算法具有很好的容错性，同时对初始条件不敏感，能在不同条件下寻找最优解 12.计算智能发展趋势 分布式人工智能、Internet 及数据库的挖掘、智能系统之间的交互与通信、智能系统之间的合作等 13.第二章 知识表示 一.知识的基本概念 1.相关概念：数据：指为描述具体事物引入的数字、符号等 信息：指不同数据组成的一种结构（如“建国 50 岁”）数据与信息的关系：数据是信息的载体和表示，信息是数据的语义 知识：对信息进行智能性加工后形成的对客
4、观世界的规律性认识*。知识的一般概念 人类认识与经验的总和 人们对客观事物的认识及解决问题的方法和策略 以高度概括形式对客观事实及相互关系的整合 试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步
5、并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和知识的三个代表性定义：经过消减、塑造、选择和转换的信息；由特定领域的描述、关系和过程组成；知识=事实+信念+启发式。2.人类对客观世界感知 四个层面：4 智能（Intelligence）3 知识（Knowledge）2 信息（Information）1 数据（Data）3.知识的特性 相对正确性、可表示性、不确定性、关联性 4.知识的分类 常识性知识、领域性知识（作用范围）确定性知识、不确定性知识（确定性）逻辑性知识、形象性知识（结构及表现形式
6、）5.知识的表示方法 对知识的表示过程就是将知识编码成某种数据结构的过程 一阶谓词逻辑表示法（First Order Predicate）产生式表示法（Production）框架表示法（Framework）语义网络法（Semantic Network）脚本表示法（Script）6.如何选择合适的表示方法？选择知识表示要根据所处理的具体领域和实际情况荀泽相应的知识表示方法 充分表示领域知识 有利于对知识的利用 便于理解和实现 便于对知识的组织、管理与维护 7.智能活动过程的模拟 知识表示 知识利用 知识获取 二谓词逻辑表示 1.命题逻辑 命题 是能够判断真或假的陈述句 通常用大写字母来表示，如
7、A,B,P,Q等 命题的真假值一般用 T 或 F 来表示 表示单一意义的命题，称之为 原子命题。原子命题通过“连接词”构成 复合命题。2.连接词 试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步
8、并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 “”表示“非”复合命题 P为真，当且仅当 P为假。“”表示“与（合取）”复合命题“PQ”为真，当且仅当 P和 Q都为真。“”表示“或（析取）”复合命题“PQ”为真，当且仅当 P、Q两者之一为真。“=（）”表示“蕴含”复合命题“PQ”为假，当且仅当 P为真且 Q为假。与自然语言不一样，蕴涵式的前件和后件可以没有内在联系 “”表示“等价”复合命题“PQ”为真，当且仅当 P、Q同时为真、或者同时为假。与自然语言不一样，等价式的 2个命题可以没有内在
9、联系 等价式具有下列性质：自反性：对于任意公式 A，有 A A 对称性：对于任意公式 A和 B，若 A B，则 B A 传递性：对于任意公式 A，B和 C，若 A B，B C，则 A C 3.命题定律 双否律 （P）P 德摩根律 （P Q）P Q （P Q）P Q 交换律 P Q Q P P Q Q P 结合律 P (Q R)(P Q)R P (Q R)(P Q)R 分配率 P (Q R)(P Q)(P R )P (Q R)(P Q)(P R )等幂律 P P P P P P 同一律 P T*P P F*P 零律 P F*F*P T*T*试人类智能活动的能力是人类在认识世界和改造世界的活动中由
10、脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 互补率 P P F*P P T*吸收率 P (Q
11、 R)P P (Q R)P 4.设 A和 B是两个公式，若 A B为永真式，则称 A蕴含 B，记作 A=B 5.主要的推理式 假言推理 P P Q -P (P Q)=Q Q 假言三段论或演绎 P Q Q R -(P Q)(Q R)=(P R)P R 拒取式 P Q Q-(P Q)(Q)=(P)P 简化式 P Q-(P Q)=P P 析取三段论 P Q P-(P Q)(P)=Q Q 二难推论 P R Q R -(P R)(Q R)=(P Q)R 试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学
12、习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和(P Q)R 6.谓词逻辑表示法的特点 自然性：符合人类对问题的直觉理解；精确性：只有“真与假”的值；严密性：谓词逻辑具有严格的形式定义以及推理规
13、则；利用推理规则及有关定理证明技术，可以从已知事实推出新的事实，或证明作出的假设。易实现：用谓词逻辑表示的知识可以比较容易地转换为计算机内部形式，易于模块化，便于对知识的增加、修改、删除。用其表达的知识也易于计算机上实现。7.谓词逻辑局限性 不能揭示不确定的知识：只能表示精确性知识，不能表示不确定的知识，表示的知识范围受到了局限。易形成组合爆炸：在推理过程中，其推理根据事实数目的增大及盲目使用推理规则，可能形成组合爆炸。效率低：将推理与知识语义割裂，降低推理效率。三产生式表示法 1.事实的表示 事实通常是用三元组成四元组来表示。对确定性知识，一个事实可用一个三元组(对象,属性,值)或(关系,对
14、象 1,对象 2)来表示。对不确定性知识,一个事实可用一个四元组(对象,属性,值,可信度因素)来表示。2.规则的表示 规则描述的是事实间的因果关系，规则的产生式表示形式称为产生式规则。其基本形式为:P Q 或者:IF P THEN Q 其中,P是产生式的前提,也称前件,由事实的逻辑组合来构成,Q是产生式的结论或操作,也称后件.产生式的含义是:如果前提 P满足,则可推出结论 Q或执行 Q规定的操作。3.产生式系统的基本结构 控制系统 规则库 综合数据库 4.优点 自然性：接近人类对因果关系知识的思维判断形式 模块性：与推理机构相互独立，利于增加、删除、修改和扩充 有效性：可表示不确定性知识、启发
15、性知识 一致性：规则具有固定表示形式 缺点 效率较低 存在组合爆炸：匹配-冲突消解-执行；不能表示结构性知识 四语义网络 1.语义网络是一个有向图，其中节点表示个体，而弧表示两个体间的二元关系，弧上标记关系模型名称，单一个体就由一结点表示。2.语义关联 试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工
16、智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 类属关系：是一种、是一员、是一个 聚类关系：是一部分 属性关系：有、能 推论关系：推论出 时间、位置关系：在前、在后、在上、在下、接近、相似等 3.语义网络主要特点：结构性 把事物的属性以及事物间的各种语义联系显式地表示出来，是一种结构化的知识表示方法。在这种方法中，下层结点可以继承、新增、变异上层结点的属性。联想性 本来是作为人类联想
17、记忆模型提出来的，它着重强调事物间的语义联系，体现了人类的联想思维过程。自然性 这种带有标识的有向图，可比较直观地把知识表示出来，符合人们表达事物间关系的习惯，并且与自然语言语义网络之间的转换也比较容易实现。复杂性 语义网络表示知识的手段是多种多样的，这虽然对其表示带来了灵活性，但同时也由于表示形式的不一致，使得它的处理增加了复杂性。五框架表示法 1.框架：是一种描述对象（事物、事件或概念等）属性的数据结构，在框架理论中，框架是知识表示的基本单位。2.一个框架由若干个“槽”（Slot）结构组成，每个槽又可分为若干个“侧面”。一个槽：用于描述所论对象某一方面的属性；一个侧面：用于描述相应数学的一
18、个方面。槽和侧面所具有的属性值分别称为槽值和侧面值。第三章 基本推理原理 一推理的基本概念 1.推理：按某种策略由已知判断推出另一判断的思维过程 已知判断：包括已掌握的与求解问题有关的知识及关于问题的已知事实 推理的结论：由已知判断推出新判断 推理机：推理由程序程序实现，称为推理机 2.推理的基本任务：从一种判断推出另一种判断 推理的分类：演绎推理、归纳推理、默认推理 3.演绎推理 推理过程：从已知的一般性知识推出组合在这些已知知识中适合于某种个别情况结论的过程 三段论式演绎推理：大前提：已知的一般性知识或假设 小前提：关于所研究的具体情况或个别事实的判断 结论：由大前提推出的适合于小前提所示
19、情况的新判断 个别经验:无意发现一种药治病 一般性认识：经验累积 结论：得出结论：这种药可以治这种病 4.归纳推理 试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和
20、实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理 完全归纳推理：在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性 不完全归纳推理：只考察了相应事物的部分对象就得出了结论 5.默认推理 又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理 按所用知识的确定性分类：确定性推理、不确定性推理 按推理过程的单调性分类：单调推理、非单调推理 二自然演绎推理 从一组已知的事实出发，直接运用命
21、题逻辑或谓词逻辑中的推理规则推出结论的过程 三归结反演推理 应用归结原理证明定理的过程称为归结反演。1.谓词公式转换成相应子句集的步骤（1）利用等价谓词关系消去谓词公式中的“”和“”QPQP)()(QPQPQP（2）减少否定符号的辖域，将每个否定符号移到仅靠谓词的位置，使得每个否定符号最多作用于一个谓词。双重否定律 ()PP 德摩根律 ()PQPQ ()PQPQ 量词转换律 ()()x PxP ()()x PxP （3）对变元标准化。在一个量词的辖域内，将谓词公式中受该量词约束的变元全部用另一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。（4）消去存在量词 若存在量词不出现在全
22、称量词的辖域内（即左边没有全称量词），只用一个新的个体常量（称为 Skolem常量）替换受该存在量词约束的变元，即可消除该存在量词。若存在量词位于一个或多个全称量词的辖域内，则需要 Skolem函数替换受该存在量词约束的变元，再消去该存在量词。量词消去原则：存在量词。将该量词约束的变量用任意常量（a，b 等）或任意变量的函数（f(x)，g(y)等）代替。左边有任意量词的存在量词，消去时该变量改写成为任意量词的函数；如没有，试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能
23、力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和改写成为常量。任意量词。简单地省略掉该量词。（5）化身前束范式 将所有量词都移到公式左边，并且不改变相对顺序。（6）化为 Skolem标准型 其标准型一般形式为 121
24、2()()()(,)nnxxx M x xxM，其中为合取式使用如下等价关系()()()PQRPQPR（7）消去全称量词 由于母式中全部变元均受到全称量词的约束，并且全称量词的次序已无关紧要，因此可省掉全称量词。（8）消去合取词 在母式中消去所有合取词，将母式用子句集的形式表示出来，其中，子句集中的每一个元素都是一个子句。（9）更换变元名称 对子句集中的某些变元重新命名，使得任意两个子句中不出现相同的变元名。（10）定理：设有谓词公式 F，其标准形的子句集为 S，则 F 不可满足的充要条件是 S不可满足。要证明一个谓词公式是不可满足的，只要证明其相应的标准子句集是不可满足的 2.鲁宾逊归结原理
25、 检查子句集 S中是否包含空子句，若包含，则 S不可满足；若不包含，就在子句集中选择合适的子句进行归结，一旦通过归结能推出空子句集，就说明子句集 S是不可满足的。（1）、命题逻辑中的归结原理（2）、谓词逻辑中的归结 3.使用归结原理证明问题 4.不确定推理 建立在不确定性知识和证据基础上的推理。引起不确定性的因素：知识的不完备、不精确；原因的多样性；知识描述的模糊性；不一致性；随机性；解决问题的方案不唯一；第四章 搜索原理 求解：推理和搜索。一搜索原理概述 1.概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。试
26、人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建
27、立和2.搜索策略的任务 确定如何选取规则的方式 3.搜索的分类 盲目搜索：无信息引导的搜索策略 启发式搜索：有信息引导的搜索 4.状态空间、搜索空间与解路径 状态空间:一个有向图，节点可表示问题的各种状态（综合数据库），及节单之间的弧代表一些操作（产生式规则），可以把一种状态导向另一种状态。解路径:在状态空间图中，从初始点到目标节点的一条路径称为解路径 搜索空间：为找到解路径而搜索的空间称为搜索空间 5.搜索成本 规则控制费用：即为决定选取可用规则而花费的费用 规则应用费用：即使用规则所花费的费用 6.搜索结果 最优结果 次优结果 任意结果 二、盲目搜索策略 1.一般图搜索算法 (1)把初始节
28、点 S0放入 Open表，并建立目前仅包含 S0的图 G；(2)检查 Open表是否为空，若为空，则问题无解，失败推出；(3)把 Open表的第一个节点取出放入 Closed表，并记该节点为节点 n；(4)考察节点 n 是否为目标节点。若是则得到了问题的解，成功退出；(5)扩展节点 n，生成一组子节点。把这些子节点中不是节点 n 先辈的那部分子节点记入集合 M，并把这些子节点作为节点 n 的子节点加入 G中 (6)针对 M 中子节点的不同情况，分别作如下处理：对那些没有在 G中出现过的 M 成员设置一个指向其父节点（即节点 n）的指针，并把它放入 Open表。（新生成的）对那些原来已在 G中出
29、现过，但还没有被扩展的 M 成员，确定是否需要修改它指向父节点的指针。（原生成但未扩展的）对于那些先前已在 G中出现过，并已经扩展了的 M 成员，确定是否需要修改其后继节点指向父节点的指针。（原生成也扩展过的）(7)按某种策略对 Open表中的节点进行排序。(8)转第(2)步。试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的
30、任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 2.深度优先搜索 算法描述 (1)把初始节点 S0放入 Open表中；(2)如果 Open表为空，则问题无解，失败退出；(3)把 Open表的第一个节点取出放入 Closed表，并记该节点为 n；(4)考察节点 n 是否为目标节点。若是，则得到问题的解，成功退出；(5)若节点 n 不可扩展，则转第(2)步；(6)
31、扩展节点 n，将其子节点放入 Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。3.有界深度优先搜索 开 始把 S放入 OPEN表OPEN为空表？失 败把 第 一 个 节 点（n）从OPEN移 至 CLOSED表n为目标节点？成 功把 n后 的 结 点 放 入 OPEN表 的 末 端，提 供 返 回 节点 n的 指 针修改指针方向重排 OPEN表是否是否图 3.1 图 搜 索 过 程 框 图试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适
32、应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和对深度优先搜索引入搜索深度的界限(设为 dm)，当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。搜索算法：(1)把初始节点 S0放入 Open表,置 S0
33、的深度 d(S0)=0；(2)如果 Open表为空,则问题无解,退出；(3)把 Open表的第一个节点(记为节点 n)取出,放入 Closed表；(4)考查节点 n 是否为目标节点.若是,则求得了问题的解,退出；(5)如果节点 n 的深度 d(节点 n)=dm,则转第(2)步；(6)若节点 n 不可扩展,则转第(2)步；(7)扩展节点n,将其子节点放入 Open表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步。4.宽度优先搜索 基本思想：开 始把 S放入 OPEN表OPEN为空表？失 败把 OPEN表 中 的 第 一 个节 点 n移 至 CLOSED表节点 n 的深度是否等于深度
34、界限？扩 展 节 点 n，把 其 后裔 放 入 OPEN表 的 末 端是否否图 3.6 有 界 深 度 优 先 搜 索 算 法 框 图S是否为目标节点？成 功是是否有任何后继节点为目标节点？是成 功是否试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体
35、逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 从初始节点 S0开始逐层向下扩展，在第 n 层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。搜索算法：(1)把初始节点 S0放入 Open表中；(2)如果 Open表为空，则问题无解，失败退出；(3)把 Open表的第一个节点取出放入 Closed表，并记该节点为 n；(4)考察节点 n 是否为目
36、标节点。若是，则得到问题的解，成功退出；(5)若节点 n 不可扩展，则转第(2)步；(6)扩展节点 n，将其子节点放入 Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。5.深度优先搜索与宽度优先搜索唯一区别 宽度优先搜索是将节点 n 的子节点放入 Open表的尾部，而深度优先搜索试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维
37、活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和是把节点 n 的子节点放入 Open表的首部。仅此一点不同，就使得搜索的路径完全不一样。6.等代价搜索 代价图:当搜索图中的节点之间的耗散不是单位耗散时，这样的图成为代价图。搜索算法:(1)把起始节点 S放到 Open表中。如果此起始节点为一目标节点则求得一个解。否则令 g(S)0。(2
38、)如果 Open是个空表，则没有解而失败退出。(3)从 Open表中选择一个节点 i，使其 g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点 i(要是有目标节点的话)，否则,就从中选一个作为节点。把节点 i 从 Open表移至扩展节点表 Closed中。(4)如果节点 i 为目标节点，则求得一个解。(5)扩展节点 i。如果没有后继节点，则转向第(2)步。(6)对于节点 i 的每个后继节点 j，计算 g(j)g(i)十 c(i，j)，并把所有后继节点 j 放进Open表。提供回到节点 i 的指针。(7)转向第(2)步。三 启发式搜索 1.概念：又称为有信息搜索，利用问题拥有
39、的启发信息引导搜索，达到减少搜索范围，降开始把S放入OPEN 表OPEN 为空表？失败把具有最小g(i)值的节点i从OPEN表中的第一个节点n移至CLOSED 表节点 i 是否为目标节点？扩展节点 i，计算其后继节点j的g(i)值。把后继节点放入OPEN表是否否图3.8 等代价搜索算法框图S是否为目标节点？成功是成功是否令g(s)=0试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人
40、脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和低问题复杂度的目的。2.三种基本启发式信息搜索策略：(1)节点选择：根据启发式信息决定要扩展的下一个节点（最有希望的节点）(2)操作选择：控制下层子节点产生，以避免盲目地同时生成所有可能的节点。(3)剪枝技术：在图搜索中对某些节点从图中剪去。3.评价函数 评
41、价函数用来估计节点重要性的函数。评价函数 f(n)被定义为从初始节点 S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为：f(n)=g(n)+h(n)其中，g(n)是从初始节点 S0到节点 n 的实际代价；h(n)是从节点 n 到目标节点 Sg的最优路径的估计代价。4.A算法 A算法也被称为启发式搜索算法。可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。全局择优：从 Open表的所有节点中选择一个评价函数值最小的一个进行扩展。局部择优：仅从刚生成的子节点中选择一个评价函数值最小的一个进行扩展。全局择优搜索 A算法
42、描述 (1)把初始节点 S0放入 Open表中，f(S0)=g(S0)+h(S0)；(2)如果 Open表为空，则问题无解，失败退出；(3)把 Open表的第一个节点取出放入 Closed表，并记该节点为 n；(4)考察节点 n 是否为目标节点。若是，则找到了问题的解，成功退出；(5)若节点 n 不可扩展，则转第(2)步；(6)扩展节点 n，生成其子节点 ni(i=1,2,)，计算每一个子节点的估价值 f(ni)(i=1,2,)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入 Open表中；(7)根据各节点的估价函数值，对 Open表中的全部节点按从小到大的顺序重新进行排序；(8)
43、转第(2)步。5.A*算法 A*算法是对A算法的评价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。第六章 神经网络 一概述 1.概念：人工神经网络（Artificial Neural Networks，简记作 ANN），是反映人脑结构及功能的一种抽象数学模型，是由大量神经元节点互连而成的复杂网络，用以模拟人类进行知识的表示与存储以及利用知识进行推理的行为。简单地讲，它是一个数学模型，可以用电子线路来实现，也可以用计算机程序来模拟，是人工智能研究的一种方法。2.人工神经网络力求从四个方面去模拟人脑的智能行为 物理结构 计算模拟 试人类智能活动的能力是人类在认识世界和改造
44、世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 存储与操作 训练 3.生物神经元
45、神经元结构包括四个部分：胞体：神经细胞的本体，维持细胞生存功能 树突：接收来自其他神经元的信号（输入）轴突：输出信号 突触：与另一个神经元相联系的特殊部位 4.一个神经元有两种状态：兴奋和抑制；5.生物神经网络的六个基本特征：1）神经元及其联接；2）神经元之间的联接强度决定信号传递的强弱；3）神经元之间的联接强度是可以随训练改变的；4）信号可以是起刺激作用的，也可以是起抑制作用的；5）一个神经元接受的信号的累积效果决定该神经元的状态；6)每个神经元可以有一个“阈值”6.MP 模型 是一种人工神经元的数学模型，它是由美国 Mc Culloch和 Pitts提出的最早神经元模型之一。MP模型是大多
46、数神经网络模型的基础。7.神经元的输出 y 是对 u 的映射：8.输出函数 线性函数 非线性斜面函数（Ramp Function）Sigmoid输出函数（S型函数）9.联接模式 层（级）内联接 循环联接 层（级）间联接 10.人工神经网络典型结构 试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就
47、无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和 人工神经网络连接的几种基本形式 前向网络(感知器)从输出到输入有反馈的前向网络 用来存储某种模式序列 层内互连前向网络 限制层内同时动作的神经元；分类功能 反馈型全互联网络&反馈型局部互联网络 11.神经网络学习 神经网络基本学习算法分为：有师学习（Supervised Learning）有师学习算法主要有 规则、BP算法、LVQ算法等 无师
48、学习（Unsupervised Learning）强化学习（Reinforcement Learning）12.神经网络的特点 大规模并行处理与容错能力 信息的分布式存储与处理 学习与自适应能力 具有联想与记忆能力 二人工神经网络 1.感知器 感知器是一种早期的神经网络模型，由美国学者 F.Rosenblatt 于 1958年提出。2.感知器模型 单输出的感知器(M-P模型)多输出的感知器 3.感知器的学习是有师学习 感知器的训练算法的基本原理来源于著名的 Hebb学习律（1949年提出）基本思想：逐步地将样本集中的样本输入到网络中，根据输出结果和理想输出之间的差别来调整网络中的权矩阵。4.H
49、ebb学习规则 Hebb学习规则调整 wij的原则为：若第 i 个神经元 ui和第 j 个神经元 uj同时处于兴奋状态，则它们之间的连接 wij应当加强 5.BP网络和 BP算法 BP：输入层、隐层、输出层 BP网络结构：多层感知器网络 输出函数：Sigmoid函数 6.反向传播算法（BP算法）的思想：从后向前反向逐层传播输出层的误差，以间接计算隐层的误差。算法可以分为两个阶段：前馈：从输入层经隐层逐层正向计算各单元的输出；学习：由输出误差逐层反向计算隐层各单元的误差，并用此误差修正前层的权值。试人类智能活动的能力是人类在认识世界和改造世界的活动中由脑力劳动表现出来的能力认识和理解世界环境的能
50、力提出概念建立方法进行演绎和归纳推理做出决策的能力学习取得经验积累知识的能力自我适应的能力联想推理判断维人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑从事的推理学习思考规划等思维活动关于知识的科学执行拟人的任务没有计算机的出现人工智能就无法得到应用人类智能与人工智能本质区别物质载体逻辑模是以知识库为基础那么计算智能则是以模型为基础以分步并行仿生计算为特征含数据算法和实现的信息系统前者强调规则的形式和表示后者强调计算智能的主要方法有人工神经网络遗传算法遗传程序演化程序局部搜索模型的建立和7.BP算法的优缺点 优点：理论基础牢固 推导过程严谨 物理概念清晰 通用性好 所以，它是目前