人工智能之问题规约策略.ppt

人工智能原理,(符号计算科学),Principles ofArtificial Intelligence,第五章：问题规约策略,Chapter 05Problem-ReductionApproach,01 PRA 的基本思想,Section 01the Essentialsof PRA,01 PRA 的基本思想,1.1 PRA与状态空间法 Three-S 的局限性,与状态空间法一样，问题规约方法也是人工智能的一种基于图搜索策略的问题求解方法。,问题的表现形式是多样的，甚至是无限的，因此，问题状态的数量可能是巨大的，并非所有的问题都象八数码问题一样，只有 9!种可能的状态。,从某种意义上说，状态空间法求解问题的过程是状态树生长的过程，是问题状态近乎几何级数地生长的过程，是被搜索的状态空间恶性膨胀的过程,01 PRA 的基本思想,1.1 PRA与状态空间法 Three-S 的局限性,随着状态空间的膨胀，数量巨大的问题状态需要占用计算机大量的资源，包括存储空间和运行时间。,特别的，对大的问题或复杂的问题，其状态空间中问题状态的数量之大，甚至可能令当代最大的计算机也难以承受。,因此，状态空间法作为一种人工智能问题求解方法，仍然存在一定的局限性，特别是在求解大问题或复杂问题的能力上。,01 PRA 的基本思想,1.2 模拟人的复杂问题求解行为 PRA 面向复杂问题,问题规约是人类处理或求解大问题或复杂问题的一种常用的方式。,人们常常将大的问题或复杂的问题分解为一系列小的或简单的问题，然后，分别加以处理或求解。,一个大的问题常常是由一些小的问题构成的，一个复杂的问题常常是由一些简单问题构成的。这些小的问题或简单的问题就是大问题或复杂问题的子问题。,01 PRA 的基本思想,1.2 模拟人的复杂问题求解行为 PRA 的 AI 特征,问题规约方法模拟人类处理大问题或复杂问题的智能行为，将大问题或复杂问题分解为较小或较简单的问题，将较小或较简单的问题再分解为更小或更简单的问题，直至所有的问题都易于处理或求解为止。,最小的问题或具有明显解答的问题被称为本原问题。,一般地，本原问题是原始问题的子孙问题。因此，问题规约的过程就是在问题空间中不断搜索问题的子问题和子问题的子问题的过程，直至将原始问题分解为本原问题集合。,01 PRA 的基本思想,1.3 规约：化解复杂问题,问题规约的基本思想是：将大问题或复杂问题分解为小的或简单的本原问题集合。,问题规约方法和状态空间法具有共同的特征，这就是图搜索。,问题规约的图搜索过程：在问题空间中，以待求解的原始问题为出发点，以本原问题为目标，不断地搜寻子问题的过程。,02 PRA 自学要点,Section 02The Focuseson Self-Learning PRA,02 PRA 自学要点,(一)PRA 问题的形式化 定义：,问题规约方法中的问题被定义为一个四元组：,其中：,P,O,p(o),p(p)(5.1),(1)P=p：问题空间(问题的集合)(2)O=O：算子空间(操作的集合)(3)p(o)P：原始问题(Original Problem)(4)p(p)P：本原问题(Primitive Problem),应用 O 中的算子对 p(o)进行操作，将原始问题 p(o)转化为本原问题集合 p(g)的过程称为问题(5.1)的求解。,本原问题集合,02 PRA 自学要点,(一)PRA 问题的形式化 关于本原问题：,所谓本原问题，是指具有明显解答的问题，或有现成答案的问题，有现成解决方案的问题。,从计算机实现的角度来讲，在计算机数据库(或方法库或知识库)中已经给出了解答的问题，即可视为本原问题。,例如，对于不定积分问题，dx 就是一个本原问题，其答案是显而易见的，即：dx=x。,02 PRA 自学要点,(一)PRA 问题的形式化 示例：不定积分问题：,不定积分问题的求解过程，常常表现为问题规约的过程。一个不定积分问题的描述示例如下：,(1)原始问题 p(o)：,(2)本原问题 p(p)：dz,(3)算子空间 O：积分规则,02 PRA 问题的描述,(一)PRA 问题的形式化 示例：不定积分问题：,不定积分问题规约过程的与或搜索图,02 PRA 自学要点,(二)PRA 问题的三要素 p(o)和 p(p)以及O,03 PRA 自学要点,(三)问题空间 AND/OR 图和树,AND/OR 图和树：描述问题空间，对应状态空间法中的状态图和状态树。,AND/OR 图和树搜索算法：(1)AND/OR 图宽度优先搜索算法(2)AND/OR 图宽深度优先搜索算法(3)AND/OR 图 AO*搜索算法,对比状态空间法和问题规约方法：(1)问题表示的方法(2)图搜索策略,