人工智能原理2.ppt

《人工智能原理2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、回顾1、绪论人工智能的定义人工智能的起源与发展人工智能三大学派人工智能的研究与应用领域1回顾2、知识表示与推理的基础一阶谓词逻辑表示法产生式表示法框架表示法语义网络表示法脚本表示法过程表示法混合型知识表示方法面向对象表示法2第二讲搜索技术1、状态空间表示法2、与或树表示法3、盲目搜索4、启发式搜索5、A*算法6、博弈树搜索3Part1搜索技术根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。搜索分为盲目搜索和启发式搜索41、盲目搜索盲目搜索是按预定的搜索方向进行搜索。由于盲目搜索总是按预先规定的路线进行

2、，没有考虑到问题本身的特性，所以这种搜索效率不高。2、启发式搜索启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的推理方向前进，加速问题的求解过程并找到最优解。5问题求解过程的形式表示为了进行搜索，首先必须考虑问题及其求解过程的形式表示，其表示是否适当，将直接影响到搜索求解的效率。1、状态空间表示法2、与或树表示法6状态空间表示法状态空间表示法用“状态”和“算符”来表示问题，其中“状态”用以描述问题求解过程不同时刻的状态；“算符”表示对状态的操作，算符的每一次使用就使状态发生变化。当到达目标状态时，有初始状态到目标状态所使用的算符序

3、列就是问题的一个解。7状态空间表示法①状态：是描述问题求解过程不同时刻的状态的数据结构，可用一组变量的有序集表示：当给每一个分量以确定的值时，就得到了一个具体的状态②算符：引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中，每一条产生式规则就是一个算符Sk=(Sk1,Sk2,…,Skn)8状态空间表示法③状态空间：由问题的全部状态及一些可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：(S,F,G)其中S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。状态空间的图示形式称为状态空间图。

4、其中节点表示状态；有向边表示算符。9状态空间表示法2阶“梵塔”问题状态空间方法有三个柱子(1，2和3)和两个不同尺寸的圆盘(A，B)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上,最初,全部两个圆盘都堆在柱子1上(最大的在底部,最小的在顶部)。要求把所有圆盘都移到另一个柱子上，搬动规则为:(1)一次只能搬一个圆盘(2)不能将大圆盘放在小圆盘(3)可以利用空柱子。10状态空间表示法用状态空间方法来描述问题：状态的表示柱的编号用i,j来代表(i,j)表示问题的状态其中:i代表A所在的柱子,j代表B所在的柱子状态集合(9种可能的状态)s0=(1,1),s1=

5、(1,2),s2=(1,3)s3=(2,1),s4=(2,2),s5=(2,3)s6=(3,1),s7=(3,2),s8=(3,3)11状态空间表示法初始状态S={s0}，目标状态G={s4,s8}S0=(1,1)A132BS4=(2,2)123ABS8=(3,3)123AB12状态空间表示法操作（算符）定义操作A(i,j),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)13状态空间图S0(1,1)S

6、3(2,1)S3(3,1)S5(2,3)S7(3,2)S8(3,3)S2(1,3)S1(1,2)S4(2,2)A(1,3)B(1,2)A(3,2)目标目标初始A(1,2)B(1,3)A(2,3)14与/或树表示法与/或树是用于表示问题及其求解过程的又一种形式化方法，也称为问题归约方法。问题归约:含义:把复杂问题转换为若干需要同时处理的较为简单的子问题后再加以分别求解的策略,可以递归地进行,直到把问题转换为本原问题的集合.方法:分解,变换15与/或树表示法1、分解把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干个更为简单的子问题。重复此

7、过程，直到不需要在分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到原问题的解。16与/或树表示法“与“树PP1P2P3与节点17与/或树表示法2、变换：对于一个复杂问题，除了可以用“分解”方法进行求解外，还可利用同构或同态的等价变换，把它变换成若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。18与/或树表示法“或“树PP1P2P3或节点19与/或树表示法上述两种方法也可结合起来使用，此时的图称为”与/或树”（AND/ORTree）。其中既有与节点，又有或节点。PP1P2P3P31P32P33P11

8、P12“与/或“树20与/或树表示法3、本原问题：不