[计算机软件及应用]人工智能与专家系统第四章 智能程序设计.ppt

第四章 PROLOG语言与智能程序设计,第一节 PROLOG语言的基本知识 第二节 PROLOG程序设计基础 第三节 对回溯的控制 第四节 PROLOG的基本程序段,第一节 PROLOG语言的基本知识,一、PROLOG语言简介 二、PROLOG语言的特点 1、PROLOG语言是一种描述型语言 2、数据和程序是统一的 3、自动实现模式匹配和回溯 4、程序易于编写和阅读 5、语句类型少，语法简明,第一节 PROLOG语言的基本知识,三、PROLOG语言的三种基本语句 1、事实 含义表示对象具有某种性质，或某几个对象之间的关系 形式 谓词（对象1，对象2，对象n），n为任意正整数 裸谓词 注意： 对象之间用逗号分开 全部对象用括号括住 谓词必须以小写字母开头 每个事实都用一个实心句点结束,第一节 PROLOG语言的基本知识,示例 man(zhangsan). is( sun,big). on(book,table). on(f,c). on(c,b). on(b,a). on(e,d). block(a). block(b).,第一节 PROLOG语言的基本知识,最简单的PROLOG程序由两部分组成 谓词部分定义谓词 predicates name(symbol,symbol, ) 字句部分列出所有事实 clauses name(对象1,对象2, ).,第一节 PROLOG语言的基本知识,一个简单的程序 predicates is(symbol,symbol) has(symbol,symbol) clauses is(“王”,”年龄小”). is(“刘”,”个头高”). is(“李”,”有音乐天才”). has(“张”,”书”).,goal: is(“刘”,”个头高”) yes goal: is(“王”,”有音乐天才”) no goal: has(“张”,”书”) yes goal: has(“书”,”张”) no,第一节 PROLOG语言的基本知识,2、规则 含义表示事物成立所要遵循的法则，即事物之间的新关系 形式 事实D if 事实A，事实B，事实C， 事实D :- 事实A，事实B，事实C， 注意： 规则头只能有一个事实 规则体部可有多个事实 规则体中各个事实之间用逗号连接表示“与”关系 每个规则都用一个实心句点结束,第一节 PROLOG语言的基本知识,示例 predicates mother(symbol,symbol) grandmother(symbol,symbol) clauses mother(“钱”,”孙”). mother(“孙”,”李”). mother(“王”,”张”). grandmother(X,Y) if mother(X,Z), mother(Z,Y) goal: grandmother(“钱”,”李”) yes goal: grandmother(“孙”,”张”) no,第一节 PROLOG语言的基本知识,3、询问 含义询问对象之间某种关系是否成立的疑问句 形式 goal: 事实1，事实2，事实3，事实n n为任意正整数 注意： 各个事实之间用逗号连接表示“与”关系 表示：“事实1，事实2，事实3，事实n”同时成立吗？,第一节 PROLOG语言的基本知识,四、项 1、项的定义 项= 常量 原子：对象的名字、谓词函数名（小写字母开头） 数字 变量 暂时不能命名或不需要命名的对象 以大写字母开头 匿名变量：on(_,a); mother(_,”李”） 自由变量和约束变量,第一节 PROLOG语言的基本知识,结构 又称复合项，是由一组其他对象组成的单个对象 包括： 函数项：readchar(X)、mother(“李”, “孙”） 表：a,b,c 表达式：2*3+17 结构的嵌套 accident(date(year,month,day),who,place),第一节 PROLOG语言的基本知识,2、项的匹配规则 （1）若A、B是项，A是自由变量，则B无论是何值，A可以被B匹配 （2）常量与自身匹配成功 （3）结构的每一对应成分匹配，则匹配成功,第一节 PROLOG语言的基本知识,五、表 1、概念 表是具有相同类型对象的有序集合 如：1,2,3、a,b,c、a,b(f,c),d、 2、表头、表尾 表头表中第一个元素 表尾表中的其余部分，可以是另一张表 3、表的匹配 表中的常量完全相同才匹配 表中的变量可与任何对象匹配 表头只与一个分量匹配，表尾可与一个表匹配,第二节 PROLOG程序设计基础,一、PROLOG程序的组成 1、前提部分（条件）包括有关的事实和规则 2、问题部分（目标）问题求解的目标结果 二、PROLOG程序的设计步骤 1、说明事实 2、定义规则 3、明确目标,第二节 PROLOG程序设计基础,三、判定规则中变量值的原则 1、在同一条规则中，所有相同名字的变量具有相同的内容 2、如果规则头中的变量被约束了，则规则体中的同名变量也被约束为相同的内容 3、当规则头中的变量未被约束时，如果规则体中的同名变量被约束了，则规则头中的同名变量和规则体中的其他同名变量也被约束为相同的内容 4、如果多条规则中有相同名字的变量，则这些同名变量不相关 5、只有规则在使用时，规则中的变量才被约束,第二节 PROLOG程序设计基础,四、PROLOG程序的目标求解过程 1、匹配与回溯 predicates person(symbol, symbol) clauses person(z, m). person(y, w). person(c, w). person(l, m). goal: person(X,m) X=z X=l,第二节 PROLOG程序设计基础,predicates likes(symbol, symbol) clauses likes(zhang, flower). likes(zhang, wine). likes(wang, wine). likes(wang, zhang). goal: likes(wang, X) X=wine X=zhang goal: likes(zhang,X), likes(wang,X) X=wine,第二节 PROLOG程序设计基础,2、包含多个子目标的问题求解过程 goal: 事实1，事实2，事实n 3、示例 dish(pork). dish(fish). main(rice). main(bread). fruit(apple). fruit(orange). meal(D, M, F) if dish(D), main(M), fruit(F). goal: meal(D, M, F),第二节 PROLOG程序设计基础,五、规则的递归描述 1、概念 在规则中，将自身作为一个成份，则称此规则是递归的 如： on(a4, a3). on(a3, a2). on(a2, a1). top(An, A1) if on(An, A1). top(An, A1) if on(A2, A1), top(An, A2). goal: top(a4, a1),第二节 PROLOG程序设计基础,2、示例 （1）求,power(0,1). power(N,Y) if N1=N-1, power(N1, Y1), Y=N*Y1 goal: power(2, Y) Y=2 (2) 求表的长度 length(, 0). length(HT, X) if length(T, X1), X=X1+1 goal: length(a,b,c, X) X=3,第二节 PROLOG程序设计基础,（3）x是否是表中的一个 member(X, X_). member(X, _Y) if member(X, Y). goal: member(b, a,b,c) yes (4) 求表中最后一个元素 last(X, X). last(YZ, P) if last(Z, P). goal: last(a,b,c, Y) Y=c,第二节 PROLOG程序设计基础,（5）表的连接 append(, L, L) . append(HL1, L2, HL3, ) if append(L1, L2, L3) goal: append(L1, L2, a,b,c),第三节 对回溯的控制,一、截断 1、示例 predicates person(symbol, symbol) clauses person(z, m). person(y, w). person(c, w). person(l, m). goal: person(A,_), person(B,_), AB goal: person(A,_), person(B,_), AB, ! A=z, B=y,A=z,B=y A=z,B=c A=z,B=l A=y,B=z A=y,B=c A=y,B=l A=c,B=z A=c,B=y A=c,B=l A=l,B=z A=l,B=y A=l,B=c,第三节 对回溯的控制,2、“!”的概念 “!”表示截断，系统内部谓词，不带任何变元 作为目标，求解立即成功，即该谓词总是取真值 成功后，不能回溯，即穿过!的回溯是不可能的 goal: h1, h2, !, h3, h4,第三节 对回溯的控制,predicates person(symbol, symbol) clauses person(z, m). person(y, w). person(c, w). person(l, m). goal: person(A,_), person(B,_), AB goal: person(A,_), person(B,_), AB, ! goal: person(A,_), !, person(B,_), AB goal: person(A,_), person(B,_), !, AB goal: !, person(A,_), person(B,_), AB,12 个解 1个解 3个解 无解 12个解,第三节 对回溯的控制,二、失败 1、示例 predicates person(symbol, symbol) output clauses person(z, m). person(y, w). person(c, w). person(l, m). output if person(X,_), write(“姓名:”, X), nl,goal: output 姓名：z yes goal: person(X,_),write(“姓名：”），nl 姓名：z 姓名：y 姓名：c 姓名：l,第三节 对回溯的控制,predicates person(symbol, symbol) output clauses person(z, m). person(y, w). person(c, w). person(l, m). output if person(X,_), write(“姓名:”, X), nl, fail goal: output 姓名：z 姓名：y 姓名：c 姓名：l no,第三节 对回溯的控制,2、”fail”的概念 是系统内部谓词，不带任何变元，表示失败 作为目标，求解立即失败，引起回溯 goal: h1, h2, fail, h3 3、!与fail相结合的例子 not-equal(X,Y) if equal(X,Y), !, fail. not-equal(X,Y). equal(X,X). goal: not-equal(6,7) yes goal: not-equal(6,6) no,第四节 PROLOG的基本程序段,一、常量段 用来说明符号常量 由“constant”标识 在常量说明中，系统不区分大小写 可有多个常量段 每个常量要先定义后使用 例如： constant pi=3.14159 zero=0 num=50,第四节 PROLOG的基本程序段,二、域段由domains标识 1、标准域 char标准ASCII码中任意一个字符，被单引号括起来 integer real string由双引号括起来的字符序列 symbol 以小写字母开始，由若干字母、数字、下划线组成的序列 双引号括起来的字符序列 若谓词参数采用标准域，则域段可省略 若谓词参数采用非标准域，则需在域段中说明,第四节 PROLOG的基本程序段,2、表域 =* 例如： domains myint=integer mylist=myint* predicates member(myint, mylist) clauses member(X,X_). member(X,_Y) if member(X,Y),domains mylist=integer* predicates member(integer, mylist),第四节 PROLOG的基本程序段,3、复合对象域 =(, , ,) 例如： domains person=person(name,address) name=name(first,last) address=address(street,city,state) street=street(number,streetname) city,state,streetname=string first,last=string numb