资源描述：
《人工智能与专家系统第3章节搜索方法课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、人工智能与专家系统第3章搜索方法3.1问题求解过程的形式表示3.2状态空间的搜索方法3.3与∕或图的搜索方法第3章搜索方法根据领域知识的多寡，分为知识贫乏系统和知识丰富系统。知识贫乏系统的求解问题如果能设计一个操作算子（算符）集,则可使用搜索技术求解。知识丰富系统的求解问题依靠推理技术求解。3.1问题求解过程的形式表示3.1.1状态空间表示法3.1.2与/或图表示法3.1.1状态空间表示法状态空间表示法用“状态”和“算符”来表示问题及求解问题可使用的知识。状态：是求解过程中用以描述问题在任一时刻状况的数据结构。算
2、符：表示对状态的操作，算符的一次使用就使问题由一种状态变换为另一种状态。问题的解：当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题的一个解。由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：（S，F，G）其中S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边（弧）表示算符。例3.1二阶梵塔问题设有三根柱子，在1号柱子上穿有A、B两个盘片，盘A小于盘B，盘A位于盘B的上面。要求把这两个盘片全
3、部移到另一根柱子上，而且规定每次只能移动一片，任何时刻都不能使盘B位于盘A的上面。画出二阶梵塔问题的状态空间有向图，并给出问题的解。解：设用S=（xA,xB）表示问题的状态，xA表示盘A所在的柱号，xB表示盘B所在的柱号。全部可能的状态有以下9种：S0=（1,1）S1=（1,2）S2=（1,3）S3=（2,1）S4=（2,2）S5=（2,3）S6=（3,1）S7=（3,2）S8=（3,3）问题的初始状态集合为S={S0}，目标状态集合为G={S4,S8}。算符：A(i,j)表示把盘A从柱i移到柱j上；B(i,j)
4、表示把盘B从柱i移到柱j上。共有12个算符，它们分别是：A(1,2)，A(1,3)，A(2,1)，A(2,3)，A(3,1)，A(3,2)B(1,2)，B(1,3)，B(2,1)，B(2,3)，B(3,1)，B(3,2)图3.1二阶梵塔的状态空间1,12,12,33,31,22,23,23,11,3B(1,2)A(1,3)A(3,2)3.1.2与/或图表示法问题归约方法:把初始问题通过一系列变换最终变为由若干子问题组成的集合，而这些子问题的解可以直接得到，从而解答了初始问题。问题归约方法表示问题及其求解过程用与/
5、或图表示。1分解变换问题的分解过程可用一个“与树”表示。把问题P分解为三个子问题P1、P2、P3，只有当P1、P2、P3三个子问题都可解时，问题P才可解，称P1、P2、P3之间存在“与关系”；称节点P为“与节点”。图3.2与树2等价变换问题的等价变换过程可用一个“或树”表示。问题P被等价变换为新问题P1、P2、P3，其中，新问题P1、P2、P3中只要有一个可解，则原问题就可解，称P1、P2、P3之间存在“或关系”；节点P称为“或节点”。PP1P2P3图3.2或树与/或树:其中既有“与”节点，也有“或”节点。PP2
6、P3P1P11P12P31P32P33图3.4与/或树3本原问题直接可解的子问题称为本原问题。4端节点与终叶节点没有子节点的节点称为端节点；本原问题所对应的端节点称为终叶节点。5可解节点①它是一个终叶节点。②它是一个“或”节点，且其子节点至少有一个是可解节点。③它是一个“与”节点，且其子节点全部是可解节点。6不可解节点①它是一个非终叶节点的端节点，即无法变换的非终叶节点。②它是一个“或”节点，且其子节点全部是不可解节点。③它是一个“与”节点，且其子节点至少有一个是不可解节点。7解树由可解节点构成的、且由这些可解节
7、点可推出初始节点（它对应于原始问题）为可解节点的与/或树称为解树。例3.2三阶梵塔问题：如图3.5所示。应用分解变换求解三阶梵塔问题。（a）初始状态（b）目标状态图3.5三阶梵塔问题可把原问题分解为三个子问题：（1）把盘片A及B移到2号柱的双盘片问题。（2）把盘片C移到3号柱的单盘片问题。（3）把盘片A及B移到3号柱的双盘片问题。解：定义问题的状态表示：S=（xC，xB，xA）其中xC表示盘片C所在的柱号；xB表示盘片B所在的柱号；xA表示盘片A所在的柱号。算符集：F={A(i,j),B(i,j),C(i,j)}
8、,分别表示把盘A，B，C从柱i移到柱j上。初始问题：(（1,1,1）,F,（3,3,3）)可用与/或树把分解过程表示出来，如图3.6所示。图3.6三阶梵塔问题的与/或树7个终叶节点对应于7个本原问题：(（1,1,1）,（1,1,3）)，(（1,1,3）,（1,2,3）)，(（1,2,3）,（1,2,2）),(（1,2,2）,（3,2,2）)，(（3,2,2）,（3,2,1
