《人工智能》复习大纲.docx
- 文档编号:2464968
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:39
- 大小:788.17KB
《人工智能》复习大纲.docx
《《人工智能》复习大纲.docx》由会员分享,可在线阅读,更多相关《《人工智能》复习大纲.docx(39页珍藏版)》请在冰点文库上搜索。
《人工智能》复习大纲
《人工智能应用技术》复习大纲
一、人工智能概述
略
二、谓词公式与逻辑推理
定义2・1^(Proposition),即具有真(T)假(F)意义的陈述性语句。
定义2.2所谓个体,是指可以独立存在的某个事物。
定义2.3谓词:
由定义的谓词名、变元,共同构成了具有陈述性表达的形式化语句,称为谓词。
一个谓词可以有n(其中n=0,1,2,……)个变元,并称之为n元谓词。
定义2.3谓词中包含个体或变元的数目,称为谓词的元或谓词的目。
定义2.4谓词表达形式中所包容相叠加的含义层次数数目,称为谓词的阶。
例2-2比较下列谓词或谓词形式的命题:
©LIKE(John,mary);©ROBOT(John);
©ROBOT(mary);®ADDQ(x,y,z)。
试解释具体含义,并指出它们各是几元谓词。
解:
上述谓词①②③意即“机器人约翰喜欢玛丽”;②和③都只有一个个体,称为一元谓词;相应①则称为二元谓词;④表示为表达式“x+y二z”,其中包含有3个变元,故称为三元谓词。
依此类推,可推出关于n元谓词的概念。
例2-3为了说明谓词的阶,我们来比较下列谓词形式的命题:
1LIFELESS(outerstars);外星球没有智能生命。
2INCORRECT(1辻心ss(outer-stars)说“外星球没有智能生命”是不确切的。
解:
在上述谓词形式的命题中,谓词①只有一层含义,称为一阶谓词;谓词②在前一层含义基础上,乂增加了一层新意,共有二层含义。
故把谓词②称为二阶谓词。
依此类推,可推出关于n阶谓词的概念。
注意:
在谓词逻辑演算中,最重要的有三大类:
即:
命题逻辑演算、一阶谓词逻辑演算和二阶谓词演算。
命题逻辑表示比较简单,只能表达具体固定的情况,
命题是谓词逻辑特殊事例的生动描述,
谓词逻辑可以灵活表现多种或变化的情况;
谓词表达是命题逻辑的抽象与推广。
总的看来,命题和谓词的知识表示形式可以相互转换,而谓词比命题有更强的表达能力。
显而易见,谓词是一种描述个体群之间的相互关系、性质及其逻辑结构的数学表示。
人们把采用这种表示的运算,又称为谓词逻辑。
比较起来:
命题逻辑演算太简单,只能解决具体容易的问题;二阶谓词演算乂太复杂,以至迄今为止,尚未找到最根本有效的算法。
因此,在人工智能中,L1前使用最多的还是一阶谓词逻辑演算。
■表2-1连接词定义真值表
P
Q
PVQ
PAQ
PfQ
P3
F
F
T
F
F
T
T
F
T
T
T
F
T?
F
T
F
F
T
F
F
F
T
T
F
T
T
T
T
2.1.3命题和谓词逻辑举例
例:
⑴小张既聪明,又勤奋,所以他的学习成绩一直很好。
P:
小张聪明
0:
小张勤奋
斤:
小张学习成绩一直很好
■(PKQ)7
⑵小王总是在图书馆看书,除非他病了或图书馆不开门。
P:
小王病了
0:
图书馆开门
R:
小王在图书馆看书
(PVQ)oR
⑴若张先生是小张的父亲,则小张是王太太的儿子。
解:
先设定谓词,再设定变元,并将变元代之以常量,用连接词运算符连接并加以描述:
设定谓词:
FATHER(x,y):
x是y的父亲
SON(y,w):
y是w的儿子
常量:
Z表示张先生;mz表示小张;wtt——王太太
则可描述为:
FATHER(z,mz)—SON(mz,wtt)
(2)若x是小张的父亲,且y是小张的兄弟,则x也是y的父亲。
解:
先设定谓词,再设定变元,并将变元代之以常量,用连接词运算符连接并加以描述:
设定谓词:
FATHER(x,y):
x是y的父亲
BROTHER(y,w):
y是w的兄弟
常量:
mz表示小张
则可描述为:
FATHER(x,mz)/\BROTHER(y,mz)
-FATHER(x,y)
(3)水在那遥远的地方,有位好姑娘,人们走过她的身旁,都要回头留恋地张望。
解:
(Elx){»姑娘(x)/\居住的地方(z,x)
/\遥远的(z)A(Vy)[人(y)/\行走经过(y,z)
一回头留恋地张望(y)]}
例4.1设已知下述事实:
®A;②B;③A~C;®BAC—D;⑤D~Q・求证:
Q为真。
证明:
(P规则及假言推理)
(引入合取)
(T规则及假言推理)
(T规则及假言推理)
IA,A-CdC
B,CnBAC
BAC,BAC-D=>D
D,D-Q亠Q
•••Q为真(证毕)例4.2设已知如下事实:
(1)凡是容易的课程小王(Wang)都喜欢;
(2)C班的课程都是容易的;
(3)ds是C班的一门课程.求证:
小王喜欢ds这门课程.证明:
首先定义谓词:
EASY(x)——x是容易的课程;
LIKE(x,y)x喜欢y课程;
C(X)x是C班的一门课程.
已知:
EASY(x)-LIKE(Wang,x)①
(Vx)(C(x)-EASY(x))②
C(ds)③
求证:
LIKE(Wang,ds)④
证明:
可应用推理规则进行推理证明。
•••由②,得(Vx)(C(x)-EASY(x))
・・・C(y)fEASY(y)⑤(全称固化)
由③⑤,得C(ds),C(y)-EASY(y)=>EASY(ds)
⑥(P规则及假言推理)
•••EASY(ds),EASY(x)-LIKE(Wang,x)LIKE(Wang,ds)(T规则及假言推理)
即小王喜欢ds这门课程。
(证毕)
例4.3设已知
(1)凡是人喜欢吃的东西狗也喜欢;
(2)jasper是一条狗;
(3)有人喜欢啃骨头.
求证:
jasper喜欢啃骨头.
证明:
首先定义谓词:
DOG(x)x是狗;xW{jasper,狗,…}
LIKEEAT(y,z)——y喜欢吃(啃)z;yG{jasper,人,…}zW{bones,肉,鱼,…}
X)①②③
则得已知条件:
(Vx)(Vz)LIKEEAT(人,z)ADOGfLIKEEAT(x,z)DOG(jasper)LIKEEAT(人,bones)求证:
LIKEEAT(jasper,bones)
证明:
②代入①得(Vz)LIKEEAT(人,z)ADOG(jasper)
—LIKEEAT(jasper,z)(全称固化)④
3代入④得LIKEEAT(人,bones)ADOG(jasper)LIKEEAT(jasper,bones)⑤
由②③为真,得LIKEEAT(人,bones)ADOG(jasper)二T(引入合取词)⑥
由⑥⑤为真,得LIKEEAT(jasper,bones)二T
(P规则及假言推理)
即jasper喜欢啃骨头.(证毕)
谓词公式概念复习与扩充:
使用连接词和量词,把若干谓词连接组合在一起,就得到了谓词逻辑公式(PLF:
PredicateLogicFormula)的表达。
下面我们给出谓词公式的相关各种概念与定义。
定义2.5仅能表达单一意义且不可再细划分的简单命题称为原子命题。
例如,一阶零元(目)命题、一阶一元命题、一阶二元命题等都是原子命题。
定义2.6用连接词或者量词把若干原子命题联结组合在一起,就得到了命题公式(PF:
PropositionFormula),又称之为命题合式公式。
定义2.7采用参量变元来替代命题合式公式中的常量,就得到了原子谓词公式,乂称之为谓词合式公式(PWFF:
PredicateWell-FormedFormula),简称合式公式或WFF。
三、状态空间表示法
例1-1设有三枚钱币,分别处在“正”>“反”>“正”状态。
每次只能且必须翻一枚钱币。
问连翻三次后能否达到三枚全朝上或全朝下的状态?
首先应把问题形式化。
设正面表示为h反面表示为0,可引入一个三元组沪(g,JQ来描述这三枚钱币的状态,每个a的取值为[0,1],因此共有2彳二8种不同的状态。
这8种状态列举如下:
Q)=(O、O,O);Q{=(0,0,1);Q2=(0,1,0):
Q、=(0丄1):
=(1,0,0);@=(匕0,1);Q=(1丄0);Q7=(1丄1);
于是问题就变为如图1-4所示。
(0,0,0)
图1-4例1-1的问题示总
接着应找岀所有能改变状态的操作。
这里翻动一枚钱币就称为一种操作,则共有3种操作,即fb,泊其中,◎表示将钱币G翻转一次,b表示将钱币翻转一次,c表示将钱币G翻转一次。
如图1-5所示是此问题的全部状态空间图。
图1-5三枚钱币的状态空间图
图1-5中结点表示状态,有向边表示操作,双向箭头表示两个状态在同一操作下是可逆的,这样可以为三次操作提供方便。
从图1-5中可以看出,从@二@出发,不可能通过三次操作到达a二这说明从@到q之间没有所要求的解;而从@出发到达@二0有7种操作序列,因而有7个解,它们是朋aba,baa^bbb»bcc9cbc和ccbo例6-1设有分别由开关控制的一字排开的3盏信号灯,处在“亮、暗、亮”的初始状态。
每次操作允许并必须扳动一只开关,问:
如果连扳三次开关后,是否可以出现错“亮.亮.亮”或“暗.暗、暗”的状态?
解:
首先将该问题形式化:
设开关“off”灯为“暗”,以0表示;开关“on”灯为“亮”,以1表示;再分别用A、B、C标识3盏灯亮或暗的状态。
这样,可引入一三元数组Sk二(A,B,C)来描述这3盏信号灯的总状态。
全部可能的状态计有8种:
S0二(0,0,0),S1二(0,0,1),S2二(0,1,0),S3二(0,1,1),
S4=(1,0,0),S5=(1,0,1),S6=(1,1,0),S7=(1,1,1)・
这里,初始状态一个:
S={S5}={(1,0,1)):
目标状态有2个:
G二{SO,S7}={(0,0,0),(1,1,1))
状态的操作数,共3个,F={a,b,c},分别表示把各灯开关扳动一次:
问题的状态空间可写成<{S5),{a,b,c},{SO,S7}〉.
教材中图6-3表示了全部可能的状态及其相互关系。
其中S5是初始状态,S0和S7都是!
_!
标状态。
从图中我们可以清楚地看出:
从S5经过三步搜索不可能恰好到达S0,即不存在从S5到达SO的解;但从S5出发搜索,到达S7的路径有7条,它们的动作序列分别为ddb.aba>baa>bbb、bcc>cbc和ccb等,共有七组解。
山上述利用状态空间图求解的举例,对具体问题搜索求解可总结为如下的思路和步骤:
(1)设定状态变量及确定值域;
(2)确定状态组,分别列出初始状态集和U标状态集;
(3)定义并确定操作集;
(4)估计全部状态空间数,并尽可能列出全部状态空间或予以描述之;
(5)当状态数量不是很大时,按问题的有序元组画出状态空间图,依照状态空间图搜索求解。
例6-2传教士和野人问题(TheMissionariesandCannibalsProblem)。
在河的左岸有三个传教士、一条船和三个野人,传教士们想用这条船将所有的成员都运过河去,但是受到以下条件的限制:
①传教士和野人都会划船,但船一次最多只能装运两个;②在任何岸边野人数目都不得超过传教士,否则传教士就会遭遇危险:
被野人攻击甚至被吃掉。
此外,假定野人会服从任何一种过河安排,试规划出一个确保全部成员安全过河的计划。
例1-2修道士和野人问题。
在河的左岸有3个修道士.3个野人和1条船,现在要渡河到右岸,但有如下限制条件:
(1)船最多坐2人,修道士和野人都会划船。
(2)在任何岸边野人人数都不能超过修道士人数,否则修道士就会被吃掉。
请规划出一个安全的渡河方案。
解:
我们按上述步骤来进行求解分析。
(1)设定状态变量及确定值域。
为了建立这个问题的状态空间,设左岸传教士数为m,则
m二{0,1,2,3};
对应右岸的传教士数为3-m;左岸的野人数为c,则有
c={0,1,2,3):
对应右岸野人数为3-c:
左岸船数为b,故乂有b二{0,1},右岸的船数为1—b・
(2)确定状态组,分别列出初始状态集和目标状态集。
问题的状态可以用一个三元数组来描述,以左岸的状态来标记,即
Sk=(m,c,b),
右岸的状态可以不必标出。
初始状态一个:
SO=(3,3,1),初始状态表示全部成员在河的左岸;
目标状态也只一个:
Sg二(0,0,0),表示全部成员从河左岸渡河完毕。
(3)定义并确定操作集。
仍然以河的左岸为基点来考虑,把船从左岸划向右岸定义为Fij操作。
其中,第一下标i表示船载的传教士数,第二下标j表示船载的野人数;同理,从右岸将船划回左岸称之为Qij操作,下标的定义同前。
则共有10种操作,操作集为
F={P01,PIO,Pll,P02,P20,Q01,Q10,Qll,Q02,Q20}
(4)估计全部的状态空间数,并尽可能列出全部的状态空间或予以描述之。
在这个问题世界中,S0=(3,3,1)为初始状态,S31=Sg=(0,0,0)为目标状态。
全部的可能状态共有32个,如表6-1所示。
表6-1传教士和野人问题的全部可能状态
状态
m,c,b
状态
m,c,b
状态
m,c,b
状态
m,c,b
so
331
S8
131
S16
330
S24
130
S1
321
S9
121
S17
320
S25
120
S2
311
S10
111
S18
310
S26
110
S3
301
Sil
101
S19
300
S27
100
S4
231
S12
031
S20
230
S28
030
S5
221
S13
021
S21
220
S29
020
S6
211
S14
011
S22
210
S30
010
S7
201
S15
001
S23
200
S31
000
注意:
按题U规定条件,应划去非法状态,从而加快搜索效率。
1)首先可以划去左岸边野人数口超过传教士的情况,即S4、S8、S9、S20、S24、S25等6种状态是不合法的;
2)应划去右岸边野人数H超过修道士的情况,即S6、S7、Sil.S22、S23、S27等情况;
3)应划去4种不可能出现状态:
划去S15和S16——船不可能停鼎在无人的岸边;划去S3——传教士不可能在数量占优势的野人眼皮底下把船安全地划回来;划去S28——传教士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。
可见,在状态空间中,真正符合题目规定条件的只有16个合理状态。
(5)当状态数量不是很大时,按问题的有序元组画出状态空间图,依照状态空间图搜索求解。
根据上述分析,共有16个合法状态和允许的操作,可以划出传教士和食人者问题的状态空间图,如图6-4所示。
S21SmS5
图6-4传教士和野人问题的状态空间图:
四、搜索技术
基本搜索策略主要分为四种类型:
即
1.宽度优先搜索;
2.深度优先搜索;
3.有界搜索;
4.代价推进搜索。
2.1宽度优先搜索(Breadth-firstSearch)
又称为广度优先搜索或横向优先搜索,顾名思义.即搜索任务是按照横向逐步扩展向前推进
图6-10宽度优先搜索过程之一
而完成的。
为了用算法来实现其搜索过程,需要预先建立两个表,分别称为OPE\表及CLOSED表。
OPEN表:
只用来登记存放新生成并待扩展的节点,不保留已扩展及已被考察的节点;
CLOSED表:
用来存放已扩展并已被考察的节点,即登记已经完成的搜索路径。
一般对于不同的搜索策略,在OPEN表中节点排列的顺序是不同的。
这里约定,OPEN表中按节点生成及进入的先后的顺序排列,先生成的节点排在前•面,后生成的节点排在后面,并实行先进先出(FIFO)的算法来进行搜索。
■宽度优先搜索过程可用图6-11的工作流程来表示。
其步骤为:
宽度优先搜索流程示意图
(1)把初始节点SO放入OPEN表;
(2)如果OPEN表为空,则问题无解,退出。
(3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表;
(4)考察节点n是否为L1标节点。
若是,则求得了问题的解,退出。
(5)若节点n不可扩展,则转第
(2)步。
(6)扩展节点n,将其子节点放入OPEN表,并为每一个子节点都配置指向父节点的指针,然后转第
(2)步
其得到的搜索的路径为:
SOfSlfS2fSllfS12—S21—S22—Sill—S112—S113—S121—S122(Sg.)
■算法特点:
显然,宽度优先搜索法是一种遵循规则的盲LI性搜索,它遍访了口标节点前的每一层次每一个节点,即检查了U标节点前的全部的状态空间点,只要问题有解,它就能最终找到解,且最先得到的将是最小深度的解。
可见,宽度优先搜索法很可靠。
但是,当LI标节点距离初始节点较远时将会产生许多无用的中间节点。
因此,速度慢,效率低,尤其对于庞大的状态空间实用价值差。
2.2深度优先搜索(Depth-firstSearch)
又称为纵向优先搜索•顾名思义.即搜索任务是按照纵深方向■逐级地向下跨越推进而完成的。
深度优先搜索的基本方法为:
从根节点so开始,始终沿着纵深方向搜索,总是在其后继子节点中选择一节点来考察。
若到达目标节点Sg,则搜索成功;若不是目标节点,则再在该节点的后继子节点中选一考察,一直如此向下搜索,直到搜索找到目标节点才停下来。
若到达某个子节点时,发现该节点既不是目标节点又不能继续扩展,就选择其兄弟节点再进行考察。
依此类推,直到找到目标节点或全部节点考察完毕,搜索过程才可以终止或结束。
例6-5如图6-14所示.设法使用深度优先捜索过程算法.寻找出从SO到达Sg的搜索路径。
解:
假设图中所标记的是全部的搜索树。
我们采用的一种深度优先搜索过程算法是:
发生器函数Q(x)按照每一层节点从左至右的优先级,并按照“最晚生成的节点优先扩展”并优先考察搜索的原则。
这里,就可获得一种先扩展(包括括号内、外的节点),再既而完成考察与搜索(不用括号的节点),其路径为:
SOT(S1)S2T(S21)S22T(S221)S222T
(S2221)S2222TS2221TS221T(S2211)S2212二Sg・
针对教材中图6-12所示的垂排九宫问题,按照上述“最晚生成的节点优先扩展”并优先考察搜索的原则,如图6-15所示,则得到的搜索路径是:
SO二1T5T9T13T21T22T,这里还只是搜索树的一部分,尚未到达目标Sg;而沿着分枝SO二1T3T6T10T14二Sg路径的深度优先搜索,却可以高效率到达目标节点。
可见深度优先搜索的效率将随着选择路径的不同而具有较大的区别。
看起来深度优先搜索算法流程与宽度优先搜索算法过程几乎完全相同。
其主要区别在于采用的OPEN表结构不同:
深度优先搜索OPEN表,实行的是后进先出(LIFO)的算法进行搜索;这与宽度优先搜索算法实行先进先出(FIFO)的算法不同。
深度优先捜索的特点:
方式灵活.规则易于实现,对于有限状态空间并有解时,必能找到解。
例如,当搜索到某个分支时,若目标节点恰好在此分支上,则可较快地得到解。
故在一定条件下,可实现较高求解效率。
但是,在深度优先搜索中,一旦搜索进入某个分支,就将沿着该分支一直向下搜索。
这时,如果目标节点不在此分支上,而该分支又是一个无穷分支,则就不可能得到解。
可见,深度优先捜索算法不完备.风险大■易于掉入陷阱。
因此,要使深度优先搜索算法可用,必须加以改造。
2.3有界搜索
为了避免深度优先捜索过程陷入无穷分支的死循环.人们乂提出了有界深度优先搜索算法基本思想:
设定一个搜索深度的界限dm,当搜索深度达到dm,而尚未出现□标节点时,可回朔换一个分支进行搜索,直到dm的深度内所有分支节点搜索完毕。
有界深度优先搜索过程可概括为:
(1)把初始节点SO放入OPEN表中,置SO的深度d(SO)=O;
(2)如果OPEN表为空,则问题无解,退出。
(3)把OPEN表中的第一个节点(记为节点Sn)取出放入CLOSED表;
(4)考察节点Sn是否为目标节点。
若是,则求得了问题的解,退出。
(5)如果节点Sn的深度d(Sn)二dm或节点Sn不可扩展,则转到第
(2)步;
(6)扩展节点Sn,将其子节点放入OPEN表的首部,并为其配置指向父节点的指针,然后转到第
(2)步。
基本搜索策略的局限性及其特点
概括起来,广度优先搜索、深度优先搜索、有界深度优先搜索和代价推进搜索法等,它们的局限性及其特点为:
①基本搜索策略普遍适用于树状问题求解,控制性知识简单,容易编程在计算机上实现。
但是,它表现出来的缺点也很突出:
一般必须知道问题的全部状态空间,搜索效果差,求解能力弱,故常被称为弱方法。
2它们都是依据某种固定规则运行的搜索,均属于非启发的强力搜索,没有表现出智能搜索的活跃性与灵活性。
也就是说,问题搜索树的生成、扩展以及节点接受考察的次序等,都是由生硬死板的搜索方法决定的,而不山具体问题状态信息引导与经验分析来决定;
3山于基本搜索策略疏忽了对给定问题的特有知识的分析,没有充分考虑所要求解问题的自身发展规律和特性,搜索完全是按事先确定好的固定排序来进行的,这是一种穷尽遍历的大海捞针式的策略,没有任何启发式信息引导,往往使得实际搜索效率很低,故乂被称为盲U搜索。
2.4启发式搜索
所谓启发式捜索(HeuristicSearch)策略,即利用与问题解有关的启发信息来作引导的捜索策略。
搜索效穆及其评价:
有一种比较直观的评价搜索效率的方法,其定义公式为:
P=L/T(6-4)
L是从根节点到达目标节点的深度;T是在整个搜索过程中产生节点总数(不计根节点),因此,这里P反映的是朝着目标搜索时的搜索宽度。
讨论:
搜索效率定义公式为:
P二L/T
1一般情况下,PW1因为总有T^L;
2)当L二T时,则P=L/T=b表示搜索过程中每次只生成一个节点,并且它恰好是解路径上的节点,表示了一种以单枝延伸的搜索树。
这时,启发能力最强,效率最高,即所扩展的每一个节点都落在最佳路径上,称为最佳搜索。
3当P=L/T«1,儿近于零,没有任何控制性知识作依据,搜索中的每一步都是完全随意而进行的,称为随机搜索;
通常搜索总是介于0〜1之间。
因此,为了快速地找到问题的解,总是使搜索尽可能利用启发信息,努力使搜索路径的每一步都尽可能与最佳搜索路径重合一致,以便实现更高的搜索求解效率。
启发式捜索的主要特点是:
山于充分考虑到问题求解所应用到的各种启发信息及知识,包括利用常识性推理和专家经验等信息与知识,启发式搜索能够动态
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 复习 大纲
![提示](https://static.bingdoc.com/images/bang_tan.gif)