人工智能之问题规约策略

《人工智能之问题规约策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能原理(符号计算科学)PrinciplesofArtificialIntelligence第五章：问题规约策略Chapter05Problem-ReductionApproach§01PRA的基本思想Section01theEssentialsofPRA§01PRA的基本思想1.1PRA与状态空间法Three-S的局限性与状态空间法一样，问题规约方法也是人工智能的一种基于图搜索策略的问题求解方法。问题的表现形式是多样的，甚至是无限的，因此，问题状态的数量可能是巨大的，并非所有的问题都象八数码问题一样，只有9!种可能的状态。从某种意义上说，状态空间法求

2、解问题的过程是状态树生长的过程，是问题状态近乎几何级数地生长的过程，是被搜索的状态空间恶性膨胀的过程§01PRA的基本思想1.1PRA与状态空间法Three-S的局限性随着状态空间的膨胀，数量巨大的问题状态需要占用计算机大量的资源，包括存储空间和运行时间。特别的，对大的问题或复杂的问题，其状态空间中问题状态的数量之大，甚至可能令当代最大的计算机也难以承受。因此，状态空间法作为一种人工智能问题求解方法，仍然存在一定的局限性，特别是在求解大问题或复杂问题的能力上。§01PRA的基本思想1.2模拟人的复杂问题求解行为PRA面向复杂问题问题规约是人类处理或求解大问

3、题或复杂问题的一种常用的方式。人们常常将大的问题或复杂的问题分解为一系列小的或简单的问题，然后，分别加以处理或求解。一个大的问题常常是由一些小的问题构成的，一个复杂的问题常常是由一些简单问题构成的。这些小的问题或简单的问题就是大问题或复杂问题的子问题。§01PRA的基本思想1.2模拟人的复杂问题求解行为PRA的AI特征问题规约方法模拟人类处理大问题或复杂问题的智能行为，将大问题或复杂问题分解为较小或较简单的问题，将较小或较简单的问题再分解为更小或更简单的问题，直至所有的问题都易于处理或求解为止。最小的问题或具有明显解答的问题被称为本原问题。一般地，本原问题

4、是原始问题的子孙问题。因此，问题规约的过程就是在问题空间中不断搜索问题的子问题和子问题的子问题的过程，直至将原始问题分解为本原问题集合。§01PRA的基本思想1.3规约：化解复杂问题问题规约的基本思想是：将大问题或复杂问题分解为小的或简单的本原问题集合。问题规约方法和状态空间法具有共同的特征，这就是图搜索。问题规约的图搜索过程：在问题空间中，以待求解的原始问题为出发点，以本原问题为目标，不断地搜寻子问题的过程。§02PRA自学要点Section02TheFocusesonSelf-LearningPRA§02PRA自学要点(一)PRA问题的形式化定义：问题

5、规约方法中的问题被定义为一个四元组：其中：P,O,p(o),p(p)(5.1)(1)P={p}：问题空间(问题的集合)(2)O={O}：算子空间(操作的集合)(3)p(o)P：原始问题(OriginalProblem)(4)p(p)P：本原问题(PrimitiveProblem)应用O中的算子对p(o)进行操作，将原始问题p(o)转化为本原问题集合p(g)的过程称为问题(5.1)的求解。本原问题集合§02PRA自学要点(一)PRA问题的形式化关于本原问题：所谓本原问题，是指具有明显解答的问题，或有现成答案的问题，有现成解决方案的问

6、题。从计算机实现的角度来讲，在计算机数据库(或方法库或知识库)中已经给出了解答的问题，即可视为本原问题。例如，对于不定积分问题，dx就是一个本原问题，其答案是显而易见的，即：dx=x。§02PRA自学要点(一)PRA问题的形式化示例：不定积分问题：不定积分问题的求解过程，常常表现为问题规约的过程。一个不定积分问题的描述示例如下：(1)原始问题p(o)：(2)本原问题p(p)：dz(3)算子空间O：积分规则§02PRA问题的描述(一)PRA问题的形式化示例：不定积分问题：不定积分问题规约过程的与或搜索图§02PRA自学要点(二)PRA问题的三要素p(

7、o)和p(p)以及O(1)原始问题(OriginalProblem)：p(o)P(问题原态的描述)(2)本原问题(PrimitiveProblem)：p(p)P(问题终态的描述)(3)操作(又称算子，Operator)：O:SS或：p(j)=O(p(i))(p(i),p(j)P;OO)§03PRA自学要点(三)问题空间AND/OR图和树AND/OR图和树：描述问题空间，对应状态空间法中的状态图和状态树。AND/OR图和树搜索算法：(1)AND/OR图宽度优先搜索算法(2)AND/OR图宽深度优先搜索算法(3)AND/OR图AO*搜索算

8、法对比状态空间法和问题规约方法：(1)问题表示的方法(2)图搜索策