人工智能及其应用

《人工智能及其应用》由会员分享，可在线阅读，更多相关《人工智能及其应用（97页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,‹#›,人工智能及其应用,,,,,制作人：王思文,,刘玉奇,,于斌,,第,1,章　绪论,,1,、重点掌握,人工智能的几种定义,。,2,、掌握目前,人工智能的三个主要学派,及 其认知观。,3,、一般了解人工智能的主要研究范围和 应用领域。,,定义,2,人工智能,(,学科,),人工智能,(,学科,),是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期主要目标在于研究用机器来模仿和执行人脑的某些智力功能，并开发相关理论和技术。,定义,3,人工智能,(,能力,),人工智能,(,能力,),是智能机器所执行

2、的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。,,人工智能的三大学派及其认知观：,(1),符号主义 认为人工智能起源于数理逻辑。,(2),连接主义 认为人工智能起源于仿生学，特别是对人脑模型的研究。,(3),行为主义 认为人工智能起源于控制论。,,第,2,章　知识表示方法,重点掌握用状态空间法、问题归约法、谓词逻辑法、语义网络法、框架表示法来描述问题，解决问题；,2.1,状态空间法,,许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空

3、间的问题表示和求解方法就是状态空间法，它是以状态和算符,(operator),为基础来表示和求解问题的。,,,2.1,状态空间法,状态空间法三要点,,(1),状态,（,state,）,：表示问题解法中每一步问题状况的数据结构；,,(2),算符,（,operator,）：把问题从一种状态变换为另一种状态的手段；,,(3),状态空间方法,：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。,2.1,状态空间法,由上可知，对一个问题的状态描述，必须确定,3,件事：,(1),该状态描述方式，特别是初始状态描述；,(2),操作符集合及其对状态描述的作用；,(3),目标状态描述的

4、特性。,,,例,2,：,(,分油问题,),有,A,、,B,、,C,三个不带刻度的瓶子，分别能装,8kg, 5kg,和,3kg,油。如果,A,瓶装满油，,B,和,C,是空瓶，怎样操作三个瓶，使,A,中的油平分两份？,(,假设分油过程中不耗油,),,解：第,一,一步：,定,定义,问,问题状,态,态的描,述,述形式,：,：,设,S,k,=(b,c),表示,B,瓶和,C,瓶中的,油,油量的,状,状态。,其中：,b,表示,B,瓶中的,油,油量。,c,表示,C,瓶中的,油,油量。,初始状,态,态集：,S={(0,0)},目标状,态,态集：,G={(4,0)},,第二步,：,： 定,义,义操作,符,符：,操

5、作：,把,把瓶子,倒,倒满油,，,，或把,瓶,瓶子的,油,油倒空,。,。,f1,：从,A,瓶往,B,瓶倒油,，,，把,B,瓶倒满,。,。,f2,：从,C,瓶往,B,瓶倒油,，,，把,B,瓶倒满,。,。,f3,：从,A,瓶往,C,瓶倒油,，,，把,C,瓶倒满,。,。,f4,：从,B,瓶往,C,瓶倒油,，,，把,C,瓶倒满,。,。,f5,：从,B,瓶往,A,瓶倒油,，,，把,B,瓶倒空,。,。,f6,：从,B,瓶往,C,瓶倒油,，,，把,B,瓶倒空,。,。,f7,：从,C,瓶往,A,瓶倒油,，,，把,C,瓶倒空,。,。,f8,：从,C,瓶往,B,瓶倒油,，,，把,C,瓶倒空,。,。,第三步,：,：

6、 求,解,解过程,：,：,0,3,3,0,2,3,f1,f1,0,0,5,3,1,3,1,0,0,1,5,1,3,3,4,0,4,3,5,2,5,3,0,0,0,2,0,3,2,0,5,0,f1,f3,f4,f7,f8,f6,f5,f3,f1,f4,f7,f5,f3,f2,f8,f3,f8,f3,f2,f5,f8,f3,f8,f7,f7,f6,f1,f4,f7,f4,f5,f1,f7,f1,f1,f1,f7,f5,f5,f7,f5,f6,f7,f5,f1,f3,f3,,f1,：从,A,瓶往,B,瓶倒油,，,，,把,B,瓶倒满,。,。,,f2,：从,C,瓶往,B,瓶倒油,，,，,把,B,瓶倒满,

7、。,。,,f3,：从,A,瓶往,C,瓶倒油,，,，,把,C,瓶倒满,。,。,,f4,：从,B,瓶往,C,瓶倒油,，,，,把,C,瓶倒满,。,。,,f5,：从,B,瓶往,A,瓶倒油,，,，,把,B,瓶倒空,。,。,,f6,：从,B,瓶往,C,瓶倒油，,把,B,瓶倒空。,,f7,：从,C,瓶往,A,瓶倒油，,把,C,瓶倒空。,,f8,：从,C,瓶往,B,瓶倒油，,把,C,瓶倒空,。,由上述状,态,态空间图,，,，可见从,初,初始状态,(0,1),到目标状,态,态,(4,0),的任何一,条,条通路都,是,是问题的,一,一个解。,其,其中：,{f1,f4,f7,f6,f1,f4,f7},是算符最,少,

8、少的解之,一,一。,例：设有,3,个传教士,和,和,3,个野人来,到,到河边，,打,打算乘一,只,只船从右,岸,岸渡到左,岸,岸去。该,船,船的负载,能,能力为两,人,人。在任,何,何时候，,如,如果野人,人,人数超过,传,传教士人,数,数，那么,野,野人就会,把,把传教士,吃,吃掉。他,们,们怎样才,能,能用这条,船,船安全地,把,把所有人,都,都渡过河,去,去？,,,解：第一,步,步： 定,义,义问题状,态,态的描述,形,形式：,设,S,k,=(M,C,B),表示传教,士,士和野人,在,在河右岸,的,的状态。,其中：,M,表示传教,士,士在右岸,的,的人数。,C,表示野人,在,在右岸的,人

9、,人数。,B,用来表示,船,船是不是,在,在右岸。,(B=1,表示在右,岸,岸，,B=0,表示在左,岸,岸,),。,初始状态,集,集：,S={(3,3,1)},目标状态,集,集：,G={(0,0,0)},第二步：,定,定义算符,。,。,算符,R(i,j),表示划船,将,将,i,个传教士,和,和,j,个野人送,到,到左岸的,操,操作。,算符,L(i,j),表示划船,从,从左岸将,i,个传教士,和,和,j,个野人带,回,回右岸的,操,操作。,由于过河,的,的船每次,最,最多载两,个,个人，所,以,以,i+j≤2,。这样定,义,义的算符,集,集,F,中只可能,有,有如下,10,个算符。,F,：,R(

10、1,0),R(2,0),R(1,1),R(0,1),R(0,2),L(1,0),L(2,0),L(1,1),L(0,1),L(0,2),第三步：,求,求解过程,。,。,1,1,0,2,2,1,3,1,1,0,2,0,3,0,0,R(2,0),L(2,0),R(1,1),L(1,1),L(0,1),R(0,1),L(2,0),R(2,0),2,2,0,3,3,1,3,2,1,3,2,0,3,1,0,L(0,2),R(0,2),R(0,1),L(0,1),L(1,0),R(1,0),L(0,1),R(0,1),L(1,1),R(1,1),L(0,2),R(0,2),1,1,1,0,0,0,0,1,

11、0,0,1,1,0,2,1,R(0,1),L(1,0),L(0,1),R(0,1),R(1,0),L(1,0),R(0,1),L(0,1),R(1,1),L(1,1),R(0,2),L(0,2),0,3,1,R(0,2),L(0,2),由上述状,态,态空间图,，,，可见从,初,初始状态,(3,3,1),到目标状,态,态,(0,0,0),的任何一,条,条通路都,是,是问题的,一,一个解。,其中：,{R(1,1),L(1,0),R(0,2),L(0,1),R(2,0),L(1,1),R(2,0),L(0,1),R(0,2),L(1,0),R(1,1)},是算符最,少,少的解之,一,一。,,2.2,

12、问题归约,法,法,问题归约,法,法的概念,已知问题,的,的描述，,通,通过一系,列,列变换把,此,此问题最,终,终变为一,个,个子问题,集,集合；这,些,些子问题,的,的解可以,直,直接得到,，,，从而解,决,决了初始,问,问题。,该方法也,就,就是从目,标,标,(,要解决的,问,问题,),出发逆向,推,推理，建,立,立子问题,以,以及子问,题,题的子问,题,题，直至,最,最后把初,始,始问题归,约,约为一个,平,平凡的本,原,原问题集,合,合。这就,是,是问题归,约,约的实质,。,。,,2.2,问题归约,法,法,问题归约,法,法的组成,部,部分,（,1,）一个初,始,始问题描,述,述；,（,

13、2,）一套把,问,问题变换,为,为子问题,的,的操作符,；,；,（,3,）一套本,原,原问题描,述,述。,2.3,谓词逻辑,法,法,一阶谓词,逻,逻辑表示,法,法适于表,示,示确定性,的,的知识。,它,它具有自,然,然性、精,确,确性、严,密,密性及易,实,实现等特,点,点。,2.3,谓词逻辑,法,法,用一阶谓,词,词逻辑法,表,表示知识,的,的步骤如,下,下：,（,1,）定义谓,词,词及个体,，,，确定每,个,个谓词及,个,个体的确,切,切含义。,（,2,）根据所,要,要表达的,事,事物或概,念,念，为每,个,个谓词中,的,的变元赋,以,以特定的,值,值。,（,3,）根据所,要,要表达的,知

14、,知识的语,义,义，用适,当,当的连接,符,符号将各,个,个谓词连,接,接起来，,形,形成谓词,公,公式。,例,1,：设有下,列,列事实性,知,知识：,张晓辉是,一,一名计算,机,机系的学,生,生，但他,不,不喜欢编,程,程序。李,晓,晓鹏比他,父,父亲长得,高,高。,请用谓词,公,公式表示,这,这些知识,。,。,（,1,）定义谓,词,词及个体,。,。,Computer(x):x,是计算机,系,系的学生,。,。,Like(x,y):x,喜欢,y,。,Higher(x,y):x,比,y,长得高。,这里涉及,的,的个体有,：,：张晓辉,(zhangxh),,编程序,(programming),,李

15、晓鹏,(lixp),，以及函,数,数,father(lixp),表示李晓,鹏,鹏的父亲,。,。,第二步：,将,将这些个,体,体代入谓,词,词中，得,到,到,Computer(zhangxh), ~Like(zhangxh, programming),Higher(lixp,father(lixp)),,第三步：,根,根据语义,，,，用逻辑,联,联结词将,它,它们联结,起,起来，就,得,得到了表,示,示上述知,识,识的谓词,公,公式。,Computer(zhangxh)∧ ~Like(zhangxh, programming),Higher(lixp,father(lixp)),,例,2,：,设

16、有下列,语,语句，请,用,用相应的,谓,谓词公式,把,把它们表,示,示出来：,（,1,）人人爱,劳,劳动。,（,2,）自然数,都,都是大于,零,零的整数,。,。,（,3,）西安市,的,的夏天既,干,干燥又炎,热,热。,（,4,）喜欢读,《,三国演义,》,的人必读,《,水浒,》,。,（,5,）有的人,喜,喜欢梅花,，,，有的人,喜,喜欢菊花,，,，有的人,既,既喜欢梅,花,花又喜欢,菊,菊花。,（,6,）他每,天,天下午,都,都去打,篮,篮球。,解：,（,1,）人人,爱,爱劳动,。,。,定义谓,词,词如下,：,：,Man(x):x,是人。,Love(x,y):x,爱,y,。,（,x)(Man(

17、x),→,→Love(x,,劳动）,）,）,,,,（,2,）自然,数,数都是,大,大于等,于,于零的,整,整数。,定义谓,词,词如下,：,：,N(x):x,是自然,数,数。,I(x):x,是整数,。,。,GZ(x):x,大于等,于,于零。,（,x)(N(x)→(GZ(x,）∧,I(x)),）,(3),西安市,的,的夏天,既,既干燥,又,又炎热,。,。,定义谓,词,词：,SUMMER(x):x,处于夏,天,天。,DRY(x):x,很干燥,。,。,HOT(x):x,很炎热,。,。,SUMMER(Xi,’,’an)→DRY(Xi’an),∧,∧HOT(Xi’an),,（,4,）喜欢,读,读,《,三

18、国演,义,义,》,的人必,读,读,《,水浒,》,。,定,定,义,义谓词,：,：,MAN(x),：,x,是人。,LIKE(x,y),：,x,喜欢读,y,。,(,x,)(MAN(x)∧LIKE(x, 《SANGUOYANYI》),→LIKE(x,,《,《SHUIHU》)),,（,5,）有的,人,人喜欢,梅,梅花，,有,有的人,喜,喜欢菊,花,花，有,的,的人既,喜,喜欢梅,花,花又喜,欢,欢菊花,。,。,定义谓,词,词：,MAN(x):x,是人。,LIKE(x,y): x,喜欢,y,。,Meihua,表示梅,花,花，,Juhua,表示菊,花,花，,(,x)(MAN(x),∧,LIKE(x,,M

19、eihua))∧,(,y)(MAN(y),∧,LIKE(y,,Juhua))∧,(,z)(MAN(z),∧,(LIKE(z,,Meihua),∧LIKE(z,Juhua))),,（,6,）他每,天,天下午,都,都去打,篮,篮球。,定义谓,词,词及个,体,体：,设,TIME(x):x,是下午,。,。,PLAY(x,y):x,去打,y,，,Liming,表示李,明,明，,Basketball,表示足,球,球，则,:,（,,x,）,TIME(x),,PLAY(Liming,Basketball),2.4,语义网,络,络法,语义网,络,络是,1968,年,J.R.Quillian,在研究,人,

20、人类联,想,想记忆,时,时提出,的,的心理,学,学模型,。,。,,2.4,语义网,络,络法,语义网,络,络的概,念,念,语义网,络,络是通,过,过概念,及,及其语,义,义关系,来,来表示,知,知识的,一,一种结,构,构化网,络,络图，,它,它由节,点,点和弧,线,线或链,线,线组成,，,，节点,用,用来表,示,示各种,概,概念、,事,事物、,属,属性、,情,情况、,动,动作、,状,状态等,，,，每个,节,节点可,以,以带有,若,若干个,属,属性，,以,以表征,其,其所代,表,表的对,象,象的特,性,性。弧,线,线用于,表,表示节,点,点间的,关,关系，,其,其上的,标,标注则,表,表示被,连,

21、连接的,两,两个节,点,点间的,某,某种语,义,义联系,或,或语义,关,关系。,,2.4,语义网,络,络法,语义网,络,络表示,知,知识的,方,方法及,步,步骤,（,a,）确定,问,问题中,的,的所有,对,对象以,及,及各对,象,象的属,性,性。,（,b,）确定,所,所讨论,对,对象间,的,的关系,。,。,（,c,）语义,网,网络中,，,，如果,节,节点间,的,的联系,是,是,ISA/AKO,，则下,层,层节点,对,对上层,节,节点的,属,属性具,有,有继承,性,性。整,理,理同一,层,层节点,的,的共同,属,属性，,并,并抽出,这,这些属,性,性，加,入,入上层,节,节点中,，,，以免,造,

22、造成属,性,性信息,的,的冗余,。,。,,（,d,）将各,对,对象作,为,为语义,网,网络的,一,一个节,点,点，而,各,各对象,间,间的关,系,系作为,网,网络中,各,各节点,间,间的弧,，,，连接,形,形成语,义,义网络,。,。节点,可,可代表,一,一个事,物,物或一,个,个具体,概,概念，,也,也可代,表,表某种,情,情况、,事,事件或,某,某一动,作,作。当,节,节点表,示,示某种,事,事件或,某,某一动,作,作时，,可,可以从,该,该节点,引,引出一,组,组向外,的,的弧，,用,用于指,出,出事件,的,的因果,或,或动作,的,的主体,及,及客体,。,。,例,1,、用一,个,个语义,网

23、,网络表,示,示下列,命,命题。,树和草,都,都是植,物,物；,树和草,是,是有根,有,有叶的,；,；,水草是,草,草，且,长,长在水,中,中；,果树是,树,树，且,会,会结果,；,；,苹果树,是,是果树,中,中的一,种,种，它,结,结苹果,。,。,分析：,问题涉,及,及的对,象,象有：,植物、,树,树、草,、,、水草,、,、果树,、,、苹果,树,树,各对象,的,的属性,分,分别为,：,：,树和草,的,的属性,：,：有根,、,、有叶,；,；,水草的,属,属性：,长,长在水,中,中；,果树的,属,属性：,会,会结果,；,；,苹果树,的,的属性,：,：结苹,果,果。,植物,苹果树,水草,果树,草,

24、树,AKO,AKO,AKO,AKO,AKO,有根,有叶,有根,有叶,会结果,结苹果,长在水,中,中,例：用,语,语义网,络,络表示,下,下列知,识,识：,猎狗是,一,一种狗,，,，而狗,是,是一种,动,动物。,狗,狗除了,动,动物的,有,有生命,、,、能吃,食,食物、,有,有繁殖,能,能力、,能,能运动,外,外，还,有,有以下,特,特点：,身,身上有,毛,毛、有,尾,尾巴、,四,四条腿,；,；猎狗,的,的特点,是,是吃肉,、,、奔跑,速,速度快,、,、能狩,猎,猎、个,头,头大；,而,而狮子,狗,狗也是,一,一种狗,，,，它的,特,特点是,吃,吃饲料,、,、身体,小,小、奔,跑,跑速度,慢,慢

25、、不,咬,咬人、,供,供观赏,。,。,,解题分,析,析,（,1,）本知,识,识涉及,的,的对象,有,有,4,个：猎,狗,狗、狮,子,子狗、,狗,狗、动,物,物。猎,狗,狗和狮,子,子狗都,是,是一种,狗,狗，除,了,了它们,本,本身的,属,属性外,，,，具有,狗,狗的一,般,般特性,：,：身上,有,有毛、,有,有尾巴,、,、四条,腿,腿。而,狗,狗是一,种,种动物,，,，动物,所,所具有,的,的属性,它,它也具,有,有。,（,2,）猎狗,与,与狗之,间,间是一,种,种类属,关,关系，,狗,狗和动,物,物之间,也,也是一,种,种类属,关,关系，,它,它们都,可,可以用,AKO,表示。,（,3,）

26、整理,各,各对象,节,节点之,间,间的属,性,性，使,上,上层节,点,点所具,有,有的属,性,性不在,下,下层节,点,点中标,出,出。,（,4,）将各,对,对象作,为,为一个,节,节点，,而,而它们,之,之间的,关,关系作,为,为弧，,得,得到如,下,下图所,示,示的语,义,义网络,。,。,动物,狮子狗,猎狗,狗,AKO,AKO,AKO,身上有,毛,毛,有尾巴,有四条,腿,腿,跑得快,能狞猎,有生命,吃饲料,能吃食,物,物,有繁殖,能,能力,能运动,个头大,吃肉,个头小,跑得慢,不咬人,供观赏,2.5,框架表,示,示,1974,年，由,Minsky,在“,A frameworkforrepre

27、senting knowledge”,中提出,。,。,框架是,一,一种描,述,述所论,对,对象属,性,性的数,据,据结构,。,。所论,对,对象可,以,以是一,个,个事物,、,、一个,事,事件或,者,者一个,概,概念。,一,一个框,架,架由若,干,干个“,槽,槽”组,成,成，每,个,个“槽,”,”又可,划,划分为,若,若干个,“,“侧面,”,”。一,个,个槽用,于,于描述,所,所论及,对,对象的,某,某一方,面,面的属,性,性，一,个,个侧面,用,用于描,述,述相应,属,属性的,一,一个方,面,面。槽,和,和侧面,所,所具有,的,的属性,值,值分别,称,称为槽,值,值和侧,面,面值。,槽,槽值可

28、,以,以是逻,辑,辑型或,数,数字型,的,的，具,体,体的值,可,可以是,程,程序、,条,条件、,默,默认值,或,或是一,个,个子框,架,架。,框架表,示,示,用框架,表,表示法,表,表示知,识,识的步,骤,骤如下,：,：,（,1,）分析,待,待表达,知,知识中,的,的对象,及,及其属,性,性，对,框,框架中,的,的槽进,行,行合理,设,设置。,（,2,）对各,对,对象间,的,的各种,联,联系进,行,行考察,。,。使用,一,一些常,用,用的名,称,称或根,据,据具体,需,需要定,义,义一些,表,表达联,系,系的槽,名,名，来,描,描述上,、,、下层,框,框架间,的,的联系,。,。,（,3,）对

29、各,层,层对象,的,的“槽,”,”及“,侧,侧面”,进,进行合,理,理的组,织,织安排,，,，避免,信,信息描,述,述的重,复,复。,例：用,框,框架表,示,示下述,报,报道的,地,地震事,件,件,【,虚拟新,华,华社,3,月,15,日电,】,昨日,，在,云南玉,溪,溪地区,发生,地震,，造成,财产损,失,失约,10,万元,，统计,部,部门,如果需,要,要详细,的,的损失,数,数字,，可,电询,62332931,。另据,专,专家,认为震,级,级,不会超,过,过,4,级,，并认,为,为地,处无人,区,区，不,会,会造成,人,人员伤,亡,亡,。,提示：,分,分析概,括,括用下,划,划线标,出,出的

30、要,点,点，经,过,过概念,化,化形成,槽,槽（,slot,）、侧,面,面（,facet,）值。,特,特别要,注,注意，,“,值,”,（,value,）、,“,默认值,”,（,default,）、,“,如果需,要,要值,”,（,if-needed,）、,“,如果附,加,加值,”,（,if-added,）的区,别,别与应,用,用，建,议,议采用,格,格式如,下,下，不,用,用的侧,面,面值可,删,删。,,,,,Frame,地震,,Slot1,：,Value,：,Default,：,If-needed,：,If-added,：,,,Slot2,：,Value,：,Default,：,If-need

31、ed,：,If-added,：,,,Slot3,：,Value,：,Default,：,If-needed,：,If-added,：,,,,解：,第一步,：,：确定,框,框架的,名,名字和,框,框架的,槽,槽。,本报道中，,涉,涉及地震的,发,发生时间、,地,地点、财产,损,损失、伤亡,人,人数、震级,大,大小等属性,，,，所以，可,将,将时间、地,点,点、震级、,伤,伤亡人数、,财,财产损失等,作,作为槽名。,第二步：分,析,析本报道中,各,各对象间的,关,关系。,由于报道中,只,只涉及地震,一,一件事，所,以,以该步可省,略,略。,框架名：＜地震,1,＞,时间：,3,月,14,日,,,,,

32、,,地点：云南玉溪地区,,,,,,,震级：,专家经验值：≤,4,级,准确值：,NIL,,,,,伤亡人数：,专家经验值：,0,,,,,,,财产损失：,大约损失：,10,万元,if-needed,：,ASK,（电询,62332931,）,,,第,3,章　搜索推,理,理技术,重点掌握一,般,般图搜索策,略,略和消解原,理,理，掌握各,种,种搜索方法,和,和产生式系,统,统原理，了,解,解规则演绎,系,系统的基本,原,原理，对系,统,统组织技术,、,、不确定性,推,推理和非单,调,调推理等高,级,级推理技术,作,作一般性了,解,解。,,第,3,章　搜索推,理,理技术,从问题表示,到,到问题的解,决,决

33、，有一个,求,求解的过程,。,。而实现求,解,解的过程，,采,采用的基本,方,方法包括搜,索,索和推理。,第,3,章　搜索推,理,理技术,和搜索相对,应,应的知识表,示,示法一般有,两,两种：,状态空间法,：（,S,，,F,，,G,）,与或图表示,法,法：基于一,种,种分解与变,换,换的思想，,利,利用树状结,构,构对复杂问,题,题进行表示,，,，使复杂问,题,题简单化。,第,3,章　搜索推,理,理技术,图搜索策略,是,是一种在图,中,中寻找路径,的,的方法。,搜索种类：,盲目搜索：,只,只按预先规,定,定的搜索控,制,制策略进行,搜,搜索。,启发式搜索,：,：根据问题,本,本身的特性,或,或

34、搜索过程,中,中产生的一,些,些信息来不,断,断改变和调,整,整搜索的方,向,向。,图搜索过程,框,框图,开始,把,S,放入,OPEN,表,OPEN,为空表？,把第一个节点,(n),从,OPEN,移至,CLOSED,表,n,为目标节点？,把,n,的后继节点放入,OPEN,表的,末端，提供返回节点,n,的指针,修改指针方向,重排,OPEN,表,失败,成功,是,是,否,否,3.2,盲目搜索,盲目搜索又,叫,叫做无信息,搜,搜索，一般,只,只适用于求,解,解比较简单,的,的问题。宽,度,度优先搜索,和,和深度优先,搜,搜索，属于,盲,盲目搜索方,法,法。,,3.2.1,宽度优先搜,索,索,搜索是以接

35、,近,近起始节点,的,的程度依次,扩,扩展节点的,，,，如左图所,示,示。,从,从图可见，,这,这种搜索是,逐,逐层进行的,；,；在对下一,层,层的任一节,点,点进行搜索,之,之前，必须,搜,搜索完本层,的,的所有节点,。,。,,s,L,O,M,F,P,Q,N,F,F,F,例：把宽度,优,优先搜索应,用,用于八数码,难,难题时所生,成,成的搜索树,，,，这个问题,就,就是要把初,始,始棋局变为,如,如右图所示,的,的目标棋局,问,问题：,,,,,,,,3.3,启发式搜索,盲目搜索的,不,不足：效率,低,低，耗费过,多,多的计算空,间,间与时间。,分析前面介,绍,绍的宽度优,先,先、深度优,先,

36、先搜索，或,等,等代价搜索,算,算法,,,其主要的差,别,别是,OPEN,表中待扩展,节,节点的顺序,问,问题。人们,就,就试图找到,一,一种方法用,于,于排列待扩,展,展节点的顺,序,序，即选择,最,最有希望的,节,节点加以扩,展,展，那么，,搜,搜索效率将,会,会大为提高,。,。,启发信息：,进,进行搜索技,术,术一般需要,某,某些有关具,体,体问题领域,的,的特性的信,息,息，把此种,信,信息叫做启,发,发信息。,把利用启发,信,信息的搜索,方,方法叫做启,发,发式搜索方,法,法。,3.3,启发式搜索,启发式搜索,策,策略,启发信息用,于,于决定要扩,展,展的下一个,节,节点，以免,象,

37、象在宽度优,先,先或深度优,先,先搜索中那,样,样盲目地扩,展,展。,这种搜索总,是,是选择,“,最有希望,”,的节点作为,下,下一个被扩,展,展的节点。,这,这种搜索叫,做,做有序搜索,(ordered search),。,3.2.1,有序搜索,有序搜索又,称,称为最好优,先,先搜索，它,总,总是选择最,有,有希望的节,点,点作为下一,个,个要扩展的,节,节点。,估价函数,f,的确定：一,个,个节点的希,望,望程度越大,，,，则其,f,值越小。为,此,此，被选为,扩,扩展的节点,，,，是估价函,数,数最小的节,点,点。,f,是从起始节,点,点约束地通,过,过节点,n,而到达目标,节,节点的最

38、小,代,代价路径上,的,的一个估算,代,代价,。,3.3.1,有序搜索,宽度优先搜,索,索、等代价,搜,搜索和深度,优,优先搜索统,统,统是有序搜,索,索技术的特,例,例。,对于宽度优,先,先搜索，我,们,们选择,f(i),作为节点,i,的深度。对,于,于等代价搜,索,索，,f(i),是从起始节,点,点至节点,i,这段路径的,代,代价。,3.3.2A,*,算法,A*,算法是一种,有,有序搜索算,法,法，其特点,在,在于对估价,函,函数的定义,上,上。,估价函数,f,：,f(n)=g(n)+h(n),g(n),：就是到目,前,前为止用搜,索,索算法找到,的,的从,S,到,n,的最小路径,代,代价

39、。,h(n),：,依赖于有关,问,问题的领域,的,的启发信息,。,。,从节点,n,到某目标节,点,点的一条最,佳,佳路径的代,价,价,的估计。,,例：八数码,难,难题,,,,,解：,采用,估,估价,函,函数,f(n)=d(n)+W(n),其中,：,：,d(n),是搜,索,索树,中,中节,点,点,n,的深,度,度；,W(n),用来,计,计算,对,对应,于,于节,点,点,n,的数,据,据库,中,中错,放,放的,棋,棋子,个,个数,。,。,因此，起,始,始节点棋,局,局的,f,值等于,0+3=3,。,,Sg,S,0,3,4,4,5,5,5,6,4,6,4,4,6,3.4,消解,原,原理,重点,掌,掌

40、握,子,子句,集,集的,求,求解,步,步骤,和,和消,解,解反,演,演过,程,程，,掌,掌握,消,消解,推,推理,的,的规,则,则。,3.4.1,子句,集,集的,求,求取,例、,将,将下,列,列谓,词,词演,算,算公,式,式化,为,为一,个,个子,句,句集,(,,x){P(x),{,(,,y)[P(y),,P(f(x,y))],,(,,y)[Q(x,y),,P(y)]}},,,(1)(,,x){~P(x),{,(,,y)[~P(y),,P(f(x,y))],,(,,y)[~Q(x,y),,P(y)]}},(2) (,,x){~P(x),{,(,,y)[~P

41、(y),,P(f(x,y))],,(,,y){,,[~Q(x,y),,P(y)]}}},(,,x){~P(x),{,(,,y)[~P(y),,P(f(x,y))],,(,,y)[Q(x,y),,P(y)]}},(4) (,,x){~P(x),{,(,,y)[~P(y),,P(f(x,y))],,[Q(x,g(x)),,~ P(g(x))]}},式中,w=g(x),为一个,Skolem,函数,(5) (,,x)(,,y){~P(x),{,[~P(y),,P(f(x,y))],,[Q(x,g(x)),,~ P(g(x))]}},,(3) (,,x

42、){~P(x),{,(,,y)[~P(y),,P(f(x,y))],,(,,w)[Q(x,w),,~ P(w)]}},(6) (,,x)(,,y){[~P(x),,~P(y),,P(f(x,y))],,[~P(x),,Q(x,g(x))],[,~P(x),,~ P(g(x))]},,(8)~P(x),,~P(y),,P(f(x,y)),~P(x),,Q(x,g(x)),~P(x),,~ P(g(x)),(9),更改变,量,量名称,，,，在上,述,述第（,8,）步的,3,个子句,中,中，分,别,别以,x1,x2,x3,代替变,量,量,x,。这种,更,更改变,量

43、,量名称,的,的过程,，,，有时,称,称为变,量,量分离,标,标准化,。,。于是,，,，可以,得,得到下,列,列子句,集,集：,~P(x1),,~P(y),,P(f(x1,y)),~P(x2),,Q(x2,g(x2)),~P(x3),,~ P(g(x3)),(7)[~P(x),,~P(y),,P(f(x,y))],,[~P(x),,Q(x,g(x))],[,~P(x),,~ P(g(x))],3.4.2,消解反,演,演求解,过,过程,1,、消解,反,反演,给出一,个,个公式,集,集,S,和目标,公,公式,L,，通过,反,反证或,反,反演来,求,求证目,标,标公式,L,，其证

44、,明,明步骤,如,如下：,(1),否定,L,，得～,L,；,(2),把～,L,添加到,S,中去；,(3),把新产,生,生的集,合,合｛～,L,，,S,｝化成,子,子句集,；,；,(4),应用消,解,解原理,，,，力图,推,推导出,一,一个表,示,示矛盾,的,的空子,句,句,NIL,。,例,1,、,判断下,列,列子句,集,集中哪,些,些是不,可,可满足,的,的,分析：,子,子句集,中,中各子,句,句间的,关,关系是,合,合取关,系,系，因,此,此只要,有,有一个,子,子句不,可,可满足,，,，则子,句,句集就,是,是不可,满,满足的,。,。,(1)NIL(,空子句,),是不可,满,满足的,。,。

45、,(2),在子句,集,集中选,择,择合适,的,的子句,对,对其进,行,行消解,，,，若能,推,推出空,子,子句，,就,就说明,子,子句,S,是不可,满,满足的,。,。,(1)S={,～,P∨Q,，～,Q,，,P,，～,P,},对子句,集,集,S,进行归,结,结推理,：,：,(1),～,P∨Q,(2),～,Q,(3)P,(4),～,P,(5)NIL(3)(4),归结,故该子,句,句集是,不,不可满,足,足的。,(2)S={,～,P(x)∨Q(f(x),a),，,～,P(h(y))∨Q(f(h(y)),a)∨,～,P(z),},解：因,子,子句集,中,中无互,补,补对，,故,故在子,句,句集,S,

46、中不存,在,在空子,句,句，故,S,为,可满,足,足的,。,。,,例,2,证明,(,,x)(P(x),(,Q(x),∧,∧R(x))),∧,∧(,x,)(P(x)∧T(x)),(,,x)(T(x),∧,∧R(x)),证明,：,：第,一,一步,：,：先,对,对结,论,论否,定,定并,与,与前,提,提合,并,并得,到,到谓,词,词公,式,式,G,。,G=(,,x)(P(x),(,Q(x),∧,∧R(x))),∧,∧(,x,)(P(x)∧T(x)),∧,∧,～,(x)(T(x)∧R(x)),第二,步,步：,将,将公,式,式,G,化为,子,子句,集,集。,可将,G,看作,是,是三,

47、项,项的,合,合取,，,，对,每,每一,项,项分,别,别求,子,子句,集,集。,,G1,：,(,,x)(P(x),(,Q(x),∧,∧R(x))),=,(x)(,～,P(x),∨,∨,(Q(x)∧R(x))),=(,,x)((,～,P(x),∨,∨,Q(x))∧(,～,P(x),∨,∨,R(x))),所以,S1={,～,P(x1)∨,Q(x1),,～,P(x2)∨,R(x2)},G2:,(,x,)(P(x)∧T(x)),所以,S2={,P(a),T(a)},～,B:,～,(x)(T(x)∧R(x)),=(,,x)(,～,T(x),∨,∨,～,R(x)),所以,S,～,B,={

48、,～,T(x),∨,∨,～,R(x),},从而,求,求得,公,公式,G,的子,句,句集,：,：,S=S1,∪,∪S2∪S,～,B,=,{,～,P(x1)∨,Q(x1),,～,P(x2)∨,R(x2),,P(a),T(a),,～,T(x3)∨,～,R(x3)},第三,步,步：,例,例用,消,消解,原,原理,，,，对,子,子句,集,集,S,进行消,解,解,～,P(x2)∨R(x2),P(a),R(a),～,T(x3)∨,～,R(x3),～,T(a),,1,={a/x2},T(a),,2,={a/x3},NIL,由此得,出,出子句,集,集,S,是不可,满,满足的,，,，因此,公,公式,G,也是不

49、,可,可满足,的,的。从,而,而命题,得,得证。,例,3,某公司,招,招聘人,员,员，,A,、,B,、,C,三人应,试,试，经,面,面试后,，,，公司,有,有如下,想,想法：,(1),三人中,至,至少录,用,用一人,；,；,(2),如果录,用,用,A,而不录,用,用,B,，则一,定,定录用,C,；,(3),如果录,用,用,B,，则一,定,定录用,C,。,求证：,公,公司一,定,定录取,C,。,证：,定,定义：,P(x),表示录,用,用,x,。,则前提,为,为,(1)P(A)∨P(B),∨,∨P(C),(2)(P(A)∧(,～,P(B)))=>P(C),(3)P(B)=>P(C),则结论,为,为

50、,P(C),将前提,化,化为子,句,句集：,(1),P(A)∨P(B),∨,∨P(C),(2),～,P(A)∨P(B),∨,∨P(C),(3),～,P(B)∨,P(C),将结论,否,否定并,化,化为子,句,句集：,(4),～,P(C),利用消,解,解原理,，,，对子,句,句集进,行,行消解,：,：,P(A)∨P(B)∨P(C),～,P(A)∨P(B)∨P(C),P(B)∨P(C),～,P(B)∨P(C),P(C),～,P(C),NIL,故证得,结,结论：,公,公司一,定,定录取,C,2,、反演,求,求解过,程,程,步骤,：,：,(1),把已,知,知前,提,提用,谓,谓词,公,公式,表,表示,出

51、,出来,，,，并,化,化为,相,相应,的,的子,句,句集,S,。,(,2,),把,待求,解,解的,问,问题,也,也用,谓,谓词,公,公式,表,表示,出,出来,，,，然,后,后把,它,它的,否,否定,与,与谓,词,词,ANSWER,构成,析,析取,式,式。,(,3,),把第,(2),步得,到,到的,析,析取,式,式化,为,为子,句,句集,，,，并,入,入子,句,句集,S,中，,得,得到,子,子句,集,集,S,’,。,(4),对子,句,句集,S,’,应用,消解,原理,进,进行,消,消解,。,。,(,5,),若得,答,答案,ANSWER,，则,答,答案,就,就在,ANSWER,中,。,例,1,：,应

52、用,消,消解,反,反演,求,求解,如,如下,问,问题,：,：,“如,果,果无,论,论约,翰,翰,(John),到哪,里,里去,，,，菲,多,多,(Fido),也就,去,去那,里,里，,那,那么,如,如果,约,约翰,在,在学,校,校里,，,，菲,多,多在,哪,哪里,呢,呢,?”,解：,定,定义,谓,谓词,：,：,AT,（,x,y,）表,示,示,x,在,y,那里,。,。,则前,提,提为,：,：,(,,x)(AT(JOHN,x),,AT,(FIDO,x),和,AT(JOHN,SCHOOL),目标,公,公式,：,：,(,,x,)AT(FIDO,x),目标,公,公式,否,否定,为,为：,(,,x

53、)(,～,AT(FIDO,x)),其子,句,句形,为,为：,～,～,AT(FIDO,x),对本,例,例应,用,用消,解,解反,演,演过,程,程：,（,1,）目,标,标公,式,式否,定,定的,子,子句,形,形为,：,：,～,AT(FIDO,x),将它,与,与谓,词,词,ANSWER,构成,析,析取,式,式：,～,AT(FIDO,x),∨,∨ANSWER(FIDO,x),（,2,）用,下,下图,的,的反,演,演树,进,进行,消,消解,，,，并,在,在根,部,部得,到,到子,句,句：,A,NSWER,(FIDO,SCHOOL),～,AT(FIDO,x)∨ANSWER(FIDO,x),～,AT(JOH

54、N,y)∨AT(FIDO,y),～,AT(JOHN,x)∨ANSWER(FIDO,x),AT(JOHN,SCHOOL),ANSWER(FIDO,SCHOOL),1={x/y},2={SCHOOL/x},例,2,某公,司,司招,聘,聘人,员,员，,A,、,B,、,C,三人,应,应试,，,，经,面,面试,后,后，,公,公司,有,有如,下,下想,法,法：,(1),三人,中,中至,少,少录,用,用一,人,人；,(2),如果,录,录用,A,而不,录,录用,B,，则,一,一定,录,录用,C,；,(3),如果,录,录用,B,，则,一,一定,录,录用,C,。,求公,司,司录,用,用谁,？,？,解：,定,定

55、,义,义：,P(x),表示,录,录用,x,。,则前,提,提为,(1)P(A),∨,∨P(B)∨P(C),(2)(P(A)∧(,～,P(B)))=>P(C),(3)P(B)=>P(C),则结,论,论为,P(x),将前,提,提化,为,为子,句,句集,：,：,(1),P(A),∨,∨P(B)∨P(C),(2),～,P(A),∨,∨P(B)∨P(C),(3),～,P(B),∨,∨,P(C),将结,论,论否,定,定与,谓,谓词,ANSWER,构成,析,析取,式,式：,(4),～,P(x),∨,∨ANSWER(x),利用,消,消解,原,原理,，,，对,子,子句,集,集进,行,行消,解,解：,P(A)∨P(

56、B)∨P(C),～,P(A)∨P(B)∨P(C),P(B)∨P(C),～,P(B)∨P(C),P(C),～,P(x)∨ANSWER(x),ANSWER(C),={C/x},可见,公,公司,一,一定,录,录取,C,例,3,已知,（,（,1,）王,是,是李,的,的老,师,师,（,2,）李,是,是张,的,的同,学,学,（,3,）如,果,果,x,与,y,是同,学,学，,则,则,x,的老,师,师也,是,是,y,的老,师,师。,求：,张,张的,老,老师,是,是谁,？,？,,解：,令,令,T(x,y):x,是,y,的老,师,师；,C(x,y),：,x,是,y,的同,学,学,,,则,已知,的,的三,个,个事

57、,实,实可,解,解释,为,为下,列,列公,式,式集,T(Wang,Li),C(Li,Zhang),(x)(y)(z){C(x,y)∧T(z,x)=>T(z,y)},目标,公,公式,：,：,(,,x)T(x,Zhang),将上,述,述事,实,实化,为,为子,句,句集,：,：,①,T(Wang,Li),②,C(Li,Zhang),③,～,C(x,y),∨,∨,～,T(z,x),∨,∨,T(z,y),目标,公,公式,否,否定,的,的子,句,句形,为,为：,～,T(x,Zhang),将它,与,与谓,词,词,ANSWER,构成,析,析取,式,式：,④,～,T(w,Zhang),∨,∨ANSWER

58、(w,Zhang),用下,图,图的,反,反演,树,树进,行,行消,解,解，,并,并在,根,根部,得,得到,子,子句,：,～,C(x,y),∨,∨,～,T(z,x),∨,∨T(z,y),T(Wang,Li),～,C(Li,y)∨T(Wang,y),C(Li,Zhang),T(Wang,Zhang),,1,={Wang/z,Li/x},～,T(w,Zhang),∨,∨ANSWER(w,Zhang),,2,={Zhang/y},ANSWER(Wang,Zhang),,3,={Wang/w},3.5,产生,式,式系,统,统,1,、产,生,生式,系,系统,的,的组,成,成,产生,式,式系,统,统由

59、,3,个部,分,分组,成,成，,即,即总,数,数据,库,库,(,或全,局,局数,据,据库,),、产,生,生式,规,规则,和,和控,制,制策,略,略，,总数据,库,库又称,为,为综合,数,数据库,、,、上下,文,文、黑,板,板等，,用,用于存,放,放求解,过,过程中,各,各种当,前,前信息,的,的数据,结,结构，,如,如问题,是,是的初,始,始状态,、,、事实,或,或证据,、,、中间,推,推理结,论,论和最,后,后结果,等,等。,产生式,规,规则是,一,一个规,则,则库，,用,用于存,放,放与求,解,解问题,有,有关的,某,某个领,域,域知识,的,的规则,之,之集合,及,及其交,换,换规则,。,

60、。,其基本,形,形式为,IF,前提,THEN,结论,控制策,略,略的作,用,用是说,明,明下一,步,步应该,选,选用什,么,么规则,。,。,2,、例：,设,设有八,数,数码难,题,题：,,,,,,请用产,生,生式规,则,则表示,移,移动小,方,方块的,操,操作。,初始状,态,态,目标状,态,态,,解：,1,）建立,棋,棋盘变,换,换的产,生,生式规,则,则。,如果把,棋,棋盘的,每,每一布,局,局看作,是,是一个,状,状态矩,阵,阵，本,题,题就变,成,成了从,初,初始状,态,态矩阵,到,到目标,状,状态矩,阵,阵的一,种,种变化,。,。,设,S,ij,为状态,矩,矩阵的,第,第,i,行和第,

61、j,列的数,码,码，其,中,中,3≥i, j,≥,≥1,。,i,0,,j,0,表示空,格,格所在,的,的行和,列,列。如,果,果在状,态,态矩阵,中,中用,0,来表示,空,空格的,话,话，则,建,建立如,下,下四条,产,产生式,规,规则：,R1:if (j,0,-1≥1)then begin,S,i0j0,:=S,i0(j0-1),;,S,i0(j0-1),:=0end,空格左,移,移,,R2:if (i,0,-1≥1)then begin,S,i0j0,:=S,(i0-1)j0,;,S,(i0-1)j0,:=0end,空格上,移,移,R3:if (j,0,+1≤3)then begin,S,

62、i0j0,:=S,i0(j0+1),;,S,i0(j0+1),:=0end,空格右,移,移,R4:if (i,0,+1≤3)then begin,S,i0j0,:=S,(i0+1)j0,;,S,(i0+1)j0,:=0end,空格下,移,移,2,）建立,综,综合数,据,据库,将棋盘,的,的布局,表,表示为,状,状态矩,阵,阵的形,式,式存入,综,综合数,据,据库。,例如，,初,初始布,局,局和目,标,标布局,以,以矩阵,形,形式表,示,示为：,综合数,据,据库中,，,，存放,着,着初始,状,状态矩,阵,阵和目,标,标状态,矩,矩阵以,及,及变换,过,过程中,的,的中间,矩,矩阵。,3,）推理,

63、求,求解,在进行,推,推理求,解,解时，,可,可能会,有,有多条,产,产生式,规,规则的,条,条件部,分,分和综,合,合数据,库,库中的,已,已有事,实,实相符,，,，这样,就,就有可,能,能激活,多,多条规,则,则。,究竟采用哪,一,一条规则作,为,为启用规则,规,规则，这就,是,是冲突解决,策,策略问题。,在本题中采,用,用一个启发,式,式函数,f(n)=d(n)+W(n),其中：,d(n),是搜索树中,节,节点,n,的深度；,W(n),用来计算对,应,应于节点,n,的数据库中,错,错放的棋子,个,个数。,在综合数据,库,库中的初始,矩,矩阵，能满,足,足规则,R1,，,R2,，,R3,，

64、,R4,的条件，所,以,以有四条匹,配,配规则。利,用,用启发函数,决,决定哪一条,规,规则为启用,规,规则。因为,规,规则,R1,的启发式函,数,数值,h(x)=4,，规则,R2,的启发式函,数,数值,h(x)=4,,规则,R3,的启发式函,数,数值,h(x)=5,,规则,R4,的启发式函,数,数值,h(x)=5,。在这里,R1,与,R2,所得到的新,状,状态与目标,状,状态差距最,小,小，且都为,4,，而在,R1,与,R2,中再选择一,条,条规则作为,启,启用规则，,在,在这里我们,使,使用规则的,排,排列顺序，,首,首先选择,R1,，所以启用,规,规则,R1,，依次类推,。,。,可以得到到,达,达目标状态,的,的规则执行,序,序列如下：,R1,，,R2,，,R1,，,R4,，,R3,其执行过程,如,如下图所示,。,。,图中节点旁,所,所标数字为,h(x),的值，箭头,上,上所标为启,用,用的规则。,Sg,S,0,3,4,4,5,5,5,6,4,6,4,4,6,R1,R2,R3,R4,R2,R4,R1,R3,R4,R3,R4,演讲完毕，,谢,谢谢观看！,