AI程序设计语言课件

《AI程序设计语言课件》由会员分享，可在线阅读，更多相关《AI程序设计语言课件（25页珍藏版）》请在装配图网上搜索。

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

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

3、建立在严格的数学系统上（因为建立在严格的数学系统上（因为AI中的许多推中的许多推理都有坚实的数学基础）理都有坚实的数学基础）表处理功能表处理功能并行处理或分布处理（提高推理速度，实现时并行处理或分布处理（提高推理速度，实现时多采用模拟并行处理技术）多采用模拟并行处理技术）sspu 王帅AI程序设计语言常用的常用的AI AI程序设计语言程序设计语言PrologLispCC+Smalltalksspu 王帅AI程序设计语言PrologPrologProlog是是Programming in Logic用逻辑进行用逻辑进行程序设计的缩写程序设计的缩写第一个第一个Prolog系统是由系统是由Colme

4、rauer及其研及其研究小组于究小组于1972年在法国马赛研制成功年在法国马赛研制成功Prolog是完全基于一阶谓词逻辑基础上的，是完全基于一阶谓词逻辑基础上的，它的所有语句和推理都可以用它的所有语句和推理都可以用Horn子句归子句归结的形式表示，所以它又严格的数学基础结的形式表示，所以它又严格的数学基础sspu 王帅AI程序设计语言Prolog Prolog 的特点的特点逻辑型语言逻辑型语言语句类型简单，只有三种基本形式：事实、语句类型简单，只有三种基本形式：事实、规则、询问规则、询问接近于自然语言，简洁明了，易写易读接近于自然语言，简洁明了，易写易读数据和程序结构一致（都由项构成，便于数据

5、和程序结构一致（都由项构成，便于将将a程序的输出作为程序的输出作为b程序的输入）程序的输入）能自动进行匹配和回溯能自动进行匹配和回溯可大量使用递归可大量使用递归sspu 王帅AI程序设计语言PrologProlog的程序结构的程序结构Prolog程序包括常量段、域段、数据库段、程序包括常量段、域段、数据库段、谓词段、目标段和子句段；另外还可以在谓词段、目标段和子句段；另外还可以在程序首部设置编译指令，在程序中加注释程序首部设置编译指令，在程序中加注释通常，一个通常，一个Prolog程序不一定包括所有段，程序不一定包括所有段，最常用的有子句段、谓词段、域段。如果最常用的有子句段、谓词段、域段。如

6、果需要产生一个可独立执行的程序，还需要需要产生一个可独立执行的程序，还需要有目标段有目标段sspu 王帅AI程序设计语言/* 注释注释 */编译指令编译指令constants 常量说明常量说明Domains 域语句域语句Database 数据库说明数据库说明Predicates 谓词语句谓词语句Goal 目标语句目标语句Clauses 子句语句子句语句sspu 王帅AI程序设计语言子句段子句段是整个程序的核心，所有的事实和规则都是整个程序的核心，所有的事实和规则都在子句段列出，例如在子句段列出，例如ClausesClauses like(Bill,Cindy). like(Bill,Cindy

7、). like(Cindy,Bill). like(Cindy,Bill). like(Bill,dogs). like(Bill,dogs). like(A,C):- like(A,B),like(B,C). like(A,C):- like(A,B),like(B,C). parent(ZhangYi,ZhangEr). parent(ZhangYi,ZhangEr).sspu 王帅AI程序设计语言谓词段谓词段Prolog有许多内部谓词，如有许多内部谓词，如read,write, makewindow等，对内部谓词不需说明等，对内部谓词不需说明在程序中，若定义了自己要用的外部谓词，在程序中

8、，若定义了自己要用的外部谓词，如上例中如上例中like，parent，则必须在谓词段加，则必须在谓词段加以说明，例：以说明，例：PredicatesPredicates like(symbol,symbol) like(symbol,symbol) parent(symbol,symbol) parent(symbol,symbol)sspu 王帅AI程序设计语言域段域段 域就相当于类型说明，如上例中域就相当于类型说明，如上例中parent中的两个参数，中的两个参数，应该是两个人名，则下面的程序更好理解应该是两个人名，则下面的程序更好理解DomainsDomains name=symbol n

9、ame=symbolPredicatesPredicates parent(name,name) parent(name,name) 通过域，可以说明标准域中没有定义的数据结构通过域，可以说明标准域中没有定义的数据结构DomainsDomains articles=book(title,author);horse(name) articles=book(title,author);horse(name) title,author,name=symbol title,author,name=symbolPredicatesPredicates own(name,articles) own(nam

10、e,articles)ClausesClauses own(John,book(ABC,Ding). own(John,book(ABC,Ding). own(John,horse(blacky). own(John,horse(blacky). 标准域：标准域：integer,char,real,ref,string,symbolinteger,char,real,ref,string,symbolsspu 王帅AI程序设计语言目标段目标段目标段输入要解决问题的语句目标段输入要解决问题的语句也可以省略目标段。若省略目标段，则在也可以省略目标段。若省略目标段，则在运行时程序会等待用户输入一个目

11、标，然运行时程序会等待用户输入一个目标，然后才能运行，这时称为外部目标后才能运行，这时称为外部目标若把目标写在目标段中，则程序运行时，若把目标写在目标段中，则程序运行时，自动执行目标，直接显示运行结果，这种自动执行目标，直接显示运行结果，这种目标称为内部目标目标称为内部目标目标段的作用有点类似于主程序目标段的作用有点类似于主程序sspu 王帅AI程序设计语言目标段目标段PredicatesPredicates run(char) run(char)ClausesClauses run(X):- write(“first”), run(X):- write(“first”), readchar(

12、X). readchar(X). run(X):- write(“second”), run(X):- write(“second”), readchar(X). readchar(X). 运行时，会在对话窗口提示输入一个目标，若输入目标运行时，会在对话窗口提示输入一个目标，若输入目标run(X). 则则输出输出first，然后按一个键接着输出，然后按一个键接着输出second，再按一个键，就结束了，再按一个键，就结束了 外部目标运行时，外部目标运行时，Prolog寻找所有解寻找所有解sspu 王帅AI程序设计语言目标段目标段PredicatesPredicates run(char) run

13、(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).运行时，直接显示运行结果，输出运行时，直接显示运行结果，输出first，然后按，然后按一个键，就结束了一个键，就结束了注意：在有内部目标时，注意：在有内部目标时，Prolog只寻找第一个只寻找第一个解解s

14、spu 王帅AI程序设计语言程序执行和匹配法则程序执行和匹配法则Prolog的程序执行过程就是不断地匹配规的程序执行过程就是不断地匹配规则，在匹配过程中对变量实例化，其实就则，在匹配过程中对变量实例化，其实就是谓词归结推理是谓词归结推理在推理过程中，使用的是在推理过程中，使用的是“试探试探-返回返回-再再试试”的回溯方法来对问题求解，也就是深的回溯方法来对问题求解，也就是深度优先的算法，顺着一条路一直往下走，度优先的算法，顺着一条路一直往下走，直到走不下去了，就返回交叉路口，选另直到走不下去了，就返回交叉路口，选另一条路再试一条路再试sspu 王帅AI程序设计语言PredicatesPredi

15、cates 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). tastes(pizza,good). tastes(pizza,good). tastes(dumpling,bad). tastes(dumpling,bad). food

16、(dumpling). food(dumpling). food(pizza). food(pizza).GoalGoal likes(bill,What). likes(bill,What).sspu 王帅AI程序设计语言LispLisp语言语言Lisp是是List Processing 的缩写，是计算机的的缩写，是计算机的表处理语言，处理的都是符号表。表处理语言，处理的都是符号表。1960年年由麦卡锡发明的。由麦卡锡发明的。Lisp语言以语言以1941年年Church提出的提出的演算为理演算为理论基础的，论基础的，演算是与图灵机等价的一种演算是与图灵机等价的一种计算模型计算模型80%的早期

17、的早期AI软件都是用软件都是用Lisp语言写成的语言写成的sspu 王帅AI程序设计语言LispLisp语言基本结构语言基本结构 Lisp语言的程序和数据具有统一的结构，就是符号表达语言的程序和数据具有统一的结构，就是符号表达式（式（S-表达式），表达式），S-表达式的基本组成元素是原子表达式的基本组成元素是原子 原子原子v文字原子：相当于标识符，如文字原子：相当于标识符，如ABCv串原子：引号引起的字符串，如串原子：引号引起的字符串，如“aaa”v数字原子：由正负号、小数点和数字组成数字原子：由正负号、小数点和数字组成 S-表达式表达式v原子是原子是S-表达式表达式v若若S1和和S2是是S-

18、表达式，则（表达式，则（S1 S2）也是）也是S-表达式表达式v例：例：A、（、（A B）、（）、（A （B C）都是正确的）都是正确的S-表达式表达式v但但 （A B C）、（）、（A B）就不是正确的）就不是正确的S-表达式表达式sspu 王帅AI程序设计语言LispLisp语言基本结构语言基本结构表表v是是lisp语言中最常用的结构语言中最常用的结构v表由左括号开始，后跟任意多个由空格隔开表由左括号开始，后跟任意多个由空格隔开的原子或表，最后以右括号结束的原子或表，最后以右括号结束例例: (A)、(A B C)、 (1 (2 (3)都是表都是表v表的结构是嵌套的，表中最外层元素的个数表的

19、结构是嵌套的，表中最外层元素的个数称为表长称为表长例：例： (A (B C) (D) 的表长为的表长为3sspu 王帅AI程序设计语言LispLisp语言的基本函数语言的基本函数 算数运算函数（用前缀方式表示）算数运算函数（用前缀方式表示）v(+ 3 5) (+ (* 3 5) (/ 4 2) 表处理函数表处理函数vCAR 取表的第一个元素取表的第一个元素 (CAR (a b c) 得到得到a (CAR (a b) c) 得到得到(a b) 表示禁止求值表示禁止求值vCDR 返回除第一个元素外所有元素组成的表返回除第一个元素外所有元素组成的表v(CONS S1 S2) 把把S1作为第一元素插入

20、作为第一元素插入S2表中表中v(LIST S1 S2 Sn) 将各参数作为表的元素组成一个表将各参数作为表的元素组成一个表 求值和赋值函数求值和赋值函数v(SET A S) 使第一个参数使第一个参数A的取值等于第二个参数的取值等于第二个参数Ssspu 王帅AI程序设计语言谓词函数：判断是否为真的函数谓词函数：判断是否为真的函数vLisp中，真用中，真用T表示，假用表示，假用NIL表示表示v(EQ A1 A2) 检查检查A1和和A2是否是相同的原子是否是相同的原子v(EQUAL S1 S2) 检查检查S1 和和S2 是否是相同的表达式是否是相同的表达式输入输出函数输入输出函数（READ） 等待输

21、入等待输入（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 王帅AI程序设计语言函数定义函数定义格式格式(DEFUN 函数名函数名(参数参数1 参数参数2 参数参数n) 函数体函数体)lisp中，定义函数最常用的手段是递归定义中，定义函数最常用的手段是递归定义v例：定义阶乘函数例：定义阶乘函数 0!=1 1!=1 n!=n*(n-1)!(DEFUN N! (n) (COND (= n

22、 0) 1) (= n 1) 1) (T (* (N!(- n 1) n)Lisp的程序设计也就是定义函数，的程序设计也就是定义函数，lisp的整个程序的整个程序也就是一堆函数也就是一堆函数sspu 王帅AI程序设计语言例：汉诺塔问题例：汉诺塔问题(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

23、) (PRINTC “to “) (PRINTC Y)盘子所在针起中转作用的针盘子要移到的目标针回车换行函数输出函数sspu 王帅AI程序设计语言小结小结 Prolog中所有事实和规则都是以谓词形式存放，中所有事实和规则都是以谓词形式存放，Prolog自己提供自己提供了一套匹配回溯的控制策略。可以说用了一套匹配回溯的控制策略。可以说用Prolog建立建立AI程序，推程序，推理部分已经在它内部实现了，我们只要用它规定的方式把各种理部分已经在它内部实现了，我们只要用它规定的方式把各种规则、事实写出，然后就可运行求解规则、事实写出，然后就可运行求解 Lisp中也是一样，都以符号表达式这种结构来表示事

24、实和规则中也是一样，都以符号表达式这种结构来表示事实和规则 设计设计AI程序时，也可采用程序时，也可采用C、C+等语言，但这需要我们自己来等语言，但这需要我们自己来控制每一步，需要考虑知识以什么形式、什么结构如何存放等控制每一步，需要考虑知识以什么形式、什么结构如何存放等（可以用数组、链表、树结构、文本文件、数据库等存放知（可以用数组、链表、树结构、文本文件、数据库等存放知识），还需要考虑以什么方式来调用、管理、控制知识的运用识），还需要考虑以什么方式来调用、管理、控制知识的运用v缺点：编程工作量增加缺点：编程工作量增加v优点：有更大的主动权，更大的灵活性，可自由采用一些优点：有更大的主动权，

25、更大的灵活性，可自由采用一些快速的搜索、推理算法，可设计更方便美观的界面，利用快速的搜索、推理算法，可设计更方便美观的界面，利用更多的系统资源更多的系统资源 采用哪种语言进行采用哪种语言进行AI程序设计是根据具体情况决定的程序设计是根据具体情况决定的sspu 王帅AI程序设计语言求三个盘子的汉诺塔，则输入求三个盘子的汉诺塔，则输入(HANO1 a b c 3)输出为输出为Move disk from a to cMove disk from a to bMove disk from c to bMove disk from a to cMove disk from b to aMove disk from b to cMove disk from a to c