清华大学《人工智能导论》课程电子教案(一).ppt
- 文档编号:18717848
- 上传时间:2023-10-18
- 格式:PPT
- 页数:143
- 大小:888KB
清华大学《人工智能导论》课程电子教案(一).ppt
《清华大学《人工智能导论》课程电子教案(一).ppt》由会员分享,可在线阅读,更多相关《清华大学《人工智能导论》课程电子教案(一).ppt(143页珍藏版)》请在冰点文库上搜索。
1,第一章产生式系统,1943年Post首先在一种计算形式体系中提出60年代开始,成为专家系统的最基本的结构形式上很简单,但在一定意义上模仿了人类思考的过程,2,1.1产生式系统的基本组成,组成三要素:
一个综合数据库存放信息一组产生式规则知识一个控制系统规则的解释或执行程序(控制策略)(推理引擎),3,规则的一般形式,IFTHENIFTHEN或者简写为:
4,1.2产生式系统的基本过程,过程PRODUCTION1,DATA初始数据库2,untilDATA满足结束条件,do3,4,在规则集中选择一条可应用于DATA的规则R5,DATAR应用到DATA得到的结果6,,5,一个简单的例子,问题:
设字符转换规则ABCACDBCGBEFDE已知:
A,B求:
F,6,一个简单的例子(续1),一、综合数据库x,其中x为字符二、规则集,1,IFABTHENC2,IFACTHEND3,IFBCTHENG4,IFBETHENF5,IFDTHENE,7,一个简单的例子(续2),三、控制策略顺序排队四、初始条件A,B五、结束条件Fx,8,求解过程,数据库可触发规则被触发规则,A,B,
(1),
(1),A,B,C,
(2)(3),
(2),A,B,C,D,(3)(5),(3),A,B,C,D,G,(5),(5),A,B,C,D,G,E,(4),(4),A,B,C,D,G,E,F,1,IFABTHENC2,IFACTHEND3,IFBCTHENG4,IFBETHENF5,IFDTHENE,9,1.3问题表示举例,例1:
传教士与野人问题(M-C问题)问题:
N个传教士,N个野人,一条船,可同时乘坐k个人,要求在任何时刻,在河的两岸,传教士人数不能少于野人的人数。
问:
如何过河。
以N=3,k=2为例求解。
10,M-C问题(续1),初始目标LRLRm30m03c30c03B10B01,11,M-C问题(续2),1,综合数据库(m,c,b),其中:
0m,c3,b0,12,初始状态(3,3,1)3,目标状态(结束状态)(0,0,0),12,M-C问题(续3),4,规则集IF(m,c,1)THEN(m-1,c,0)IF(m,c,1)THEN(m,c-1,0)IF(m,c,1)THEN(m-1,c-1,0)IF(m,c,1)THEN(m-2,c,0)IF(m,c,1)THEN(m,c-2,0),13,M-C问题(续4),IF(m,c,0)THEN(m+1,c,1)IF(m,c,0)THEN(m,c+1,1)IF(m,c,0)THEN(m+1,c+1,1)IF(m,c,0)THEN(m+2,c,1)IF(m,c,0)THEN(m,c+2,1)5,控制策略:
(略),14,M-C问题(第二种方法),4,规则集:
IF(m,c,1)AND1i+j2THEN(m-i,c-j,0)IF(m,c,0)AND1i+j2THEN(m+i,c+j,1),15,猴子摘香蕉问题,cab,16,猴子摘香蕉问题(续1),1,综合数据库(M,B,Box,On,H)M:
猴子的位置B:
香蕉的位置Box:
箱子的位置On=0:
猴子在地板上On=1:
猴子在箱子上H=0:
猴子没有抓到香蕉H=1:
猴子抓到了香蕉,17,猴子摘香蕉问题(续2),2,初始状态(c,a,b,0,0)3,结束状态(x1,x2,x3,x4,1)其中x1x4为变量。
18,猴子摘香蕉问题(续3),4,规则集r1:
IF(x,y,z,0,0)THEN(w,y,z,0,0)r2:
IF(x,y,x,0,0)THEN(z,y,z,0,0)r3:
IF(x,y,x,0,0)THEN(x,y,x,1,0)r4:
IF(x,y,x,1,0)THEN(x,y,x,0,0)r5:
IF(x,x,x,1,0)THEN(x,x,x,1,1)其中x,y,z,w为变量,19,1.4产生式系统的特点,数据驱动知识的无序性控制系统与问题无关数据、知识和控制相互独立,20,1.5产生式系统的类型,正向、逆向、双向产生式系统可交换的产生式系统可分解的产生式系统,21,第二章产生式系统的搜索策略,内容:
状态空间的搜索问题。
搜索方式:
盲目搜索启发式搜索关键问题:
如何利用知识,尽可能有效地找到问题的解(最佳解)。
22,产生式系统的搜索策略(续1),S0,Sg,23,产生式系统的搜索策略(续2),讨论的问题:
有哪些常用的搜索算法。
问题有解时能否找到解。
找到的解是最佳的吗?
什么情况下可以找到最佳解?
求解的效率如何。
24,2.1回溯策略,例:
皇后问题,25,(),26,(),Q,(1,1),27,(),Q,Q,(1,1),(1,1)(2,3),28,(),Q,(1,1),(1,1)(2,3),29,(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),30,(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),31,(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),32,(),Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),33,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),34,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),35,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),36,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),37,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),Q,(1,2)(2,4)(3,1)(4,3),38,递归的思想,当前状态,目标状态g,39,一个递归的例子,intListLenght(LIST*pList)if(pList=NULL)return0;elsereturnListLength(pList-next)+1;,40,回溯搜索算法,BACKTRACK(DATA)DATA:
当前状态。
返回值:
从当前状态到目标状态的路径(以规则表的形式表示)或FAIL。
41,回溯搜索算法,递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:
=APPRULES(DATA);4,LOOP:
IFNULL(RULES)RETURNFAIL;5,R:
=FIRST(RULES);6,RULES:
=TAIL(RULES);7,RDATA:
=GEN(R,DATA);8,PATH:
=BACKTRACK(RDATA);9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);,42,存在问题及解决办法,解决办法:
对搜索深度加以限制记录从初始状态到当前状态的路径,问题:
深度问题,死循环问题,43,回溯搜索算法1,BACKTRACK1(DATALIST)DATALIST:
从初始到当前的状态表(逆向)返回值:
从当前状态到目标状态的路径(以规则表的形式表示)或FAIL。
44,回溯搜索算法1,1,DATA:
=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST)RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)BOUNDRETURNFAIL;6,RULES:
=APPRULES(DATA);7,LOOP:
IFNULL(RULES)RETURNFAIL;8,R:
=FIRST(RULES);,45,回溯搜索算法1(续),9,RULES:
=TAIL(RULES);10,RDATA:
=GEN(R,DATA);11,RDATALIST:
=CONS(RDATA,DATALIST);12,PATH:
=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);,46,一些深入的问题,失败原因分析、多步回溯,47,一些深入问题(续),回溯搜索中知识的利用基本思想(以皇后问题为例):
尽可能选取划去对角线上位置数最少的。
48,2.2图搜索策略,问题的引出回溯搜索:
只保留从初始状态到当前状态的一条路径。
图搜索:
保留所有已经搜索过的路径。
49,一些基本概念,节点深度:
根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,50,一些基本概念(续1),路径设一节点序列为(n0,n1,nk),对于i=1,k,若节点ni-1具有一个后继节点ni,则该序列称为从n0到nk的路径。
路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。
用C(ni,nj)表示从ni到nj的路径的耗散值。
51,一些基本概念(续1),扩展一个节点生成出该节点的所有后继节点,并给出它们之间的耗散值。
这一过程称为“扩展一个节点”。
52,一般的图搜索算法,1,G=G0(G0=s),OPEN:
=(s);2,CLOSED:
=();3,LOOP:
IFOPEN=()THENEXIT(FAIL);4,n:
=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)mi,G:
=ADD(mi,G);,53,一般的图搜索算法(续),7,标记和修改指针:
ADD(mj,OPEN),并标记mj到n的指针;计算是否要修改mk、ml到n的指针;计算是否要修改ml到其后继节点的指针;8,对OPEN中的节点按某种原则重新排序;9,GOLOOP;,54,节点类型说明,.,.,.,.,.,mj,mk,ml,55,修改指针举例,1,2,3,4,5,6,s,56,修改指针举例(续1),1,2,3,4,5,6,s,57,1,2,3,4,5,6,修改指针举例(续2),s,58,1,2,3,4,5,6,修改指针举例(续3),s,59,2.3无信息图搜索过程,深度优先搜索宽度优先搜索,60,深度优先搜索,1,G:
=G0(G0=s),OPEN:
=(s),CLOSED:
=();2,LOOP:
IFOPEN=()THENEXIT(FAIL);3,n:
=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)DmGOLOOP;7,EXPAND(n)mi,G:
=ADD(mi,G);8,IF目标在mi中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;,61,23184765,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,62,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏情况时,搜索空间等同于穷举与回溯法的差别:
图搜索是一个通用的与问题无关的方法,63,宽度优先搜索,1,G:
=G0(G0=s),OPEN:
=(s),CLOSED:
=();2,LOOP:
IFOPEN=()THENEXIT(FAIL);3,n:
=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)mi,G:
=ADD(mi,G);7,IF目标在mi中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;,64,23184765,1,2,5,6,7,3,目标,8,4,65,宽度优先搜索的性质,当问题有解时,一定能找到解当问题为单位耗散值,且问题有解时,一定能找到最优解方法与问题无关,具有通用性效率较低属于图搜索方法,66,渐进式深度优先搜索方法,目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。
思想首先给回溯法一个比较小的深度限制,然后逐渐增加深度限制,直到找到解或找遍所以分支为止。
67,2.4启发式图搜索,利用知识来引导搜索,达到减少搜索范围,降低问题复杂度的目的。
启发信息的强度强:
降低搜索工作量,但可能导致找不到最优解弱:
一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解,68,希望:
引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率。
69,基本思想,定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。
70,1,启发式搜索算法A(A算法),评价函数的格式:
f(n)=g(n)+h(n)f(n):
评价函数h(n):
启发函数,71,符号的意义,g*(n):
从s到n的最短路径的耗散值h*(n):
从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n):
从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值,72,A算法,1,OPEN:
=(s),f(s):
=g(s)+h(s);2,LOOP:
IFOPEN=()THENEXIT(FAIL);3,n:
=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)mi,计算f(n,mi):
=g(n,mi)+h(mi);,73,A算法(续),ADD(mj,OPEN),标记mj到n的指针;IFf(n,mk)f(mk)THENf(mk):
=f(n,mk),标记mk到n的指针;IFf(n,ml)f(ml,)THENf(ml):
=f(n,ml),标记ml到n的指针,ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序;8,GOLOOP;,74,.,.,.,.,.,mj,mk,ml,n,a,b,75,Closed表,Open表,76,一个A算法的例子,定义评价函数:
f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数,28316475,12384765,77,h计算举例,h(n)=4,28316475,123,45,76,8,78,28316475,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,79,2,最佳图搜索算法A*(A*算法),在A算法中,如果满足条件:
h(n)h*(n)则A算法称为A*算法。
80,A*条件举例,8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和,81,A*算法的性质,A*算法的假设设ni、nj是任意两个节点,有:
C(ni,nj)其中为大于0的常数,几个等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点,t是目标节点,n是s到t的最佳路径上的节点。
82,A*算法的性质(续1),定理1:
对有限图,如果从初始节点s到目标节点t有路径存在,则算法A一定成功结束。
83,A*算法的性质(续2),引理2.1:
对无限图,若有从初始节点s到目标节点t的路径,则A*不结束时,在OPEN表中即使最小的一个f值也将增到任意大,或有f(n)f*(s)。
84,A*算法的性质(续3),引理2.2:
A*结束前,OPEN表中必存在f(n)f*(s)。
存在一个节点n,n在最佳路径上。
f(n)=g(n)+h(n)=g*(n)+h(n)g*(n)+h*(n)=f*(n)=f*(s),85,A*算法的性质(续3),定理2:
对无限图,若从初始节点s到目标节点t有路径存在,则A*一定成功结束。
引理2.1:
A*如果不结束,则OPEN中所有的n有f(n)f*(s)引理2.2:
在A*结束前,必存在节点n,使得f(n)f*(s)所以,如果A*不结束,将导致矛盾。
86,A*算法的性质(续4),推论2.1:
OPEN表上任一具有f(n)f*(s)的节点n,最终都将被A*选作扩展的节点。
由定理2,知A*一定结束,由A*的结束条件,OPEN表中f(t)最小时才结束。
而f(t)f*(t)f*(s)所以f(n)f*(s)的n,均被扩展。
得证。
87,A*算法的性质(续5),定理3(可采纳性定理):
若存在从初始节点s到目标节点t有路径,则A*必能找到最佳解结束。
88,可采纳性的证明,由定理1、2知A*一定找到一条路径结束设找到的路径st不是最佳的(t为目标)则:
f(t)=g(t)f*(s)由引理2.2知结束前OPEN中存在f(n)f*(s)的节点n,所以f(n)f*(s)f(t)因此A*应选择n扩展,而不是t。
与假设A*选择t结束矛盾。
得证。
注意:
A*的结束条件,89,A*算法的性质(续6),推论3.1:
A*选作扩展的任一节点n,有f(n)f*(s)。
由引理2.2知在A*结束前,OPEN中存在节点n,f(n)f*(s)设此时A*选择n扩展。
如果nn,则f(n)f*(s),得证。
如果nn,由于A*选择n扩展,而不是n,所以有f(n)f(n)f*(s)。
得证。
90,A*算法的性质(续7),定理4:
设对同一个问题定义了两个A*算法A1和A2,若A2比A1有较多的启发信息,即对所有非目标节点有h2(n)h1(n),则在具有一条从s到t的路径的隐含图上,搜索结束时,由A2所扩展的每一个节点,也必定由A1所扩展,即A1扩展的节点数至少和A2一样多。
简写:
如果h2(n)h1(n)(目标节点除外),则A1扩展的节点数A2扩展的节点数,91,A*算法的性质(续7),注意:
在定理4中,评价指标是“扩展的节点数”,也就是说,同一个节点无论被扩展多少次,都只计算一次。
92,定理4的证明,使用数学归纳法,对节点的深度进行归纳
(1)当d(n)0时,即只有一个节点,显然定理成立。
(2)设d(n)k时定理成立。
(归纳假设)(3)当d(n)=k+1时,用反证法。
设存在一个深度为k1的节点n,被A2扩展,但没有被A1扩展。
而由假设,A1扩展了n的父节点,即n已经被生成了。
因此当A1结束时,n将被保留在OPEN中。
93,定理4的证明(续1),所以有:
f1(n)f*(s)即:
g1(n)+h1(n)f*(s)所以:
h1(n)f*(s)-g1(n)另一方面,由于A2扩展了n,有f2(n)f*(s)即:
h2(n)f*(s)g2(n)(A)由于d(n)=k时,A2扩展的节点A1一定扩展,有g1(n)g2(n)(因为A2的路A1均走到了)所以:
h1(n)f*(s)-g1(n)f*(s)g2(n)(B)比较A、B两式,有h1(n)h2(n),与定理条件矛盾。
故定理得证。
94,对h的评价方法,平均分叉树设共扩展了d层节点,共搜索了N个节点,则:
其中,b*称为平均分叉树。
b*越小,说明h效果越好。
实验表明,b*是一个比较稳定的常数,同一问题基本不随问题规模变化。
95,对h的评价举例,例:
8数码问题,随机产生若干初始状态。
使用h1:
d=14,N=539,b*=1.44;d=20,N=7276,b*=1.47;使用h2:
d=14,N=113,b*=1.23;d=20,N=676,b*=1.27,96,A*的复杂性,一般来说,A*的算法复杂性是指数型的,可以证明,当且仅当以下条件成立时:
abs(h(n)-h*(n)O(log(h*(n)A*的算法复杂性才是非指数型的,但是通常情况下,h与h*的差别至少是和离目标的距离成正比的。
97,3,A*算法的改进,问题的提出:
因A算法第6步对ml类节点可能要重新放回到OPEN表中,因此可能会导致多次重复扩展同一个节点,导致搜索效率下降。
98,一个例子:
s(10),s(10),A(7)B(8)C(9),A(7)s(10),B(8)C(9)G(14),A(5)C(9)G(14),C(9)G(12),B(7)G(12),A(4)G(12),G(11),B(8)s(10),A(5)B(8)s(10),C(9)A(5)s(10),B(7)C(9)s(10),A(4)B(7)C(9)s(10),99,出现多次扩展节点的原因,在前面的扩展中,并没有找到从初始节点到当前节点的最短路径,如节点A。
100,解决的途径,对h加以限制能否对h增加适当的限制,使得第一次扩展一个节点时,就找到了从s到该节点的最短路径。
对算法加以改进能否对算法加以改进,避免或减少节点的多次扩展。
101,改进的条件,可采纳性不变不多扩展节点不增加算法的复杂性,102,对h加以限制,定义:
一个启发函数h,如果对所有节点ni和nj,其中nj是ni的子节点,满足h(ni)-h(nj)c(ni,nj)h(t)=0或h(ni)c(ni,nj)+h(nj)h(t)=0则称h是单调的。
h(ni),ni,nj,h(nj),c(ni,nj),103,h单调的性质,定理5:
若h(n)是单调的,则A*扩展了节点n之后,就已经找到了到达节点n的最佳路径。
即:
当A*选n扩展时,有g(n)=g*(n)。
104,定理5的证明,设n是A*扩展的任一节点。
当ns时,定理显然成立。
下面考察ns的情况。
设P(n0=s,n1,n2,nk=n)是s到n的最佳路径P中一定有节点在CLOSED中,设P中最后一个出现在CLOSED中的节点为nj,则nj+1在OPEN中。
105,定理5的证明(续1),由单调限制条件,对P中任意节点ni有:
h(ni)C(ni,ni+1)+h(ni+1)g*(ni)+h(ni)g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最佳路径上,所以:
g*(ni+1)=g*(ni)+C(ni,ni+1)带入上式有:
g*(ni)+h(ni)g*(ni+1)+h(ni+1)从i=j到i=k-1应用上不等式,有:
g*(nj+1)+h(nj+1)g*(nk)+h(nk)即:
f(nj+1)g*(n)+h(n)注意:
(nj在CLOSED中,nj+1在OPEN中),106,定理5的证明(续2),重写上式:
f(nj+1)g*(n)+h(n)另一方面,A*选n扩展,必有:
f(n)=g(n)+h(n)f(nj+1)比较两式,有:
g(n)g*(n)但已知g*(n)是最佳路径的耗散值,所以只有:
g(n)=g*(n)。
得证。
107,h单调的性质(续),定理6:
若h(n)是单调的,则由A*所扩展的节点序列其f值是非递减的。
即f(ni)f(nj)。
108,定理6的证明,由单调限制条件,有:
h(ni)h(nj)C(ni,nj),=f(ni)-g(ni),=f(nj)-g(nj),f(ni)-g(ni)-f(nj)+g(nj)C(ni,nj),=g(ni)+C(ni,nj),f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)C(ni,nj)f(ni)-f(nj)0,得证。
109,h单调的例子,8数码问题:
h为“不在位”的将牌数1h(ni)-h(nj)=0(nj为ni的后继节点)-1h(t)=0c(ni,nj)=1满足单调的条件。
110,对算法加以改进,一些结论:
OPEN表上任以具有f(n)f*(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能导论 清华大学 人工智能 导论 课程 电子 教案