人工智能与机器翻译3-4章（产生式及搜索方法、机器翻译方法）3

1、 人工智能与机器翻译产生式系统及其搜索方法第3 章 产生式系统及其搜索方法3.1 产生式系统3.2 产生式系统的搜索(控制)策略3.3 图搜索算法3.4 产生式系统的规则问题3.5 应用举例3.6 产生式系统的不确定性问题3.7 系统设计技巧3 . 1 产生式系统 产生式系统使用类似于文法的规则, 对符号串作替换运算。 它是智能软件中使用最普遍、最典型的一种结构。为什么要采用产生式系统作为智能软件的主要结构呢? 这可以有两点理由: (1) 用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象, 因而可以用它来模拟人类求解问题时的思维过程; (2) 可以把产生式系统作为智能软件中的基本

2、结构单元或基本模式看待, 就好象是 积木世界中的积木块一样, 因而研究产生式系统的基本问题就具有一般意义。3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分一个智能软件用产生式系统设计的基本组成是: 一个综合数据库; 一组产生式规则; 一个控制系统。综合数据库是产生式系统所使用的主要数据结构, 用来表述问题的状态或有关事实。 它包含求解问题的信息 , 其中有些部分可以是不变的, 有些部分可能只与当前问题的解有关。人们可以根据问题的性质, 用适当的方法来构造综合数据库的信息。3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分产生式规则的一般形式为: 条件行动 或 前提

3、结论 即表示成为: ifthen 的形式。其中, 左边确定了该规则可应用的先决条件; 右边描述了应用这条规则所采取的行动或得出的结论。一条产生式规则满足了应用的先决条件之后, 就可对综合数据库进行操作, 使其发生变化。如综合数据库代表当前状态, 则应用规则后就使状态发生转换, 生成新状态。3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 控制系统是软件的控制程序, 也是规则的解释(推理)程序。 它规定了如何选择一条 可应用的规则对数据库进行操作, 即确定了求解过程的推理路线。 当数据库满足结束条件时, 系统就应停止运行; 还要使系统在求解过程中记住应用过的规则序列, 以便最终能

4、给出解的路径。 控制系统也称控制策略, 它也可以是从规则集中选择规则并作用于状态的一种广义选取函数。确定某一种策略后, 可以算法的形式给出。在建立产生式系统描述时, 还要给出初始状态和目标条件, 具体说明所求解的问题。 产生式系统中控制策略的作用就是从初始状态出发, 寻求一个满足一定条件的问题状态。 目标条件也是产生式系统结束条件的基础。3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 上述产生式系统的定义具有一般性, 它可用来模拟任一可计算过程。 在研究人类进行问题求解过程时, 完全可用一个产生式系统来模拟求解过程, 及可作为描述搜索的一种有效方法。作为智能中的一种形式体系,

5、 它还具有以下优点: (1) 适合于模拟强数据驱动特点的智能行为。当一些新的数据数入时, 系统的行为就要改变; (2) 易于添加新规则去适应新的情况, 而不破坏系统的其他部分。 这是由于产生式系统的各组成部分具有相对的独立性, 因而便于扩展和修改。3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 用产生式系统来求解问题, 首先必须建立起问题的产生式系统描述, 即规定出数据库、规则集合及其控制策略。这种把一个问题的叙述转化为产生式系统的三个组成部分, 在智能技术中通常称为问题的表示。一般来说一个问题可有多种表示方式, 而选择一种较好的表示是运用智能技术解决实际问题首先要考虑的,

6、而且要有一定的技巧。 建立了产生式系统描述之后, 通过控制策略, 可求得实现目标的一个规则序列, 这就是所谓问题的解, 这个解序列是根据控制系统记住搜索目标过程中用过的所有规则而构造出来的。3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 在一般情况下, 问题可能有多个解的序列, 但有时会要求得到有某些附加约束条件的解, 例如要求步数最少、距离最短等。 这些约束条件通常是用耗散或代价这一概念来概括, 这时问题可称为寻找具有最小耗散的解。 在用产生式系统求解问题时, 有时引入状态空间图。状态空间图是一个有向图, 其节点可表示问题的各种状态(综合数据库), 节点之间的弧线代表一些操

7、作(产生式规则), 它们可把一种状态导向另一种状态。这样建立起来的状态空间图, 描述了问题所有可能出现的状态及状态和操作之间的关系, 因而可以较直观地看出问题的解路径及其性质。当然, 只有问题空间规模较小才可能作出状态空间图。3 . 1 产生式系统 3 . 1 . 1 产生式系统的组成部分 建立产生式系统描述的过程, 就是所谓问题的表示。对问题表示的好坏, 往往对求 解过程的效率有很大的影响。一种较好的表示法会简化状态空间和规则集表示, 此外, 高 效率的问题求解过程与控制策略有关, 合适的控制策略可缩小状态空间的搜索范围, 提高求解的效率。 从以上论述可知, 用产生式系统来描述和求解问题,

8、就是在问题空间中搜索一条从初始状态到达某一个目标状态的路径。这完全可以模拟人的求解过程, 也就是可以把产生式系统作为求解问题思考过程的一种模拟。3 . 1 产生式系统 3 . 1 . 2 产生式系统的基本算法E1: DATA初始事实库E2: until DATA 满足结束条件以前, doE3: beginE4: 在规则集中,选某一条可用于DATA的规则E5: DATA规则应用到DATA得到的结果E6: 结束3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型正向、逆向、双向产生式系统 用产生式系统求解某一问题时, 如果按照规则使用的方式或者说按推理方向来划分的话, 有正向、逆向和双向产

9、生式系统。 正向产生式系统是从初始状态出发朝着目标状态这个方向使用规则, 即正推的方式工作, 称这些规则为F规则; 若选目标状态作为初始 数据库逆向进行求解, 即逆向使用规则, 产生子目标状态, 反方向一步一步朝着初始状态方向求解, 整个逆推方式工作, 称逆向产生式系统, 逆向应用的规则称B规则; 若以双向搜索的方式(即正向和逆向同时进行)去求解问题, 则称为双向产生式系统。3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型可交换的产生式系统 可交换式产生式系统的可交换性指几条规则的应用可以任意交换次序而不影响求解。 一般来说, 当一个产生式系统对任何一个数据库D都具有如下性质时,

10、这样一个产生式系 统是可交换的。 (1) 可应用于D的规则集合, 使用了其中任意一条规则之后所生成的任何数据库, 这样一个规则集合还适用; (2) 满足目标条件的某个数据库D, 当应用任何一个可应用于数据库D 的规则之后所 生成的任何数据库, 任然满足目标条件; (3) 若对D应用某一规则序列后得到的一个数据库D(并能达到解), 当改变这些规则次序后, 任然可求得解, 即求得D与使用满足D的可应用规则集合中的规则次序无关。3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型可交换的产生式系统 例: 给定一个整数集合的初始状态a, b, c, 设目标状态为具有a, b, c, ab, b

11、c, ca这六个元素组成的集合。可应用的规则集合为 R1: if a, b, c then a, b, c, ab R2: if a, b, c then a, b, c, bc R3: if a, b, c then a, b, c, ca 显然, 这个产生式实例具有可交换性。 一个产生式系统具有可交换性 , 求解时只需搜索其中任一条途径 , 只要解存在就一 定能找到目标, 不必探索多条途径, 因此不可撤回的控制方式(下节论述) 在这种系统中使用很合适, 因解与最初可应用的规则系列的次序无关, 系统不必提供特殊选择规则的机理。3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型可分解

12、的产生式系统 先研究一个重写问题的产生式系统, 初始数据库为(C, B, Z), 产生式规则如下: R1: C(D, L) R2: C(B, M) R3: B(M, M) R4: Z(B, B, M) 结束条件是生成只包含M组成的数据库, 即(M, , M)。3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型可分解的产生式系统用图搜索方式求解这个问题时, 搜索得到的部分状态空间图见图26。 图中只给出两条达到目标的路径和一条失败的路径。实际搜索时有可能去探索更多的路径, 往往导致效率降低。 对于个问题, 为了避免搜索多余的路径 , 可以将初始数据库分解成几个可以独立加以处理的分量,

13、分别对它们进行求解。 即可以分别对每一个分量数据库, 测试产生式规则可以应用的条件, 如此进行下去, 直到分量数据库满足某种结束条件为止。 要注意一般结 束条件应是所有分量数据库都已满足结束条件。3 . 1 产生式系统 3 . 1 . 3 产生式系统的类型可分解的产生式系统 能够分解产生式系统的综合数据库和结束条件的产生式系统称为可分解的产生式系统。一个可分解的产生式系统, 其基本算法描述如下: (1) DATA:=初始数据库 (2) Di:=DATA的分解式; 每个Di元素都看成单独的数据库 (3) Until Di的所有元素都满足结束条件之前, do: (4) begin (5) 从Di中

14、选一个不满足结束条件的D* (6) 从Di中删去D* (7) 在规则集中选择一条可应用于D*的规则R (8) di:=R应用于D*的结果 (9) 在Di上添加di (10) end下图为分解方式 (C,B,Z)初态 R2 R4 R1 (B,M,B,Z) (C,B,B,B,M) (D,L,B,Z) R3 R2 R3 (M,M,M,B,Z) (B,M,B,B,B,M) (D,L,M,M,Z) R3 R3 R4 (M,M,M,M,M,Z) (M,M,M,B,B,B,M) (D,L,M,M,B,B,M) R4R3 R3 (M,M,M,M,M,B,B,M) (D,L,M,M,M,B,M) R3 R3 (

15、M,M,M,M,M,M,M,B,M) (D,L,M,M,M,M,M,M,M) R3目标 (M,M,M,M,M,M,M,M,M,M) 图 263 . 2 产生式系统的搜索(控制)策略 在3 .1 . 2节的算法中, 如何选择一条可应用的规则, 作用于当前的综合数据库, 生成新 的状态以及记住选用的规则序列是构成控制策略的主要内容。对大多数的智能应用问题, 所拥有的控制策略知识或信息并不足以使每次通过算法E4时, 一下子就能选出最合适的 一条规则来, 因而产生式系统还必须把E4扩大成搜索(推理)算法, 以至于基本算法的每 一循环中选一条规则试用, 最终找出某一序列能产生一个满足结束条件的数据库为止

16、。由此可见, 高效率的控制策略需要有关被求解问题的足够知识, 这样才能在搜索过程 减少盲目性, 比较快的找到解路径。 过去三十多年中, 人们研究了许多种搜索算法,归纳起来主要有两类: 一类是非启发 式算法; 另一类是启发式算法。 非启发式算法是按预定的控制策略进行搜索, 在其过程中获得的中间信息不用来改进控制策略。 由于搜索总是按预先规定的路线进行, 没有考虑问题本身的特性, 所以不容易选择到最优的搜索途径, 效率较低 , 且出现组合爆炸的频率高。 启发式算法是在搜索中加入了与问题有关的启发性信息, 用以指导搜索朝着最有希望的方向前进, 加速问题的求解过程并找到最优解。 3.2 产生式系统的搜

17、索(控制)策略3.2 产生式系统的搜索(控制)策略 3 . 2 . 1 产生式系统控制策略分类可分解的产生式系统 控制策略可划分为两大类: 不可撤回方法 回溯方法 试探性方法 图搜索方法3.2 产生式系统的搜索(控制)策略 3 . 2 . 2 不可撤回方法 这种方法相当于沿着单独一条路搜索下去, 利用问题给出的局部知识决定如何选取规则, 就是说根据当前可靠的局部知识选一条可应用规则并作用于当前综合数据库。 接着再根据新状态继续选取规则, 搜索过程一直进行, 不必考虑撤回用过的规则。 这是由于在搜索过程中如能有效利用局部知识, 即使使用了一条不理想的规则, 也不妨碍下一步选得另一条更合适的规则。

18、这样不撤消用过的规则, 并不影响求到解, 只是解序列中可能多了一些不必要的规则。显然这种策略具有控制简单的优点。3.2 产生式系统的搜索(控制)策略 3 . 2 . 2 不可撤回方法 爬山法不仅适用于爬山问题, 那些目标为极大值, 搜索过程是不断接近目标的单值问题都可应用这一方法。使用不可撤回策略, 虽然不可能对任何状态总能选得最优的规则, 但是如果应用了一条不合适的规则之后, 不去撤消它并不排除下一步应用一条合适的规则, 那么只是解序列有些多余的规则而已, 求得的解不是最优解, 但控制较简单。此外还应当指出, 一般很难对给定问题构造出任何情况下都能通用的爬山函数, 因而不 可撤回的方法具有一

19、定的局限性。3.2 产生式系统的搜索(控制)策略 3.2.3 回溯方法 在问题求解过程中, 有时会发现应用一条不合适的规则会阻扰或拖延达到目标的过程。在这种情况下, 需要有这样的控制策略: 先试一试某一条规则, 如果以后发现这条规则不合适, 则允许退回去, 另选一条规则来试。回溯方法不保留完整的搜索树结构, 只记住当前工作的一条路径, 回溯就是对这条路径进行修正。 使用回溯策略首要的问题要研究在什么情况下应该回溯, 即要确定回溯条件的问题。其次就是如何利用有用知识进行规则排序, 以减少回溯次数。 回溯应发生在以下三种情况: (1) 新生成的状态在通向初始状态的路径上已出现过; (2) 从初始状

20、态开始, 应用的规则数目达到所规定的数目之后还未找到目标状态(这一组规则的数目实际上就是搜索深度范围所规定的); (3) 对当前状态, 再没有可应用的规则。3.2 产生式系统的搜索(控制)策略 3.2.3 回溯方法 搜索深度的设置是一个值得注意的问题, 设置太浅, 有可能找不到解; 设置太深, 有可能导致回溯次数巨增。因而应根据实际情况来规定搜索范围, 先设置适中的深度搜索, 失败时再逐步加深。 回溯过程是一种可试探的方法, 从形式上无论是否存在对选择规则有用的知识, 都可以采用这种策略。即如果没有有用的知识来引导规则选取, 那么规则可按任意方式(固定排序或随机)选取; 如果有好的选择规则的知

21、识可用, 那么用这种知识来引导规则选取, 就会减少盲目性, 降低回溯次数, 甚至不回溯就能找到解, 总之一般来说有利于提高效率。此外由于引入回溯机理, 可以避免陷入局部极大值的情况, 继续寻找其他达到目标的路径。3.2 产生式系统的搜索(控制)策略 3.2.3 回溯方法可用递归算法描述回溯策略: YX0: 选择一条新路径搜索; YX1: 搜索已超出规定指标(无新路径、超时, 超深度等), 失败退出;否则搜索继续; YX2: 搜索的状态找不到可用规则, 回溯到YX0; YX3: 搜索的状态依某种原则(任意排列或按启发式准则)取有用规则; YX4: 若规则用完未找到目标, 回溯YX0; YX5:

22、取头条可用规则Ri; YX6: 删去头条规则, 减少搜索中规则集长度(注意, 这不动原始规则集); YX7: 规则Ri作用于当前状态, 生成新状态; YX8: 若找到目标, 成功退出; 若生成的新状态已出现过, 回溯到YX0; YX9: 记录新状态, 对新状态递规调用YX1YX7; 产生式系统求解问题时, 如果控制系统保留所有规则应用后生成并链接起来的状态记录图, 则称工作在这种方式下的控制系统使用了图搜索策略。 实际上图搜索策略是实现从一个隐含图中, 生成一部分确实含有一个目标节点的显式表示的子图搜索过程。3 . 3 图搜索算法3 . 3 图搜索算法 3. 3 . 1 一般性图搜索算法 步骤

23、1 GS,OPEN(S); 建立一个搜索图G,它只含有初始节点S, 建立一个OPEN表 (今后它用于存储生成的节点), 开始它只含有初始节点S。 步骤2 CLOSED( ); 建立一个CLOSED表(今后它用于存储已扩展节点或将要扩展的某个节点), 它的初始状态为空表。 步骤3 LOOP: if OPEN=( ) then return FAIL; 进入循环。 如果OPEN表已空, 说明没有节点可扩展, 就返回FAIL, 即失败。 步骤4 nFIRST(OPEN), CLOSED(n, CLOSED); 从OPEN表中取出一个节点n, 将其 放入CLOSED表中。3 . 3 图搜索算法 3.3

24、.2 典型的非启发式图搜索算法分析与改进广度优先搜索法 该方法从初始节点开始, 序扩展生成下一级各子节点, OPEN 表中已有的节点后 面(实现先生成的子节点先扩展), 然后从OPEN 表中提取最前的一个节点检查是否是目标节点, 否则再扩展, 再重复上述操作。 这种方法认为同一级各节点对问题求解的价值是同等的, 因而对全部节点沿广度进行横向扫描, 按各节点生成的先后次序,先生成、先检查、先扩展, 沿广度遍历所有节点。 这种方法只要问题有解, 即若树图上存在目标节点, 经搜索一定能找到。 所以, 广度优先搜索法是完备的, 是一种推理算法。 但是, 在问题大节点多, 且目标节点距离初始节点较远时将

25、会产生许多无用节点, 搜索效率低, 还可能产生组合爆炸。 因此, 这种方法较适宜问题不大的环境中3 . 3 图搜索算法 3.3.2 典型的非启发式图搜索算法分析与改进深度优先搜索法 该方法从初始节点开始, 顺序扩展生成下一级各子节点,放在OPEN表中已有的节点前面(实现后生成的子节点先扩展), 然后从OPEN 表中提取最前的一个节点检查是否是目标节点, 否则再扩展, 再重复上述操作。 这种方法每一次扩展最晚生成的子节点, 沿着最晚生成的子节点分支, 逐级纵向深入发展。 这种方法搜索一旦进入某个分支, 就将沿着该分支一直向下搜索。 如果目标节点恰 好在此分支上 , 则可较快地得到解。 但是, 如

26、果目标节点不在此分支上 , 不回溯就不可能得到解。 所以, 深度优先搜索是不完备的, 只是推理步骤。 如果回溯, 不难证明其平 均效率与广度优先搜索法相同。 因此, 深度优先搜索法如果没有启发信息 , 很难有实用价值。3 . 3 图搜索算法 3.3.2 典型的非启发式图搜索算法分析与改进代价驱动搜索法 该方法考虑了从一个节点经过一条支路, 转移到另一个节点时所需要支付的代价, 如费用、时间等。 该方法从初始节点开始, 扩展生成下一级各子节点, 这些子节点中若没有目标节点需再扩展搜索。 把它们放进OPEN表中, 依据初始节点到它们各自所付出的代价 大小进行排序, 代价小的节点放在前面扩展, 周而

27、复始重复上述操作, 直至找到目标节点为止。 这种方法根据各条支路所需支付的代价有差别, 所以具有同样路径长度( 所经过的支路数 )的搜索过程, 其搜索代价(所支付的总代价)可能不同, 优选最小代价的搜索路径, 进行推理求解问题。 代价驱动搜索无论在理论研究方面还是实际应用方面都很有前景, 例如最短路径问题。进一步的研究认为最短路径问题的改进应为以下几点:3 . 3 图搜索算法 3.3.2 典型的非启发式图搜索算法分析与改进代价驱动搜索法1) OPEN表的节点排序问题, 特别是在问题节点多达成千上万时尤为重要.这一排序应采用映射排序， 它是一个基于地址计算的排序, 在预置路径最大代价dmax后,

28、 开辟一个数组P(dmax), 就可把节点送入其值与P数组下标相等的对应元素中, 显然di=50它对应P(50); dj=500, 对应P(500)。 相同代价值的节点落在同一数组元素中, 用计数方式 可知有几个。 由于数组元素是有序的, 50050, 数组元素的下标自然把节点一次定好了位置, 排序即完成。 这一排序的时间复杂性为O(N), 对于OPEN表面临的无数次排序操作, 极大的提高了效率.2) 搜索过程中, 如果到达某一节点的代价任一初始节点到目标节点的路径代价, 这一节点的路径删去。3) 搜索过程中, 如果同时出现了两条到达某一节点的路径 ,代价大的那条路径即时删去。3 . 3 图搜

29、索算法 3 . 3 . 3 典型的启发式搜索算法分析与改进 搜索过程中, 如果在确定扩展那一个节点时能充分利用与问题求解有关的特性信息, 就可以估计出节点的重要性 , 就能使搜索选择重要性较高的节点 , 以利于求得最优解。 象这样 就可用于指导搜索过程, 且与具体问题求解有关的控制性信息称为启发性信息。 启发性信息可以用于估价节点重要性, 表示为函数形式: f(x)=g(x)+h(x) 其中, g(x)为初始节点S。到节点x已经付出的代价; h(x)是从节点x到目标节点Sg的最优 路径的估计代价, 它体现了问题的启发性信息, 其形式根据问题的特性确定。3 . 3 图搜索算法 3 . 3 . 3

30、 典型的启发式搜索算法分析与改进 A*算法如果对一般性图搜索算法作以下限制, 则它成为A*算法: (1) OPEN表中的节点按估价函数 f(x)=g(x)+h(x) 的值从小至大进行排序. (2) g(x)是到目前为止, 从S。到x的一条最小耗散值路径的耗散值, 是作为从S。到 x 最小耗散值路径的耗散值g*(x)的估计值, g(x)0。 (3) h(x)是h*(x)的下界, 即对所有x均有h(x)h*(x)。 而h*(x)是从节点x到目标节点的最小代价 , 若有多个目标节点, 则为其中最小的一个。3 . 3 图搜索算法 3 . 3 . 3 典型的启发式搜索算法分析与改进 A*算法几个重要性质

31、: 性质1 对于有限图, A*算法一定会在有限步内终止. 证明： 对于有限图, 其节点个数是有限的, A* 算法在经过若干次循环后会出现两种情况: 或者搜索到目标节点在步骤5结束; 或者OPEN表中的节点被取完在步骤3结束。 不 管那种情况, A*算法都在有限步内终止。3 . 3 图搜索算法 3 . 3 . 3 典型的启发式搜索算法分析与改进 A*算法几个重要性质:性质2 对于无限图, 只要从初始节点到目标节点有路径存在, A*算法也必然终止。证明: 分两步. 第一步证明A*算法结束前, OPEN表中存在节点x, 它是最优路径上 的一个节点 , 且满足 f(x)f*(s).。 设最优路径是 S

32、。x1, x2, , S*g 由于 A*算法中的h(x)满足 h(x)h*(x) 所以 f(s0), f(x1), f(x2), , f(xm)均不大于f(sg*)=f*(s0). 又因为A*算法是广度代价择优, 所以在它结束之前, OPEN表中一定含有S。x1,x2, S*g中的一些节点, 设x是其中最前面的一个, 则它必然满足 f(x)f*(S0) 至此, 第一步证明结束;3 . 3 图搜索算法 3 . 3 . 3 典型的启发式搜索算法分析与改进 A*算法几个重要性质:性质2 对于无限图, 只要从初始节点到目标节点有路径存在, A*算法也必然终止。第二步证明：用反证法, 假设A*算法不终止

33、, 并设e是图中各条边的最小代价, d*(xn )是从S。到节点xn的最短路径长度, 则显然有 g*(xn)d*(xn)e 又因为 g(xn)g*(xn) 所以有 g(xn)d*(xn)e 再因 h(xn)0, f(xn)g(xn) 故得到 f(xn)d*(xn)e 由于A*算法不终止, 随着搜索的进行, d*(xn)会无限增大, 从而使f(xn)也无限增大。 这与第一步证明得出的结论矛盾, 因对可解状态空间来说, f*(s0)一定是有限值。 所以, 只要从初始节点到目标节点有路径存在, 即使对于无限图, A* 算法也一定会终止。3 . 3 图搜索算法 3 . 3 . 3 典型的启发式搜索算法

34、分析与改进 A*算法几个重要性质: 性质3 A*算法一定终止在最佳路径上 证明: 假设A*算法不是在最优路径上终止, 而是在某个目标节点t处终止, 则 f(t)=g(t)f*(s0)。但是由性质2证明可知, 在A*算法结束之前, OPEN表中存在着节点x, 它应该在最优路径上 , 且满足 f(x)f*(s0) 此时, A *算法一定会选择x来扩展而不会选择t, 这就与假设矛盾, 所以, A*算法一定会终止在最优路径上。3 . 3 图搜索算法 3 . 3 . 3 典型的启发式搜索算法分析与改进 A*算法几个重要性质:性质4 A*算法是最优的证明: A*算法的搜索效率很大程度上取决h(x), 在满

35、足h(x)h*(x)的前提下, h(x)的值越大越好。 h(x)值越大, 表明它携带的启发信息越多, 搜索时扩展的节点数越少 , 搜索的效率越高。 设f1(x)与f2(x)是对同一问题的两个估价函数 f1(x)=g1(x)+h1(x) f2(x)=g2(x)+h2(x) A1*和A2*分别是以f1(x)及f2(x)为估价函数的A*算法, 且对于所有的非目标节点x均有h1(x)h2(x)。3 . 3 图搜索算法 3 . 3 . 3 典型的启发式搜索算法分析与改进 A*算法几个重要性质:性质4 A*算法是最优的证明（接前页): 此情况下证明A1*扩展的节点数不会比A*2扩展的节点数少, 用归纳法:

36、设K表示搜索树的深度当K=0时, 结论显然成立;设当搜索树的深度为K-1时结论成立, 即A*2扩展了的节点, A*1也扩展了;现仅证明A*2扩展的第K代的任一节点xk也被A*1扩展:3 . 3 图搜索算法 3 . 3 . 3 典型的启发式搜索算法分析与改进 A*算法几个重要性质:性质4 A*算法是最优的证明（接前页): 由假设可知, A*2扩展的前K-1代节点A*1也都扩展了, 因此A1* 搜索树中有一条从初始节点S。到xk的路径, 其费用不会比A*2搜索树从S。到xk的费用更大。 即 g1(xk)g2(xk)假设A*1不扩展节点xk, 这表示A* 1能找到另一个具有更小估价值的节点进行扩展并

37、找到最优解,此时有 f1(xk)f*(S0) 即 g1(xk)+h1(xk)f*(S0) 应用关系式g1(xk)g2(xk)到上列不等式中, 得 h1(xk)f*(S0)-g2(xk), 由于h2(xk)=f*(S0)-g2(xk), 这就得到 h1(xk)h2(xk) 这与最初的假设h1(x)50， 数组元素的下标自然把数据一次定好位置，最后只要按规定的方式调非零元秦，相同元素按计数值次数调动，排序即完成。 枚举计数：如果规则Ri被规则Rj依赖(j=1，2, ., N)，则Pi=pi+1（Pi初值赋1) 。 显然，对于N条规则，每一条都将确定与其它规则的依赖关系并计算，这一过程称之为枚举计数

38、。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析静态算法（上） B1: 初始化，有N条规则，置P1至PN皆为1。 B2:对i循环对i=N，N1，N-2，2执行B3; 然后转B5。 B3:对j循环对j=i-1，i-2，1执行B4; 然后转B2。 B4:寻求Ri被Rj依赖次数若Ri被Rj依赖，PiPi1；否则转B3。 B5: 一遍扫描Pi（i=1，2, .，N)，求Pmax。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析静态算法（上） 静态算法进行到这里，求出了任一规则Ri被依赖次数Pi。Pi对应于Ri，相当于Ri 被

39、 依赖次数Pi。Pi对应Ri，相当于Ri的关键字。其中，很可能出现Pi=Pj (ij), 这说明 Ri和Rj被其它规则依赖的条数相同。怎样快速地按关键字Pi(i=1，2，., N) 大小把规 则快速地排列起来，并满足动态需要，我们采用高效算法映射排序 算法初始按关键字值以映射关系作一次扫描，基本排定规则位置，RiPiD（Pi）。 对相同关键字的处理，算法附加了三个数组空间：每一记录的链指针空间L（i）， 链首指针空间Q，链当前指针空间W。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析静态算法（上） 关键字值Pi与D数组元素下标映射关系有一次时,D(Pi)

40、=1；这时Q(Pi)1，记录了具 有这唯一对应关系Pi所在规则的地址i，并作为最后排序调整位置的首地址。W（Pi）i 为出现相同关键字提供链接地址作准备。 映射时出现相同关键字，如Pi=Pj，这时D（Pi）1，我们把Pi和Pj 对应的两条规则 链接起来，入口地址仍是Q（Pi）=i，但L（W（Pi）j，相当于L(i)=j, 此外，W（Pj）j，为链接出现多个相同关键字作准备。 实施映射和链接处理后，最后再实施一次扫描，根据D数组下标值的有序性，D=0 不实施操作，Dl从相对应的Q数组下标值作为入口地址调整一次规则位置即完成排列。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法

41、排序算法描述与分析静态算法（下） B6：映射初始化，开辟链指针空间L，容量N; 映射计数空间D，链首指针空间Q，链当前指针空间W，容量均为Dmax，赋初值i=1。 B7: 扫描Pi，让D（Pi）D（Pi）1 ；以映射关系确定Pi的位置，记录相同Pi 的 个数。 B8：若D(Pi)=1，作W(Pi)i和Q(Pi)i，转B10。 B9: 若D（Pi）1，作L（W（Pi）i和W(Pi)i。 B10：ii+1，直至i=N为止，实施B7B9。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析静态算法（下） B11:（Z=1)，从J=Dmax开始，若D（J）=0转B12

42、; D（J）0，作递减排列。 (1) TQ（J）；链首指针送T。 (2) 输出RT。 (3) zz 1，若ZD(J)，TL（T）后转(2)；否则转B12。 B12：JJ-1，实施B11，直至J=0结束。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析动态算法规则匹配过程中，如果系统自学习新增一条规则RN+1，将立即置人规则集适当位置，自动启动的算法是： C1：对i=1，2, .，N，若RN+1被Ri依赖，PN+1PN+1+l（PN+1初值赋1）；反之， 若Ri被RN+1依赖，PiPi+1。 C2：若PN+1Pmax，PmaxPN1 C3，调静态算法（下），

43、其中修改NN + 1。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析算法分析1）静态算法（上）时间复杂性为O（N2），因为B1B5执行步骤共需 (N-1)+(N-2)+.+2+1+N=1/2(N2+N)。2）静态算法（下）时间复杂性为O（N），因为算法的构思来源于映射排序算法中的一 部份，其证明可参阅书末文献。由于动态算法仅C1一C2引进附加操作，显然为O(N)，C3为O(N)，所以动态算法时间复杂性为O(N)3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析算法分析3）由于静态算法（下）附加存储空间3Pmax+N，因

44、此， 动态算法获得的高效率是由空间代 价换取的。4） 算法假设了规则自身依赖，所以Pi的初值赋1。5) 算法将规则优先排列，使规则匹配花费平均时间最小。平均时间最小亦说明，一 般状况下，分折的句子越多，其效率越高；但也可能存在某些状况， 所需规则恰好排列在最后。所以，这一算法是平均时间较优算法。3 . 4 产生式系统的规则问题 3 . 4 . 2 规则排序算法 排序算法描述与分析实验结果 排序算法的实验是这样进行的，在上述规则集中，分析4条语句。设计第1 条语句产 生1条规则，该规则2、3、4条语句都将涉及。把这条规则分别放于最后和进行动态排列，结果后者完成2、3、4条语句分析较前者速度提高1

45、倍多。这是一个目前具有3380条规则的 实验系统，有如此实验效果足以说明此算法的实用性。3 . 5 应用举例 任何一种自然语言,总是要遵循一定的语法规则的.计算机要理解、翻译自然语言,就要对理解和翻译的语言建立一套规则,也就是语法, 并且提供一种适合计算机处理的语法描述形式。上下文无关语法是适合描述自然语言的一种体系。作为一个例子, 先来考察汉语的一个很小子集, 它的上下文无关语法由以下一系列重写规则组成:(1) (2) 电脑学院中国地图卫星(3) 购买绘制发射(4) 一颗十台一幅3 . 5 应用举例 在这些重写规则中, 尖括号称之为非终极符; 而电脑、学院称终极符;竖线表示或的意思。这种语法

46、之所以是上下文无关的, 是因为在这些重写规则中, 左边项都是孤立的非终极符, 它们可以被右边的符号串所替换, 而不管左边出现的上下文。 这种语法既可用于生成语法正确的汉语句子,也可用于分析输入的汉语句子是否合乎语法。 下面三例计算机可以简单验证是正确的句子: 1 中国发射一颗卫星 2 学院购买十台电脑 3 电脑绘制一幅地图3 . 5 应用举例即 一种句子结构 名词 动词 数词 名词 中国 发射 一颗 卫星 学院 购买 十台 电脑 电脑 绘制 一幅 地图 上下文无关语法的形式化描述严谨且规范,计算机程序便于实现, 其算法大致上可分为以下三种:自顶向下分析法;自底向上分析法;融合自顶向下和自底向上

47、分析法。 本节仅 探讨自顶向下算法。3 . 5 应用举例自顶向下分析算法(仅针对上述子集): D1: 从规则(1)开始,即从开始,替换成。 D2: 句首切分出的第一词语与(2)中词语匹配,找到转D3;否则转D6。 D3: 句子第 二词语与(3)中词语匹配,找到转D4;否则转D6。 D4: 句子第三词语与(4)中词语匹配,找到转D5;否则转D6。 D5: 句末词语与(2)中词语匹配,找到成功结束;否则转D6。 D6: 失败退出。 产生式规则还可描述成: 条件行动 或 前提结论。 这与重写规则相似, 但使用产生式规则的方法作句法分析,容易分析复杂的句子,操作灵活,也易于模块化和结构化。3 . 5

48、应用举例 用于句法分析的产生式模块经过改进,但仍包含三个基本组成部分: (1) 事实库:改进后的词语库,它进行了词类标注等.如,的/P;涌现/V;价值/A;技术/N; 产品/N;科技园/N;高新/DET (2) 规则集:存储有关语法的状态转移、性质变化等规则的过程性知识。 (3) 控制器:将规则与事实进行匹配,控制句法分析过程。3 . 5 应用举例 例: 定义分析有限个汉语句子的产生式规则(限于篇幅,仅选有关一小部分), 终结目标S。 (1) NNP (2) A NPNP (3) DET NPDNP (4) P DNPPP (5) DNP PPDNP (6) V DNPVP (7) DNP V

49、PS 下面用计算机程序(产生式模块)来分析一个汉语句子是否合法: 高新技术的高新价值产品涌现高新科技园.3 . 5 应用举例 算法执行过程: 经自动分词和算法E1,已得到: DET N P DET A N V DET N 继续执行算法E2E6, 将 NNP(1): DET NP P DET A NP V DET NP 将 A NPNP(2): DET NP P DET NP V DET NP 将 DET NPDNP(3): DNP P DNP V DNP 将 P DNPPP(4): DNP PP V DNP 将 DNP PPDNP(5): DNP V DNP 将 V DNPVP(6): DNP

50、 VP 将 DNP VPS(7): S (合法而结束) 3 . 6 产生式系统的不确定性问题 产生式系统在应用中, 结论可能是不完全确定的。因此, 产生式系统的设计应考虑不确定性的搜索过程. 有两种不确定性: 证据不确定性和结论不确定性。 3 . 6 产生式系统的不确定性问题 3 . 6 . 1 关于证据不确定性 当在考虑问题时, 所遇到的经常具有某种不确定性。例如, 当你观察某种动物的颜色时, 有可能认为这种动物是白色的, 但也可能是灰色的。 这就是说, 你的观察具有某 种不确定性。 在考虑问题时, 所带有的干扰或不精确性都会导致证据的不确定性。 目前人们用来处理不确定性的启发式方法, 在理

51、论上应该还是不严格的, 但在实际应用中却可解决某些实际问题。 3 . 6 产生式系统的不确定性问题 3 . 6 . 1 关于证据不确定性 一般通过对事实赋于一个介于0和1之间的系数来表示事实的不确定性。 1代表完全确定, 0代表完全不确定。 这个系数称为可信度(也有取可信度的范围-1到+1)。 当规则具有 一个以上的条件时, 就需要根据各条件的可信度来求得总条件部分的可信度。 已有的方法有两类: 3 . 6 产生式系统的不确定性问题 3 . 6 . 1 关于证据不确定性 (1) 以模糊集理论为基础的方法 按这种方法, 把所有条件中最小的可信度作为总条件的可信度。 例如, 具有三个条 件的规则,

52、 对每个证据各自的可信度分别赋于以及的可信度。 如果从每个证 据各自的可信度得到这个规则的总输入的可信度, 取最小值就是。 产生式规则的各个 条件之间是合取的关系, 取其可信度的最小值代表总的可信度, 这也符合模糊理论。 总之, 这种方法类似于, 当把几根绳子连接起来时, 总的绳子的强度等于其中最差 的绳子强度。 3 . 6 产生式系统的不确定性问题 3 . 6 . 1 关于证据不确定性(2) 以概率论为基础的方法 这种方法同样赋于每个证据可信度。 但当把单独条件的可信度结合起来求总的可信 度时, 它取决于各可信度的乘积。 采用上述例子, 这时规则的输入部分的可信度为。 因为规则的输入部分的各

53、个条件之间是合取关系, 总的可信度是各个分量的可信度 乘积, 这看起来是符合概率理论的。 因此这种方法称为以概率为基础的方法。 但根据概率论, 若要总的概率为各分量概率之乘积的先决条件是各分量之间是独立的。 然而, 这里并不能检验各条件之间是否相互独立。 因此, 从这点上讲, 这是一种不完全合法的应 用。 3 . 6 产生式系统的不确定性问题 3 . 6 . 2 关于结论的不确定性 关于结论的不确定性是在规则的条件被完全满足时, 产生某种不确定的结论。 这种 结论不确定的程度, 是以赋以规则一个在0和1之间的系数的方法来表示的。 例如, 有以下规则: IF 启动器发出刺耳的噪声 THEN 启动

54、器坏的可能性是 以上规则表示, 若事实完全肯定即可信度应为1.0; 但规则的条件部分不能完全确定, 即证据的可信度不为1时, 求结论的可信度有两种方法: 3 . 6 产生式系统的不确定性问题 3 . 6 . 2 关于结论的不确定性 (1) 取结论的可信度为条件的可信度与上述系数的乘积。 例如, 如果取条件可信度为0.5, 则结论可信度Cout=0.50.8=0.4.(2) 按照某种概率理论的解释, 可以假设规则的条件部分的可信度Cin和其结论部分 的可信度Cout存在某种关系, 这种关系可用来代表规则的不确定性。 下面为三种这样的关系曲线。（图 28） 3 . 6 产生式系统的不确定性问题 3

55、 . 6 . 2 关于结论的不确定性 Cout Cout Cout 先验值 1.0 1.0 1.0 - - - - - - 先验值 Cin Cin Cin (a) 1.0 (b) 1.0 (c) 1.0 图 28 3 . 6 产生式系统的不确定性问题 3 . 6 . 2 关于结论的不确定性 (a)所示的Cin与Cout的关系所代表的就是乘积方法, 结论的可信度Cout 等于条件的可信度Cin和某个系数的乘积; (b)所示的关系即使条件这边完全确定, 即Cin=0时, 结论 的可信度Cout仍为0.2, 这意味着, 即使条件这边的证据不存在, 也可以得到结论。 在大多数情况下, Cin与Cout

56、的关系曲线由两条直线组成, 如( c) 所示。 这种状况, Cin和Cout之间的关系不仅要反映终点的条件, 而且要反映开始分析以前的估计。 这种估 计也称为先验值, 这个值说明当完全没有要处理情况的预置可信度。 例如, 你要接手某问题时, 你可以估计这个问题的许多方面, 当然, 这是依据你的经验得出的, 即赋于一定程度的可信度.。这就是给予的先验可信度。 3 . 6 产生式系统的不确定性问题 3.6.3 多个规则支持的同一事实的不确定性 当多个规则支持同一事实时, 这些规则之间的关系是析取. 也有两种方法:(1) 基于模糊理论的方法 取支持这个事实的各规则的可信度的最大值作为事实的可信度,

57、这类似于模糊集理论中当多个条件相析取时, 取这些条件中的隶属函数的最大值作为总的隶属函数值。 3 . 6 产生式系统的不确定性问题 3.6.3 多个规则支持的同一事实的不确定性 (2) 基于概率论的方法 这里论述的只是基于概率的方法中的一种, 一组规则支持的事实的可信度, 可用以下方法求得, 首先把各个证据的可信度转换成可信性比例r。 可信性比例r和可信度C之间 的关系可表示为 r=C/(1-C) 或 C=r/(r+1) 把各证据的可信性比例简单相乘就可以求得这些证据所支持的事实的可行性比例。然后, 再利用上述公式转换回相应的可信度。这样就可求得这个事实的可信度。当时, 相应的r=1, 这时称

58、为中性的可信性比例。 3 . 6 产生式系统的不确定性问题 3.6.3 多个规则支持的同一事实的不确定性 例: C1=0.9 C2=0.25, 与此相应的r1和r2分别为 r1=0.9/(1-0.9)=9 r2=0.25/(1-0.25)=1/3 取r1和r2的乘积作为这个事实的可信性比例r r=r1r2=91/3=3 因此相应的可信度C为 这样求得的可信度为0.75, 这个数值比按以模糊集理论为基础的方法求得的可信度低。 这是因为其中一个证据的可信度为0.25, 这实际上是否定这个事实。 如果这个证据的可信度大于0.5, 按这种方法求得的可信度就会大于。 3 . 6 产生式系统的不确定性问题

59、 3.6.3 多个规则支持的同一事实的不确定性应用以概率论为基础的方法有以下两个困难: (1) 按照概率论, 应该检查支持同一事实的各个规则之间是否相互独立, 而实际上难以进行这样的检查。 (2) 如果有以下规则 IF 启动器发出刺耳噪声 THEN 启动器坏的可能0.75 按概率论, 意味着还存在另一条规则: IF 启动器发出刺耳噪声 THEN 启动器好的可能 在许多问题中, 不允许同时使用这样的规则。3 . 6 产生式系统的不确定性问题 3. 6 . 4 非精确推理的原理智能系统的设计将面临两个问题: (1) 在实际问题中, 我们模拟人所处理的信息有许多是不确定的, 不精确的, 不完 全知道

60、的。只要是智能系统, 一般都处在这样的设计环境中。 (2) 为了防止辅助知识和规则太多而引起组合爆炸, 有意识引入非精确推理方法。 这样, 既减少了智能系统设计的复杂性, 又可提高系统运行的速度。 非精确推理用于基本规则的智能系统的核心思想是: 为原始证据和规则本身赋于一个不确定的度量, 在给出一组算法, 在此基础上利用这组算法, 求出规则中的结论部分的不确定性。 非精确推理一个可采用规则为下述结构: IF E THEN H(X)3 . 6 产生式系统的不确定性问题 3. 6 . 4 非精确推理的原理 其中, E是证据, H是假设, X是规则的不确定因子, 或称规则强度。 证据E和假设H都是由