人工智能复习材料

及其变换 1 同构同态变换 2 问题分解法 与图（树）描述问题分解。 或图（树）描述同构同态变换 。 2 问题的直接求解法状态空间求解法：1 用状态描述与问题相关的事实和事实间的关系 2 问题演绎法基本思想：分解原问题成 若干个子问题。3 博弈问题求解法 属于对策性课题，表示若干个体开展竞争的过程。 度量问题求解的性能问题求解算法的输出不是 Failure 就是解。 完备性： 当问题有解时， 这个算法能否保证找到一个解最优性： 算法是否能找到最优解？时间复杂度：找到一个解需要花费多长时间？空间复杂度：在执行算法的过程中需要多少内存？ 3 状态空间图搜索算法搜索（Search） ，即寻找，设法在庞大状态空间图中找到目标。也可以把搜索看作是一种推理，它是人工 智能问题求解的基本方法之一。主要分为两类性质的搜索：即基本搜索和智能搜索。基本搜索是一种没有任何经验和知识起作 用的、由某种规则所确定的非智能性的搜索；启发式搜索（Heuristic Search） ：其特点在于是一种有准备的、追求效率而有 的放矢的智能搜索，它要求依据某种知识及信息的指导，通过逐一状态比较而找到符合规定条件的目标状态解。 4 问题世界的全部信息空间划分为三类： （1）全信息环境 Ee；已知与问题的解有关的全部信息，其搜索的目标和任务是：运用 知识和经验，设法找到最佳路径，以便取得理想搜索效果。 （2）部分已知信息环境 Ep；当只有部分信息已知，这时其目标和任 务是：充分利用已知信息，把未知的信息不利影响设法降到最低程度，尽可能按照最佳搜索路径取得理想搜索效果。或者设法 弥补信息损失，发挥已知信息作用，扬长避短，制定策略来克敌制胜。 （3）未知信息环境 En 对于未知信息环境的问题求解， 首先要设法变 En 为部分已知信息环境 Ep 来解决。 5 状态空间表示法 1 状态：描述某一类事物在不同时刻所处于的信息状况。可用一组变量的有序组合来表示为如下形式： Sk=[ x0, x1, x2, x3, …]T 其中的每个元素 xi (i=0,1,2…)称为分量，相应的变量值域为[ai,bi]。给定每个分量的值，就 得到了一个具体的状态。状态的维数可以任意，一般为有限值。2 操作：描述了状态之间的关系。它可以是一个行为步骤，也 可以是一个改变过程、规则或操作数。使状态中的某些分量发生改变，就将使问题由一个具体状态变化到了另一个具体状态。 问题的状态空间可用一个三元序组来表示： 〈S，F，G〉S 是初始状态集；F 是操作的集合；而 G 为目标状态集。3 问题的求解就 转化为从状态空间图的初始状态 S0 出发，搜索寻取目标状态 Sg 的路径问题。搜索过程所得到的操作序列就反映了问题的解路 径。故搜索求解的过程可简洁地表示为：Sg=fn(…（f2(f1(S0))）…)式中，fi 表示对其右边的当前状态将进行第 i 个操作 6 搜索法求解问题的基本思想： 1 将初始状态当作当前状态。 2 选择适当的算符作用于当前状态得到后继状态。3 检查这组后 继状态中是否有目标状态。 7 问题的状态空间可用有向图来表达，又常称其为状态树 状态空间图在计算机中有两种存储方式：一种是图的显式存储，另一种是图的隐式存储。 图的显式存储:（1）概念：所谓图的显式存储，即把问题的全部状态空间图直接都存于计算机中的方式。诸如一般计算机文件、 程序文件和库文件的存储等，均为图的显式存储方式。 （2）适用条件：通常图的显式存储方式需要占据计算机的大量存储空间和处理时间，故这种存储方式仅适用于状态空间十分 有限以及较简单的问题求解。 （3）特点：其优点是直观、明了，但缺点是占据存储空间大。图的隐式存储:（1）概念：仅在计 算机中存储关于要求解问题的相关各种知识，只在必要时再由相关的信息和知识逐步生成状态空间图的方式称为图的隐式存 储。 （2）适用条件：适用于一般问题求解，尤其适宜于状态空间庞大的情况。 （3）特点：占据空间小，但不够直观，与图的显 式存储刚好特点互补。 8 隐式图的搜索过程:1.按照问题的已知条件，产生一个初始状态 S0 的有限描述，并依照一定的数据结构形式存于计算机中；2. 用发生器函数 Q(x)作用于 S0 并扩展生成 S0 的子节点 Si , 逐一比较目标节点 Sg 是否在 Si 中出现，若出现则搜索成功。3.若 没有出现 Sg， 就用估计函数 f(x)对所有这些刚生成的子节点 Si 进行价值评估， 在适当范围内选择最有希望的结点 Sk 替代 S0， 返回步 2 对 Sk 进行扩展生成。当所有可扩展的节点均已用 Q(x)生成，仍无 Sg 出现，则搜索失败。可逐层按照 f(x)选择子节 点并返回步 2、步 3 反复进行扩展生成，比较目标，价值评估等操作，直到找到目标节点 Sg 为止。 9 具体问题搜索求解可总结为如下的思路和步骤： （1）设定状态变量及确定值域； （2）确定状态组，分别列出初始状态集和目 标状态集； （3）定义并确定操作集； （4）估计全部状态空间数，并尽可能列出全部状态空间或予以描述之； （5）当状态数量 不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。 10 广度优先算法搜索原则：1 深度越小、越早生成结点的优先级越高。2 当最低层不止一个结点时，它选择最先生成的结点进 行搜索。 广度优先算法步骤：(1) 初始结点 S 加入到队列 OPEN 的尾部；(2) 若 OPEN 为空，则搜索失败，问题无解；(3) 取 出 OPEN 队头的结点 n，并放入 CLOSE 队列中；(4) 若 n 是目标结点 D，则搜索成功，问题有解；(5) 若 n 是叶结点，则转(2)； (6) 扩展 n 结点(即找出它的所有直接后继)，并把它的诸子结点依次加入 OPEN 队尾，修改这些子结点的返回指针，使其指向 结点 n。转(2)。 11 深度优先搜索搜索原则：1 深度越大、越晚产生结点的优先级越高。2 深度优先搜索是不完备的，属于非算法的搜索过程。 深度优先算法步骤：(1) 初始结点 S 放入堆栈 OPEN 中； (2) 若 OPEN 为空，则搜索失败，问题无解； (3) 弹出 OPEN 表中最 顶端结点放到 CLOSE 表中，并给出顺序编号 n； (4) 若 n 为目标结点 D，则搜索成功，问题有解； (5) 若 n 无子结点，转(2)； (6) 扩展 n 结点，将其所有子结点配上返回 n 的指针，并按次序压入 OPEN 堆栈，转(2) 。 12 有界深度优先搜索特点： 引入搜索深度限制值 d，使深度优先搜索过程具有完备性 。有界深度优先算法步骤：(1)初始结 点 S 放入堆栈 OPEN 中；(2)若 OPEN 为空，则搜索失败，问题无解；(3)弹出 OPEN 中栈顶结点 n，放入 CLOSE 表中，并给出顺序 编号 n；(4)若 n 为目标结点 D，则搜索成功，问题有解；(5)若 n 的深度 d(n)=d，则转(2) ；(6)若 n 无子结点，即不可扩展， 转(2) ；(7)扩展结点 n，将其所有子结点配上返回 n 的指针，并压入 OPEN 堆栈，转(2) 13 代价推进搜索特点：节点间有向边的代价不同 14 基本搜索的局限性及其特点为： ①基本搜索策略普遍适用于树状问题求解，控制性知识简单，容易编程在计算机上实现。 但是，它表现出来的缺点也很突出：一般必须知道问题的全部状态空间，搜索效果差，求解能力弱，故常被称为弱方法。 ② 它们都是依据某种固定规则运行的搜索，均属于非启发的强力搜索，没有表现出智能搜索的活跃性与灵活性。也就是说，问题 搜索树的生成、扩展以及节点接受考察的次序等，都是由生硬死板的搜索方法决定的，而不由具体问题状态信息引导与经验分 析来决定； ③由于基本搜索策略疏忽了对给定问题的特有知识的分析,没有充分考虑所要求解问题的自身发展规律和特性，搜 索完全是按事先确定好的固定排序来进行的，这是一种穷尽遍历的大海捞针式的策略，没有任何启发式信息引导，往往使得实 际搜索效率很低，故又被称为盲目搜索。 15 启发式搜索策略利用与问题解有关的启发信息来作引导的搜索策略。 特点是： 由于充分考虑到问题求解所应用到的各种启发 信息及知识，包括利用常识性推理和专家经验等信息与知识，启发式搜索能够动态地确定操作排序，优先调用较合适的操作规 则，扩展、比较并选择最有希望的节点，使搜索尽可能以最快的速度，最短的距离，最小的代价，朝着最有利于达到目标节点 的方向推进。即以智能思想调节搜索区，使尽量沿着最有希望找到解的路径方向上，纵向小范围地搜索前进。 采用启发式搜索策略： （1）使用了控制性知识中的启发信息，因而弥补了略去的部分状态空间所带来的有用信息丢失； （2） 启 发式搜索往往是深度优先搜索法的改进。只需知道问题的部分状态空间，就可以求解智能问题。 （3）与基本搜索相比，启发式 搜索最大特点就是搜索效率要高得多。搜索效率及其评价：P=L/T L 是从根节点到达目标节点的深度；T 是在整个搜索过程中 产生节点总数(不计根节点)，因此，这里 P 反映的是朝着目标搜索时的搜索宽度。 16 估价函数，是指从问题树根节点到达目标节点的搜索中，所要耗费全部代价的一种估计值，记为 f (n)。f(n)=g(n)+h(n) ① f (n)：表示从根节点 So 出发，经过当前节点 Sn，到达目标节点 Sg 已耗费及将要耗费代价总和的估计值。 ② g (n)：表示从根节点 So，在到达目标节点 Sg 的搜索路径上，已到达当前节点 Sn，g (n) 即表示从 So→Sn 已耗费的代价。 ③ h (n)：指从当前节点 Sn， ，预测估计到达目标节点 Sg，将要耗费的可能代价。也就是说，h（n）表示了 Sn→Sg 这一路径搜 索段上将要耗费代价的可能值。称之为启发函数。
一、绪 1.21 世纪最具有发展前景和最具影响力的两大带头学科群：生命科学群与群体科学群 2.人工智能流派（符号智能——物理符号系统假设和有限合理性原理为基础，认为认知是一种符号处理的过程，人类思维过程 也可用某种符号来描述，思维就是计算，认知就是计算；计算智能—— 认为人类认知活动主要基于大脑神经元的活动。 核心： 人工神经网络、进化计算；群体智能——智能可通过群体协同模拟，如多智能体系统，蚁群算法和生态平衡； ） 3.Minsky 总结了 AI 的两类任务：理论研究与技术研究； 4.Turing 测试（人与计算机分处在不同房间中; 相互对话;真实人不能判断对话方是人还是计算机;计算机就具有智能。) 二、 概述 1.人工智能主要研究用人工的方法和技术，模仿、延伸和扩展人的智能,实现机器智能。人工智能的长期目标是实现人类水平的 人工智能。人工智能尚缺乏必要的理论。在一些关键技术方面, 诸如机器学习、非单调推理、常识性知识表示、不确定推理等 尚未取得突破性的进展。人工智能对全局性判断模糊信息处理、多粒度视觉信息的处理是极为困难的。人工智能还处于智能学 科研究的早期阶段, 必须开展智能科学的研究。 智能科学研究智能的基本理论和实现技术，是由脑科学、认知科学、人工智能 等学科构成的交叉学科。 2.认知是和情感、动机、意志等相对的理智或认识过程。认知科学是研究人类感知和思维信息处理过程的科学, 包括从感觉的 输入到复杂问题求解, 从人类个体到人类社会的智能活动, 以及人类智能和机器智能的性质。 3.人工智能的五个基本问题(1) 知识与概念化是否是人工智能的核心(2) 认知能力能否与载体分开来研究（3) 认知的轨迹是否 可用类自然语言来描述(4) 学习能力能否与认知分开来研究？ (5) 所有的认知是否有一种统一的结构 4.思维是客观现实的反映过程，是具有意识的人脑对于客观现实的本质属性、内部规律性的自觉的、间接的和概括的反映。 5.智能是个体认识客观事物和运用知识解决问题的能力。 符号智能：以知识为基础，通过推理进行问题求解。也即所谓的传统人工智能。 计算智能：以数据为基础，通过训练建立联系，进行问题求解。人工神经网络、遗传算法、模糊系统、进化程序设计、人工生 命等都可以包括在计算智能。 6.人工智能的研究方法：①逻辑学派以 Simon, Minsky 和 Newell 等为代表，从人的思维活动出发，利用计算机进行宏观功能模 拟。 ②认知学派逻辑学派是以 McCarthy 和 Nilsson 等为代表， 主张用逻辑来研究人工智能， 即用形式化的方法描述客观世界 ③ 行为学派 Brooks 认为人工智能的研究应走出这种抽象过份简单的现实世界模型的象牙塔，而以复杂的现实世界为背景，让人 工智能理论、技术先经受解决实际问题的考验，并在这种考验中成长。提出了无需知识表示的智能、无需推理的智能。 7.推理：从一个或几个已知的判断(前提)逻辑地推论出一个新的判断(结论)的思维形式。 非单调推理：指的是一个正确 的公理加到理论中, 反而会使预先所得到的一些结论变得无效了。非单调推理过程：建立假设, 进行标准逻辑意义下的推理, 若发现不一致, 进行回溯, 以便消除不一致, 再建立新的假设。定性推理：把物理系统或物理过程细分为子系统或子过程, 对 于每个子系统或子过程以及它们之间的相互作用或影响都建立起结构描述, 通过局部因果性的传播和行为合成获得实际物理系 统的行为描述和功能描述。 8.学习的基本机制是设法把在一种情况下是成功的表现行为转移到另一类似的新情况中去。学习是获取知识、积累经验、改进 性能、发现规律、适应环境的过程。知识、知识表示及运用知识的推理算法是人工智能的核心, 而机器学习则是关键问题。 9.机器学习的研究四个阶段： 无知识的学习： 主要研究神经元模型和基于决策论方法的自适应和自组织系统。 符号概念获取：给定某一类别的若干正例和反例，从中获得该类别的一般定义。 实例学习：从实例学习结构描述。 有知识的学习：把大量知识引入学习系统做为背景知识 机器学习的风范： 归纳学习：研究一般性概念的描述和概念聚类；分析学习：在领域知识指导下进行实例学习, 包括基于解释的学习、 知 识块学习等。 发现学习：根据实验数据或模型重新发现新的定律的方法。④遗传学习：模拟生物繁衍的变异和自然选择， 把概念的各种变体当作物种的个体, 根据客观功能测试概念的诱发变化和重组合并, 决定哪种情况应在基因组合中予以保 留。⑤连接学习是神经网络通过典型实例的训练, 识别输入模式的不同类别。 10.分布式人工智能：研究在逻辑上或物理上分散的智能动作者如何协调其智能行为，即协调它们的知识、技能和规划, 求解单 目标或多目标问题，为设计和建立大型复杂的智能系统或计算机支持协同工作提供有效途径。 11.知识系统包括：专家系统、知识库系统、智能决策系统等。 专家系统：专家系统是一种模拟人类专家解决领域问题的计算机程序系统。 这类计算机程序包括两部分: 知识库, 它表示和 存储由任务所指定领域知识的一组数据结构集合，包含有关领域的事实和专家水平的启发式知识。推理机, 它是构造推理路径 的一组推理方法集合, 以便导致问题求解、假设的形成、目标的满足等。由于推理采用的机理、概念不同，推理机形成多种范 型的格局。知识库系统：把知识以一定的结构存入计算机, 进行知识的管理和问题求解, 实现知识的共享。决策支持系统是 计算机科学（包括人工智能） 、行为科学和系统科学相结合的产物，是以支持半结构化和非结构化决策过程为特征的一类计算 机辅助决策系统，用于支持高级管理人员进行战略规划和宏观决策。其组成 ：数据库管理子系统、模型库管理子系统、方法 库管理子系统、知识库管理子系统、会话子系统。