问题归约和ANDOR图启发式搜索ppt课件.ppt

《问题归约和ANDOR图启发式搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能第3章搜索策略3.1引言3.2盲目搜索3.3启发式搜索(1)3.3启发式搜索(2)√3.4问题归约和AND-OR图启发式搜索2021/7/281人工智能丁世飞启发式搜索通常用于两种不同类型的问题：（1）正向推理（2）反向推理正向推理一般用于状态空间的搜索。在正向推理中，推理是从预选定义的初始状态出发向目标状态方向执行。上一节介绍的启发式搜索算法，如最好优先算法（或OR图算法）、启发式图搜索算法（或A算法）、A*算法等等。都属于状态空间搜索问题。引言2021/7/282人工智能丁世飞在状态空间搜索中，搜索过程只记录

2、状态空间中被搜索过的状态，它们构成一个搜索图G,G由Open节点与Closed节点组成。在状态空间表示法中，由表示一个问题的全部状态以及一切可用的算符构成的集合称为该问题的状态空间，它一般表示为一个三元组：（S,F,G)其中：S表示问题的所有初始状态的集合，F是算符的集合，G是目标状态的集合。其状态搜索过程通常用搜索图或搜索树来表示。本节我们将学习问题归约法。引言2021/7/283人工智能丁世飞3.4问题归约和AND-OR图启发式搜索问题归约法不同于状态空间法，是另一种问题描述和求解的方法。所谓问题归约：在问题求解过程

3、中，将一个大的问题变换成若干个子问题，子问题又可以分解成更小的子问题，这样一直分解到可以直接求解为止，全部子问题的解就是原问题的解；并称原问题为初始问题，可直接求解的问题为本原问题。AND-OR图的反向推理过程可以看作是一个问题归约的过程。2021/7/284人工智能丁世飞3.4.1问题归约的描述问题归约可以用三元组表示:(S0,O,P),其中S0是初始问题，即要求解的问题；P是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或已证明过的问题；O是操作算子集，它是一组变换规则，通过一个操作算子把

4、一个问题化成若干个子问题。2021/7/285人工智能丁世飞问题归约表示方法就是由初始问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直进行到产生的问题均为本原问题，则问题得解。3.4.1问题归约的描述2021/7/286人工智能丁世飞看如下符号积分问题：初始问题——∫f(x)dx变换规则——积分规则本原问题——可直接求原函数的积分，如∫sin(x)dx，∫cos(x)dx等。注意：所有问题归约的最终目的是产生本原问题。3.4.1问题归约的描述2021/7/287人工智能丁世飞3.4

5、.2AND-OR图表示用AND-OR图把问题归约为子问题替换集合。例如，假设问题A既可通过问题C1与C2，也可通过问题C3、C4和C5，或者由单独求解问题C6来解决，如下图所示。图3.6中各节点表示要求解的问题或子问题。图3.6子问题替换集合的结构2021/7/288人工智能丁世飞对应于某个给定集合的各节点，用一个连接它们的圆弧来标记。一般而言，这种弧叫K连接弧，表示对问题A由某个操作算子作用后产生K个子问题。这样，连接C1与C2和C3、C4、C5的圆弧分别叫2连接弧和3连接弧。3.4.2AND-OR图表示如图3.7所示

6、：问题C1和C2构成后继问题的一个集合，问题C3、C4和C5构成另一后继问题集合；而问题C6则为第三个集合。图3.7各节点后继只含一个K-连接弧的AND-OR图2021/7/289人工智能丁世飞3.4.2AND-OR图表示注意以下几个问题：1、由节点及K连接弧组成的图，称为AND-OR图，当所有K均为1时，就变为普通的OR图。2、可以对如图3.6所示的AND-OR图进行变换，引进某些附加节点，以便使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下。这样，图3.6就变为图3.7所示的结构了。每个节点的后继只包

7、含一个K连接弧。2021/7/2810人工智能丁世飞3.4.2AND-OR图表示图3.6到图3.7的变换过程图3.6子问题替换集合的结构图3.7各节点后继只含一个K-连接弧的AND-OR图2021/7/2811人工智能丁世飞3、弧连接的子节点叫与节点。如图3.7中C1、C2及C3、C4、C5。4、K=1的连接弧连接的子节点叫做或节点。如图3.7中C6。3.4.2AND-OR图表示图3.7各节点后继只含一个K-连接弧的AND-OR图2021/7/2812人工智能丁世飞5、在下面的讨论中，假设AND-OR图中每个节点，只包含

8、一个K连接弧的子节点。6、将问题求解归约为AND-OR图搜索时，将初始节点表示初始问题描述，对应于本原问题的节点称为叶节点。7、在AND-OR图上执行的搜索过程，其目的在于表明起始节点是有解的。3.4.2AND-OR图表示2021/7/2813人工智能丁世飞AND-OR图中的一个可解节点可递归地定义如下：（1）叶节点