人工智能期末复习.doc

第二章状态空间法要完成某一个具体问题的状态描述，必须完成三项工作：如何描述状态，特别是初始状态 操作符集合及其对状态描述的作用 如何描述目标状态即定义好三元状态（S, F, G）中的三个成分 。状态空间法的问题：寻找从初始状态到目标状态的某一个操作符序列状态空间法的解：从初始状态变换到目标状态的操作符序列2.1.2 状态图示法 状态空间法（求解过程）的表示方法：用图来表示（借助于图论中某些技术）图是由节点（不一定是有限个的节点）的集合构成的注意：在图论中，图的定义中还包括边的集合当用有向图来表示状态空间法时，对应关系：Ø 图中的一个节点对应于某一个状态Ø 图中的一个有向弧对应于某一个算符注：有向弧的旁边可以标以具体算符在某些情况下，每个操作符作用、成本是不一样的，需要引入代价的概念（不相邻的）两个节点间路径的代价等于连接该路径的各个节点的所有弧线的代价之和 引入代价的概念后，我们的问题可能是：寻找初始节点到目标节点之间的代价最小的路径对应的原始问题：寻找从初始状态到目标状态的操作符代价之和最小的操作符序列利用图论的技术，我们要解决两个问题：第一、找出初始节点到目标节点的一条路径。对应于寻找初始状态到目标状态的操作符序列第二、找出初始节点到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列。问题归约法：从已知问题的描述出发，通过一系列变换或分解将问题最终变为一个子问题集合，这些子问题的解可以直接得到，从而解决初始问题 。问题归约法由三个部分组成：1.一个初始问题描述 2.一套将问题变换或分解为子问题的操作符 3.一套本原问题（解可以直接得到的简单问题）描述。2、问题归约的描述 问题归约法的基本思路是：应用一系列算符将原始问题的描述变换或分解成为子问题的描述。问题的描述可以采用各种数据结构，如表、树、矢量、数组等。问题归约法可以用一个三元组（S, O, P）来表示，其中：Ø S：原始问题，即要解决的问题Ø P：本原问题集，其中的每一个问题是不用证明的或自然成立的，例如公理、已知事实等Ø O：操作算子集，用于将问题化为子问题与或图的特例：Ø 所有节点都是或节点，这时就是一般的图，即状态空间法用到的图Ø 除了起始节点外，所有节点只有一个父节点，此时称为与或树，前面的图2.11就是与或树。 问题归约法、与或图表示之间的对应关系：问题归约法 与或图表示原始问题 起始节点本原问题 终叶节点操作符 与、或关系的弧线中间问题 非终叶节点一般情况下：分解 操作符得到 与节点。 变换 操作符得到 或节点。在与或图中，问题有解的条件是：起始节点是可解的。 在与或图中，一个可解节点的定义是（递归地）：1、终叶节点是可解的（因为它们与本原问题相关联的）。一般情况，终叶节点用 t 来表示2、如果某一个非终叶节点含有“或”后继节点，那么，只要有一个后继节点是可解的，这一个非终叶节点就是可解的。3、如果某一个非终叶节点含有“与”后继节点，那么，只要所有后继节点是可解的，这一个非终叶节点才是可解的。与或图中，一个不可解节点的定义（递归地）是：1、没有后裔的非终叶节点是不可解节点。2、如果某一个非终叶节点含有“或”后继节点，那么，只要当所有的后继节点都不可解时，这一个非终叶节点才是不可解的。3、如果某一个非终叶节点含有“与”后继节点，那么，只要有一个后继节点是不可解的，这一个非终叶节点就是不可解的。 与或图的解图：由最少的可解节点所构成的子图，这些节点能够使问题的起始节点是可解的谓词逻辑法逻辑 经典逻辑：命题逻辑、谓词逻辑 非经典逻辑：不确定性推理、非单调性推理命题逻辑核心思想：原子命题不可再分数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑。谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言。人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）。1、命题逻辑的基本概念命题 是能够判断真或假的陈述句。通常用大写字母来表示，如A, B, P, Q等命题的真假值一般用 T 或 F 来表示 命题逻辑 是研究命题及命题之间关系的符号逻辑系统。在命题逻辑中，表示单一意义的命题，称之为原子命题。原子命题通过 “联结词” 构成 复合命题。联接词的优先顺序：非 、合取 、析取 、蕴含Þ 、等价Û 。 注：可以用括号表示优先级命题变元：用符号P、Q等表示的不具有固定、具体含义的命题。它可以表示具有“真”、“假”含义的各种命题。 命题变元可以利用联结词构成所谓的合适公式。 对于合适公式，规定下列运算优先级： 逻辑联结词的运算优先次序为： 、 、Þ 、Û 同级联结词按出现顺序优先运算。 在命题逻辑中，主要研究推理的有效性。即：能否根据一些合适公式（前提）推导出新的合适公式（结论）。 谓词逻辑是命题逻辑的扩充和发展。它将一个原子命题分解成客体和谓词两个组成部分。例如： 雪 （客体） 是黑的 （谓词） 谓词是指个体（客体）所具有的性质或者若干个体之间的关系。用大写字母来表示。 个体是可以具体的（如: 小张、3、5）也可以是抽象的（如: x, y）。论域：由个体组成的集合。（个体）变量：定义在某一个论域上的变量。用x, y, z 来表示。函数（或函词）：以个体为变量，以个体为值的函数。一般用小写字母来表示，例如 f(x), f(x,a)。 如果谓词有 n 个变量，称之为 n 元谓词，并约定 0 元谓词就是命题（谓词的特例）。如果函数有 n 个个体，称之为 n 元函数，并约定 0 元函数就是常量。常量习惯上用小写字母来表示，如a, b, c。项的定义：常量是项 变量是项 如果 f 是n元函数，且t1 , tn(n1)是项，则 f (t1 , tn)也是项。所有的项都必须是有限次应用上述规则产生的。一阶谓词：只允许对变量施加量词，不允许对谓词和函数施加量词。2、合适公式的性质 如果 P 和 Q 是合适公式，则由这两个合适公式构成的合适公式的真值表与前面介绍的真值表相同。 如果两个合适公式的真值表相同，则我们称这两个合适公式是等价的，可以用“Û”来表示。 2.4.3 置换与合一 置换的定义：形如 t1 / v1 , , tn / vn 的集合，称为一个置换，其中 vi 是不同的变量，ti 是与 vi 不同的项。 例或例子的定义：设 t1/v1 , , tn/vn 为一个置换，E是一个原子谓词公式。则E表示将E中的 vi 同时用 ti（i=1,n）代入后所得到的结果，E称为E的一个例子。 置换的合成：设t1/x1, ,tn/xn和s1/y1, ,sm/ym是两个置换，则和的合成是如下置换： t1/x1 , ti/xi , tn/xn, s1/y1, , sm/ym 其中，若yj 是 x1,xn 之一者消去，对于任何 tj=xj 者消去，并记成。注意：置换的合成满足结合律，不满足交换律。 (s1s2)s3 = s1(s2s3) (满足结合律）。 s1s2 s2s1（不满足交换律）说明：1、合一算法是消解原理的基础。2、合一算法中的公式集就是从谓词合适公式化成的子句集。应用举例： （1）事实知识的描述例如假设用下列定义：P（x, a）表示某人x的职业为a；S（z, c）表示z的性别为c； R（t）表示t已退休。以下事实可以用谓词逻辑表示为：王的职业是教师：P（Wang, Teacher）。 王是男性：S（Wang，Male）张是女性：S（Zhang，Female）张工龄38年： W（Zhang，38）（2） 规则知识的描述 所有教师或工程师都具有高等教育学历，或者说：如果是教师或工程师那么都具有高等教育学历，可以描述为： 所有具有高等教育学历的人，年龄一般大于或等于25岁。 第3章 确定性推理 解决实际问题的两个关键之处：问题的表达：状态空间法，问题归约法，谓词逻辑法。问题的求解：搜索技术，推理技术。盲目与启发式搜索：状态空间法、图的搜索技术。与或树搜索：问题归约法、与或图的特例的搜索技术。博弈树搜索：状态空间法问题归约法、双人博弈的特殊搜索技术。消解原理：谓词逻辑法、推理技术。解的含义：在状态空间中，解是从初始状态到目标状态的操作符序列；在图中，解是从初始节点到目标节点的一条路径。注意：搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树，称之为搜索树 宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径（所用操作符最少）等代价搜索算法：例：最小路程问题。下图是五个城市的交通路线图，图中的数字是公里数。问题是找到一条从A到E的最短路线。操作符: 从一个城市走向另一个城市（方向大体上从A指向E）A(0)B(2)C(3)D(7)C(5)D(6)D(7)E(11)237344105CLOSEDE(13)三种盲目搜索技术的比较主要差别：在于挑选要扩展节点的规则不同宽度优先搜索技术：先扩展出来的节点随后先扩展，OPEN表是队列深度优先搜索技术：后扩展出来的节点随后先扩展，OPEN表是堆栈等代价搜索技术：选取OPEN表中代价最小的节点先扩展，OPEN表是线性表（以局部代价的递增顺序排列）2 估价函数的基本特性：一般情况下，估计函数值越大，希望程度就越低；根据搜索过程、问题的启发信息来定义的，对搜索效率会产生较大的影响。用 f (n) 表示节点 n 的估价函数值，并且期望，它是从起始节点、通过节点 n 、到达目标节点的最小代价的一个估计值。估价函数的计算：计算一个节点的“ 估价函数 ” ，可以分成两个部分：已经付出的代价（起始节点到当前节点）将要付出的代价（当前节点到目标节点）节点 n 的估价函数 f ( n ) 定义为从初始节点、经过 n 、到达目标节点的路径的最小代价的估计值，即 f ( n ) = g ( n ) + h ( n ) 。 g ( n ) 是从初始节点到达当前节点 n 的实际代价；h ( n ) 是从节点 n 到目标节点的最佳路径的估计代价h(n)起始节点起始节点起始节点g(n)f ( n ) = g ( n ) + h ( n )h ( n ) 体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数g ( n ) 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h ( n ) 的比重越大，表示启发性能就越强遗传算法遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一个数学仿真，属于进化计算中的一类方法。串码：表示染色体或者个体适应度函数：表示一个染色体的适应能力，其最大值或者最小值就是最优化问题的解一、遗传算法的基本机理： 1 编码与解码 2 适应度函数 3 遗传操作1 编码与解码在遗传算法中，为了模仿遗传学的遗传规律，必须对问题的解的结构进行编码，运行遗传算法后，再通过解码得到问题的解。编码与解码方法：二进制码方法 ；浮点数方法；符号方法；格雷码方法。2 适应度函数适应度函数：度量染色体优劣程度的函数，体现自然进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。1 遗传算法的特点通过编码使得解空间是有限的，所有遗传算法是一种基于空间搜索的求解技术，通过自然选择、交叉、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻找问题的解。特点：1.对参数集合的编码进行进化，不是参数本身进行进化2.从问题解的编码组（群体）开始，不是从单个解开始搜索3.只利用适应度函数（目标函数），不需要导数等信息4.只利用选择、交叉、变异等操作，不需要利用确定性规则进行随机操作遗传算法的基本思想：通过随机方式产生若干个个体，形成一个初始种群；利用适应度函数计算它们的适应度函数值，淘汰适应度小的个体，选择适应度高的个体参加遗传操作；经过遗传操作后的个体形成下一代种群，再对新的种群进行新的一轮进化。