AI程序设计语言

sspu王帅人工智能概述前面几章，我们介绍了一些运用AI技术求解问题的一般方法。这些方法可运用于定理证明、自然语言理解、模式识别、专家系统等各个领域。要在计算机上实现，就涉及到计算机语言的问题。严格地讲，可以使用任何计算机语言来实现这些算法。但是AI的主要课题是非数值计算的问题求解和知识处理等复杂问题，主要任务在于完成推理、规划、决策、分析、论证等智能行为，其中包括各种符号处理和表处理等。传统过程性语言不太适合AI方面的程序设计sspu王帅人工智能AI语言的特点具有回溯功能具有模式匹配功能守护功能（保护递归、回溯的现场）过程说明功能（解释推理过程）表达能力强（尤其对各种符号知识）建立在严格的数学系统上（因为AI中的许多推理都有坚实的数学基础）表处理功能并行处理或分布处理（提高推理速度，实现时多采用模拟并行处理技术）sspu王帅人工智能常用的AI程序设计语言PrologLispCC++Smalltalksspu王帅人工智能PrologProlog是ProgramminginLogic用逻辑进行程序设计的缩写第一个Prolog系统是由Colmerauer及其研究小组于1972年在法国马赛研制成功Prolog是完全基于一阶谓词逻辑基础上的，它的所有语句和推理都可以用Horn子句归结的形式表示，所以它又严格的数学基础sspu王帅人工智能Prolog的特点逻辑型语言语句类型简单，只有三种基本形式：事实、规则、询问接近于自然语言，简洁明了，易写易读数据和程序结构一致（都由项构成，便于将a程序的输出作为b程序的输入）能自动进行匹配和回溯可大量使用递归sspu王帅人工智能Prolog的程序结构Prolog程序包括常量段、域段、数据库段、谓词段、目标段和子句段；另外还可以在程序首部设置编译指令，在程序中加注释通常，一个Prolog程序不一定包括所有段，最常用的有子句段、谓词段、域段。如果需要产生一个可独立执行的程序，还需要有目标段sspu王帅人工智能/*注释*/编译指令constants常量说明Domains域语句Database数据库说明Predicates谓词语句Goal目标语句Clauses子句语句sspu王帅人工智能子句段是整个程序的核心，所有的事实和规则都在子句段列出，例如Clauseslike(Bill,Cindy).like(Cindy,Bill).like(Bill,dogs).like(A,C):-like(A,B),like(B,C).parent(ZhangYi,ZhangEr).sspu王帅人工智能谓词段Prolog有许多内部谓词，如read,write,makewindow等，对内部谓词不需说明在程序中，若定义了自己要用的外部谓词，如上例中like，parent，则必须在谓词段加以说明，例：Predicateslike(symbol,symbol)parent(symbol,symbol)sspu王帅人工智能域段域就相当于类型说明，如上例中parent中的两个参数，应该是两个人名，则下面的程序更好理解Domainsname=symbolPredicatesparent(name,name)通过域，可以说明标准域中没有定义的数据结构Domainsarticles=book(title,author);horse(name)title,author,name=symbolPredicatesown(name,articles)Clausesown(John,book(ABC,Ding)).own(John,horse(blacky)).标准域：integer,char,real,ref,string,symbolsspu王帅人工智能目标段目标段输入要解决问题的语句也可以省略目标段。若省略目标段，则在运行时程序会等待用户输入一个目标，然后才能运行，这时称为外部目标若把目标写在目标段中，则程序运行时，自动执行目标，直接显示运行结果，这种目标称为内部目标目标段的作用有点类似于主程序sspu王帅人工智能目标段Predicatesrun(char)Clausesrun(X):-write(“first”),readchar(X).run(X):-write(“second”),readchar(X).运行时，会在对话窗口提示输入一个目标，若输入目标run(X).则输出first，然后按一个键接着输出second，再按一个键，就结束了外部目标运行时，Prolog寻找所有解sspu王帅人工智能目标段Predicatesrun(char)Clausesrun(X):-write(“first”),readchar(X).run(X):-write(“second”),readchar(X).Goalrun(X).运行时，直接显示运行结果，输出first，然后按一个键，就结束了注意：在有内部目标时，Prolog只寻找第一个解sspu王帅人工智能程序执行和匹配法则Prolog的程序执行过程就是不断地匹配规则，在匹配过程中对变量实例化，其实就是谓词归结推理在推理过程中，使用的是“试探-返回-再试”的回溯方法来对问题求解，也就是深度优先的算法，顺着一条路一直往下走，直到走不下去了，就返回交叉路口，选另一条路再试sspu王帅人工智能Predicateslikes(symbol,symbol)tastes(symbol,symbol)food(symbol)Clauseslikes(bill,X):-food(X),tastes(X,good).tastes(pizza,good).tastes(dumpling,bad).food(dumpling).food(pizza).Goallikes(bill,What).sspu王帅人工智能Lisp语言Lisp是ListProcessing的缩写，是计算机的表处理语言，处理的都是符号表。1960年由麦卡锡发明的。Lisp语言以1941年Church提出的λ演算为理论基础的，λ演算是与图灵机等价的一种计算模型80%的早期AI软件都是用Lisp语言写成的sspu王帅人工智能Lisp语言基本结构Lisp语言的程序和数据具有统一的结构，就是符号表达式（S-表达式），S-表达式的基本组成元素是原子原子文字原子：相当于标识符，如ABC串原子：引号引起的字符串，如“aaa”数字原子：由正负号、小数点和数字组成S-表达式原子是S-表达式若S1和S2是S-表达式，则（S1•S2）也是S-表达式例：A、（A•B）、（A•（B•C））都是正确的S-表达式但（A•B•C）、（（A•B））就不是正确的S-表达式sspu王帅人工智能Lisp语言基本结构表是lisp语言中最常用的结构表由左括号开始，后跟任意多个由空格隔开的原子或表，最后以右括号结束例:(A)、(ABC)、(1(2(3)))都是表表的结构是嵌套的，表中最外层元素的个数称为表长例：(A(BC)(D))的表长为3sspu王帅人工智能Lisp语言的基本函数算数运算函数（用前缀方式表示）(+35)(+(*35)(/42))表处理函数CAR取表的第一个元素(CAR‘(abc))得到a(CAR‘((ab)c))得到(ab)‘表示禁止求值CDR返回除第一个元素外所有元素组成的表(CONSS1S2)把S1作为第一元素插入S2表中(LISTS1S2…Sn)将各参数作为表的元素组成一个表求值和赋值函数(SETAS)使第一个参数A的取值等于第二个参数Ssspu王帅人工智能谓词函数：判断是否为真的函数Lisp中，真用T表示，假用NIL表示(EQA1A2)检查A1和A2是否是相同的原子(EQUALS1S2)检查S1和S2是否是相同的表达式输入输出函数（READ）等待输入（PRINTS）输出表达式S的值条件函数(COND(P1S1)(P2S2)…(PnSn))相当于IfP1thenS1ElseifP2thenS2Elseif…ElseifPnthenSnsspu王帅人工智能函数定义格式(DEFUN函数名(参数1参数2…参数n)函数体)lisp中，定义函数最常用的手段是递归定义例：定义阶乘函数0!=11!=1n!=n*(n-1)!(DEFUNN!(n)(COND((=n0)1)((=n1)1)(T(*(N!(-n1))n))))Lisp的程序设计也就是定义函数，lisp的整个程序也就是一堆函数sspu王帅人工智能例：汉诺塔问题(DEFUNHANO1(abcn)(COND((=n1)(movediskac))(T(HANO1acb(-n1))(movediskac)(HANO1bac(-n1)))))(DEFUNmovedisk(XY)(TERPR1)(PRINTC“movediskfrom”)(PRINTCX)(PRINTC“to“)(PRINTCY))盘子所在针起中转作用的针盘子要移到的目标针回车换行函数输出函数sspu王帅人工智能小结Prolog中所有事实和规则都是以谓词形式存放，Prolog自己提供了一套匹配回溯的控制策略。可以说用Prolog建立AI程序，推理部分已经在它内部实现了，我们只要用它规定的方式把各种规则、事实写出，然后就可运行求解Lisp中也是一样，都以符号表达式这种结构来表示事实和规则设计AI程序时，也可采用C、C++等语言，但这需要我们自己来控制每一步，需要考虑知识以什么形式、什么结构如何存放等（可以用数组、链表、树结构、文本文件、数据库等存放知识），还需要考虑以什么方式来调用、管理、控制知识的运用缺点：编程工作量增加优点：有更大的主动权，更大的灵活性，可自由采用一些快速的搜索、推理算法，可设计更方便美观的界面，利用更多的系统资源采用哪种语言进行AI程序设计是根据具体情况决定的sspu王帅人工智能求三个盘子的汉诺塔，则输入(HANO1‘a‘b‘c3)输出为MovediskfromatocMovediskfromatobMovediskfromctobMovediskfromatocMovediskfrombtoaMovediskfrombtocMovediskfromatoc