第10章 人工智能程序设计VIP

人工智能基础,主讲:蔡自兴教授,第十章人工智能程序设计,10.1符号和逻辑处理编程语言10.2LISP语言10.3PROLOG语言10.4专用开发工具与人工智能机,10.1符号和逻辑处理编程语言,对符号和逻辑处理编程语言的要求具有表结构形式便于表示知识和逻辑计算具有识别数据、确定控制匹配模式和进行自动演绎的能力能够建立框架结构，便于聚集各种知识和信息，并作为一个整体存取具有以最适合于特定任务的方式把程序与说明数据结合起来的能力具有并行处理的能力,3,现有的符号和逻辑处理语言编程语言,4,10.1符号和逻辑处理编程语言,图10.1逻辑型编程语言的分类,10.2LISP语言,LISP语言的特点主要数据结构是表特性表简单最主要的控制结构为递归程序内外一致能够产生更复杂的函数和解释程序对事物的约束发生在尽可能晚的时刻数据和过程都可以表示成表交互方式运行,5,10.2.1LISP的特点和数据结构,10.2.1LISP的特点和数据结构,数据结构原子LISP中最小的符号单位各种性质或属性可附加到单个原子上最重要的属性除其名字外是值表递归地定义为括号内零个或n个元素的序列表的数据结构（CONS单元）控制结构,6,10.2.1LISP的特点和数据结构,变量约束及其辖域变量约束到值上建立函数辖域,7,10.2.2LISP的基本函数,CAR和CDRCDR返回表中除第一个元素之外的其余部分CAR返回表中的第一个元素SET和SETQ赋值函数SET使第二个自变量为第一个自变量的值SETQ不对第一个变量求值,8,10.2.2LISP的基本函数,APPEND、LIST和CONSAPPEND把所有作为自变量的表内各元素串在一起LIST用自变量造出一张表，每个自变量成为表中的一个元素CONS作用于一张表，在其中插入一个新的第一元素EVAL,9,10.2.2LISP的基本函数,DEFUN建立新函数T和NIL逻辑上的真与假AND、OR及NOTCOND条件函数PROG,10,10.2.2LISP的基本函数,GET和PUTPROPGET检索特征值PUTPROP存放特征值、替代特征值LAMBDA定义匿名函数READ和PRINT对话,11,10.2.3递归和迭代,递归执行的一部分涉及到再次执行该函数迭代约束某些变量；测试变量以检查出口（停止）条件是否适用。若适用，则进行；以某种方法改变变量的值；返回。,12,10.2.4LISP编程举例,LISP程序设计的一般步骤将问题用递归的表处理方式表示，即问题的概念化。根据问题求解的要求，设计问题求解的搜索推理过程。根据所设计的求解过程，定义所需要的工作函数。根据求解过程，给出函数调用的顺序。根据问题求解的目标和解的评价准则，给出程序结束的标志。,13,10.3PROLOG语言,项的定义子句事实规则问题表结构,14,10.3.1语法与数据结构,10.3.2PROLOG程序设计原理,匹配（Matching）设法满足一个目标从事实和规则的顶部开始搜索。找到一个与之匹配的事实或规则的头。找不到相匹配的事实或规则的头，则目标失败。设法重新满足这一目标。,15,10.3.2PROLOG程序设计原理,合一（Unification）对事实子句（或规则）中的变量进行换名，使其不与目标中的变量同名，对变量受囿表进行初始化。检查目标子句与事实子句（或规则）的下一个相异项是否不存在；若不存在，则结束合一过程，合一成功，返回合一过程中产生的变量受囿表；若存在，则转。根据合一原则，判断目标子句与事实子句（或规则）的下一个相异项是否可合一。若可合一，就把这两项加入到变量受囿表中，并对目标子句和事实子句（或规则）中的有关变量进行置换，然后转；若不可合一，则结束合一过程，释放变量受囿表，返回不可合一信息。,16,10.3.2PROLOG程序设计原理,回溯（Backtracking）把问题语句作为初始目标，并置其为激发状态，开始执行该目标。系统处于激发状态时，先为该目标保存必要的回溯信息，然后判断它是否是单一子句组成的目标。如果是就转；否则就依次从左到右求解激发目标的各个子目标。当所有的子目标都得到满足时，激发目标就成功返回。否则，激发目标就失败返回。系统执行一个由单一子句组成的激发目标时，就从事实规则库中取出与激发目标子句句首谓词符号相同的子句子集，从该子句子集的顶部开始查找可与激发目标合一的子句。,17,10.3.3PROLOG编程举例,梵塔问题hanoi(N):-move(N,left,centre,right)move(0,_，_，_，)：-!.move(N,A,B,C):-MisN-1,move(M，A，C，B)，inform(A,B),move(M,C,B,A)inform(X,Y):-write(move,a,disc,from,the,X,pole,to,the,Y,pole),n1.?-honoi(3).moveadiscfromtheApoletotheBpolemoveadiscfromtheApoletotheCpolemoveadiscfromtheBpoletotheCpolemoveadiscfromtheApoletotheBpolemoveadiscfromtheCpoletotheApolemoveadiscfromtheCpoletotheBpolemoveadisc