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

(1)(2)√-OR图启发式搜索Date1人工智能丁世飞启发式搜索通常用于两种不同类型的问题:(1)正向推理(2)反向推理正向推理一般用于状态空间的搜索。在正向推理中,推理是从预选定义的初始状态出发向目标状态方向执行。上一节介绍的启发式搜索算法,如最好优先算法(或OR图算法)、启发式图搜索算法(或A算法)、A*算法等等。都属于状态空间搜索问题。引言Date2人工智能丁世飞在状态空间搜索中,搜索过程只记录状态空间中被搜索过的状态,它们构成一个搜索图G,G由Open节点与Closed节点组成。在状态空间表示法中,由表示一个问题的全部状态以及一切可用的算符构成的集合称为该问题的状态空间,它一般表示为一个三元组:(S,F,G)其中:S表示问题的所有初始状态的集合,F是算符的集合,G是目标状态的集合。其状态搜索过程通常用搜索图或搜索树来表示。本节我们将学****问题归约法。-OR图启发式搜索问题归约法不同于状态空间法,是另一种问题描述和求解的方法。所谓问题归约:在问题求解过程中,将一个大的问题变换成若干个子问题,子问题又可以分解成更小的子问题,这样一直分解到可以直接求解为止,全部子问题的解就是原问题的解;并称原问题为初始问题,可直接求解的问题为本原问题。AND-OR图的反向推理过程可以看作是一个问题归约的过程。:(S0,O,P),其中S0是初始问题,即要求解的问题;P是本原问题集,其中的每一个问题是不用证明的,自然成立的,如公理、已知事实等,或已证明过的问题;O是操作算子集,它是一组变换规则,通过一个操作算子把一个问题化成若干个子问题。Date5人工智能丁世飞问题归约表示方法就是由初始问题出发,运用操作算子产生一些子问题,对子问题再运用操作算子产生子问题的子问题,这样一直进行到产生的问题均为本原问题,则问题得解。:初始问题——∫f(x)dx变换规则——积分规则本原问题——可直接求原函数的积分,如∫sin(x)dx,∫cos(x)dx等。注意:所有问题归约的最终目的是产生本原问题。-OR图表示用AND-OR图把问题归约为子问题替换集合。例如,假设问题A既可通过问题C1与C2,也可通过问题C3、C4和C5,或者由单独求解问题C6来解决,如下图所示。。,用一个连接它们的圆弧来标记。一般而言,这种弧叫K连接弧,表示对问题A由某个操作算子作用后产生K个子问题。这样,连接C1与C2和C3、C4、C5的圆弧分别叫2连接弧和3连接弧。-:问题C1和C2构成后继问题的一个集合,问题C3、C4和C5构成另一后继问题集合;而问题C6则为第三个集合。-连接弧的AND--OR图表示注意以下几个问题:1、由节点及K连接弧组成的图,称为AND-OR图,当所有K均为1时,就变为普通的OR图。2、-OR图进行变换,引进某些附加节点,以便使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下。这样,。每个节点的后继只包含一个K连接弧。Date10人工智能丁世飞