7-AI程序设计语言ppt课件

1、人工智能人工智能程序设计语言程序设计语言sspu 王帅概概 述述前面几章，我们介绍了一些运用前面几章，我们介绍了一些运用AI技术求解问技术求解问题的一般方法。这些方法可运用于定理证明、题的一般方法。这些方法可运用于定理证明、自然语言理解、模式识别、专家系统等各个领自然语言理解、模式识别、专家系统等各个领域。要在计算机上实现，就涉及到计算机语言域。要在计算机上实现，就涉及到计算机语言的问题。的问题。严格地讲，可以使用任何计算机语言来实现这严格地讲，可以使用任何计算机语言来实现这些算法。但是些算法。但是AI的主要课题是非数值计算的问的主要课题是非数值计算的问题求解和知识处理等复杂问题，主要任务在于

2、题求解和知识处理等复杂问题，主要任务在于完成推理、规划、决策、分析、论证等智能行完成推理、规划、决策、分析、论证等智能行为，其中包括各种符号处理和表处理等。传统为，其中包括各种符号处理和表处理等。传统过程性语言不太适合过程性语言不太适合AI方面的程序设计方面的程序设计sspu 王帅AI AI语言的特点语言的特点具有回溯功能具有回溯功能具有模式匹配功能具有模式匹配功能守护功能保护递归、回溯的现场）守护功能保护递归、回溯的现场）过程说明功能解释推理过程）过程说明功能解释推理过程）表达能力强尤其对各种符号知识）表达能力强尤其对各种符号知识）建立在严格的数学系统上因为建立在严格的数学系统上因为AI中的

3、许多推中的许多推理都有坚实的数学基础）理都有坚实的数学基础）表处理功能表处理功能并行处理或分布处理提高推理速度，实现时并行处理或分布处理提高推理速度，实现时多采用模拟并行处理技术）多采用模拟并行处理技术）sspu 王帅常用的常用的AI AI程序设计语言程序设计语言PrologLispCC+Smalltalksspu 王帅PrologPrologProlog是是Programming in Logic用逻辑进行用逻辑进行程序设计的缩写程序设计的缩写第一个第一个Prolog系统是由系统是由Colmerauer及其研及其研究小组于究小组于1972年在法国马赛研制成功年在法国马赛研制成功Prolog是

4、完全基于一阶谓词逻辑基础上的，是完全基于一阶谓词逻辑基础上的，它的所有语句和推理都可以用它的所有语句和推理都可以用Horn子句归子句归结的形式表示，所以它又严格的数学基础结的形式表示，所以它又严格的数学基础sspu 王帅Prolog Prolog 的特点的特点逻辑型语言逻辑型语言语句类型简单，只有三种基本形式：现实、语句类型简单，只有三种基本形式：现实、规则、讯问规则、讯问接近于自然语言，简洁明了，易写易读接近于自然语言，简洁明了，易写易读数据和程序结构一致都由项构成，便于数据和程序结构一致都由项构成，便于将将a程序的输出作为程序的输出作为b程序的输入）程序的输入）能自动进行匹配和回溯能自动进

5、行匹配和回溯可大量使用递归可大量使用递归sspu 王帅PrologProlog的程序结构的程序结构Prolog程序包括常量段、域段、数据库段、程序包括常量段、域段、数据库段、谓词段、目标段和子句段；另外还可以在谓词段、目标段和子句段；另外还可以在程序首部设置编译指令，在程序中加注释程序首部设置编译指令，在程序中加注释通常，一个通常，一个Prolog程序不一定包括所有段，程序不一定包括所有段，最常用的有子句段、谓词段、域段。如果最常用的有子句段、谓词段、域段。如果需要产生一个可独立执行的程序，还需要需要产生一个可独立执行的程序，还需要有目标段有目标段sspu 王帅/* 注释注释 */编译指令编译

6、指令constants 常量说明常量说明Domains 域语句域语句Database 数据库说明数据库说明Predicates 谓词语句谓词语句Goal 目标语句目标语句Clauses 子句语句子句语句sspu 王帅子句段子句段是整个程序的核心，所有的事实和规则都是整个程序的核心，所有的事实和规则都在子句段列出，例如在子句段列出，例如Clauses like(Bill,Cindy). like(Cindy,Bill). like(Bill,dogs). like(A,C):- like(A,B),like(B,C). parent(ZhangYi,ZhangEr).sspu 王帅谓词段谓词段P

7、rolog有许多内部谓词，如有许多内部谓词，如read,write, makewindow等，对内部谓词不需说明等，对内部谓词不需说明在程序中，若定义了自己要用的外部谓词，在程序中，若定义了自己要用的外部谓词，如上例中如上例中like，parent，则必须在谓词段加，则必须在谓词段加以说明，例：以说明，例：Predicates like(symbol,symbol) parent(symbol,symbol)sspu 王帅域段域段 域就相当于类型说明，如上例中域就相当于类型说明，如上例中parent中的两个参数，中的两个参数，应该是两个人名，则下面的程序更好理解应该是两个人名，则下面的程序更好

8、理解 Domains name=symbol Predicates parent(name,name) 通过域，可以说明标准域中没有定义的数据结构通过域，可以说明标准域中没有定义的数据结构 Domains articles=book(title,author);horse(name) title,author,name=symbol Predicates own(name,articles) Clauses own(John,book(ABC,Ding). own(John,horse(blacky). 标准域：标准域：integer,char,real,ref,string,symbolss

9、pu 王帅目标段目标段目标段输入要解决问题的语句目标段输入要解决问题的语句也可以省略目标段。若省略目标段，则在也可以省略目标段。若省略目标段，则在运行时程序会等待用户输入一个目标，然运行时程序会等待用户输入一个目标，然后才能运行，这时称为外部目标后才能运行，这时称为外部目标若把目标写在目标段中，则程序运行时，若把目标写在目标段中，则程序运行时，自动执行目标，直接显示运行结果，这种自动执行目标，直接显示运行结果，这种目标称为内部目标目标称为内部目标目标段的作用有点类似于主程序目标段的作用有点类似于主程序sspu 王帅目标段目标段PredicatesPredicates run(char) run

10、(char)ClausesClauses run(X):- write(“first”), run(X):- write(“first”), readchar(X). readchar(X). run(X):- write(“second”), run(X):- write(“second”), readchar(X). readchar(X).运行时，会在对话窗口提示输入一个目标，若输入目标运行时，会在对话窗口提示输入一个目标，若输入目标run(X). run(X). 则输出则输出firstfirst，然后按一个键接着输出，然后按一个键接着输出secondsecond，再按一个键，就结束了再

11、按一个键，就结束了外部目标运行时，外部目标运行时，PrologProlog寻找所有解寻找所有解sspu 王帅目标段目标段PredicatesPredicates run(char) run(char)ClausesClauses run(X):- write(“first”), run(X):- write(“first”), readchar(X). readchar(X). run(X):- write(“second”), run(X):- write(“second”), readchar(X). readchar(X).GoalGoal run(X). run(X).运行时，直接显示

12、运行结果，输出运行时，直接显示运行结果，输出firstfirst，然后按一个键，就结束，然后按一个键，就结束了了留意：在有内部目标时，留意：在有内部目标时，PrologProlog只寻找第一个解只寻找第一个解sspu 王帅程序执行和匹配法则程序执行和匹配法则Prolog的程序执行过程就是不断地匹配规的程序执行过程就是不断地匹配规则，在匹配过程中对变量实例化，其实就则，在匹配过程中对变量实例化，其实就是谓词归结推理是谓词归结推理在推理过程中，使用的是在推理过程中，使用的是“试探试探-前往前往-再再试试的回溯方法来对问题求解，也就是深的回溯方法来对问题求解，也就是深度优先的算法，顺着一条路一直往下

13、走，度优先的算法，顺着一条路一直往下走，直到走不下去了，就返回交叉路口，选另直到走不下去了，就返回交叉路口，选另一条路再试一条路再试sspu 王帅PredicatesPredicates likes(symbol,symbol) likes(symbol,symbol) tastes(symbol,symbol) tastes(symbol,symbol) food(symbol) food(symbol)ClausesClauses likes(bill,X):- food(X),tastes(X,good). likes(bill,X):- food(X),tastes(X,good).

14、tastes(pizza,good). tastes(pizza,good). tastes(dumpling,bad). tastes(dumpling,bad). food(dumpling). food(dumpling). food(pizza). food(pizza).GoalGoal likes(bill,What). likes(bill,What).sspu 王帅LispLisp语言语言Lisp是是List Processing 的缩写，是计算机的的缩写，是计算机的表处理语言，处理的都是符号表。表处理语言，处理的都是符号表。1960年年由麦卡锡发明的。由麦卡锡发明的。Lisp

15、语言以语言以1941年年Church提出的提出的演算为理演算为理论基础的，论基础的，演算是与图灵机等价的一种演算是与图灵机等价的一种计算模型计算模型80%的早期的早期AI软件都是用软件都是用Lisp语言写成的语言写成的sspu 王帅LispLisp语言基本结构语言基本结构 Lisp语言的程序和数据具有统一的结构，就是符号表达语言的程序和数据具有统一的结构，就是符号表达式式S-表达式），表达式），S-表达式的基本组成元素是原子表达式的基本组成元素是原子 原子原子 文字原子：相当于标识符，如文字原子：相当于标识符，如ABC 串原子：引号引起的字符串，如串原子：引号引起的字符串，如“aaa” 数字原

16、子：由正负号、小数点和数字组成数字原子：由正负号、小数点和数字组成 S-表达式表达式 原子是原子是S-表达式表达式 若若S1和和S2是是S-表达式，那么表达式，那么S1 S2也是也是S-表达式表达式 例：例：A、（、（A B）、（）、（A （B C）都是正确的）都是正确的S-表达表达式式 但但 （A B C）、（）、（A B）就不是正确的）就不是正确的S-表达式表达式sspu 王帅LispLisp语言基本结构语言基本结构表表是是lisp语言中最常用的结构语言中最常用的结构表由左括号开始，后跟任意多个由空格隔表由左括号开始，后跟任意多个由空格隔开的原子或表，最后以右括号结束开的原子或表，最后以右

17、括号结束例例: (A)、(A B C)、 (1 (2 (3)都是表都是表表的结构是嵌套的，表中最外层元素的个表的结构是嵌套的，表中最外层元素的个数称为表长数称为表长例：例： (A (B C) (D) 的表长为的表长为3sspu 王帅LispLisp语言的基本函数语言的基本函数 算数运算函数用前缀方式表示）算数运算函数用前缀方式表示） (+ 3 5) (+ (* 3 5) (/ 4 2) 表处理函数表处理函数 CAR 取表的第一个元素取表的第一个元素 (CAR (a b c) 得到得到a (CAR (a b) c) 得到得到(a b) 表示禁止求值表示禁止求值 CDR 返回除第一个元素外所有元素

18、组成的表返回除第一个元素外所有元素组成的表 (CONS S1 S2) 把把S1作为第一元素插入作为第一元素插入S2表中表中 (LIST S1 S2 Sn) 将各参数作为表的元素组成一个表将各参数作为表的元素组成一个表 求值和赋值函数求值和赋值函数 (SET A S) 使第一个参数使第一个参数A的取值等于第二个参数的取值等于第二个参数Ssspu 王帅谓词函数：判断是否为真的函数谓词函数：判断是否为真的函数Lisp中，真用中，真用T表示，假用表示，假用NIL表示表示(EQ A1 A2) 检查检查A1和和A2是否是相同的原子是否是相同的原子(EQUAL S1 S2) 检查检查S1 和和S2 是否是相

19、同的表达是否是相同的表达式式输入输出函数输入输出函数（READ） 等待输入等待输入（PRINT S输出表达式输出表达式S的值的值条件函数条件函数( COND (P1 S1) (P2 S2) (Pn Sn)相当于相当于If P1 then S1 Else if P2 then S2Else if Else if Pn then Snsspu 王帅函数定义函数定义格式格式(DEFUN 函数名函数名(参数参数1 参数参数2 参数参数n) 函数体函数体)lisp中，定义函数最常用的手段是递归定义中，定义函数最常用的手段是递归定义例：定义阶乘函数例：定义阶乘函数 0!=1 1!=1 n!=n*(n-1)

20、!(DEFUN N! (n) (COND (= n 0) 1) (= n 1) 1) (T (* (N!(- n 1) n)Lisp的程序设计也就是定义函数，的程序设计也就是定义函数，lisp的整个程序的整个程序也就是一堆函数也就是一堆函数sspu 王帅例：汉诺塔问题例：汉诺塔问题(DEFUN HANO1(a b c n) (COND (= n 1)(movedisk a c) (T (HANO1 a c b (- n 1) (movedisk a c) (HANO1 b a c (- n 1)(DEFUN movedisk (X Y) (TERPR1) (PRINTC “move disk from ”) (PRINTC X) (PRINTC “to “) (PRINTC Y)盘子所在针起中转作用的针盘子要移到的目标针回车换行函数输出函数sspu 王帅小结小结 Prolog中所有事实和规则都是以谓词形式存放，中所有事实和规则都是以谓词形式存放，Prolog自己提供自己提供了一套匹配回溯的控制策略。可以说用了一套匹配回溯的控制策略。可以说用Prolog建立建立AI程序，推程序，推理部分已经在它内部实现了，我们只要用它规定的方式把各种理部分已经在它内部实现了，我们只