AI第四章 PROLOG语言.ppt

2020 3 12 0 第四章PROLOG语言 4 1逻辑程序设计概述4 2Prolog语言概述Prolog实验环境在线资源4 3合一与控制流4 4表处理基本概念表处理及其应用举例 2020 3 12 1 4 1逻辑程序设计概述 一 LISP PROLOG是常用的人工智能语言 LISP 函数程序设计语言 20世纪50年代后期 PROLOG 逻辑程序设计语言 20世纪70年代中期 目前C C 使用比较多 专家系统开发语言或开发工具 如 CLIPS语言 Lisp语言创始人McCarthy 2020 3 12 2 二 逻辑程序设计语言 说明性语言 1 Prolog是唯一广泛使用的逻辑程序设计语言 易于表达人的思维 主要应用于专家系统 规划 自然语言理解 机器定理证明等人工智能相关问题的求解 2 区别于命令式语言和函数式语言 逻辑式语言都支持说明性程序设计风范 1 根据问题约束的高层描述来构建程序 2 告诉计算机 什么是真的 和 需要做什么 而不是 怎样做 3 允许程序员集中精力对待求解问题 一个封闭的世界 的描述 而不是写一些诸如 下一步做什么 之类的底层算法指令 2020 3 12 3 例4 1 水平线与垂直线问题 使用两个谓词 vertical 2和horizontal 2 vertical line point X Y point X Z horizontal line point X Y point Z Y vertical line point 1 1 point 1 3 yes 事实 查询 目标 horizontal line point 1 1 point 2 Y Y 1 no horizontal line point 2 3 P P point G434 3 no 什么是真的 需要做什么 2020 3 12 4 例4 2 求解以下六个英语单词的纵横字谜问题 abalone abandon anagram connect elegant enhance 事实 规则 2020 3 12 5 a a b l o n e a n a g r a m o c n n e c t a a d n e e e a t h n e a a d n b o n l e e a t n g n e h n e c a a a o e a a r m c n e t 查询 目标 2020 3 12 6 一 所有的Prolog语句由项 term 构成1 常量原子 atom Prolog的符号值以小写字母开始的一串字母 数字 下划线或用单引号界定的一串任何可打印的ASCII字符 整数2 变量以大写字母开始一串字母 数字和下划线 下划线 表示匿名变量 注意与命令式语言中变量的区别 3 结构 谓词 复杂项 谓词演算的原子命题functor term 1 term n 算符 项1 项n 4 2Prolog语言概述 2020 3 12 7 二 Prolog语言及其基本结构 Prolog的基本语句仅有三种 即事实 规则和目标 Prolog是陈述性语言 一旦给它提交必要的事实和规则之后 Prolog就使用内部的演绎推理机制自动求解程序给定的目标 而不需要在程序中列出详细的求解步骤 事实事实用来说明一个问题中已知的对象和它们之间的关系 在Prolog程序中 事实由谓词名及用括号括起来的一个或几个对象组成 谓词和对象可由用户自己定义 例如 likes bill book 是一个名为like的关系 表示对象bill和book之间有喜欢的关系 2020 3 12 8 规则由几个互相有依赖性的简单句 谓词 组成 用来描述事实之间的依赖关系 从形式上看 规则由左边表示结论的后件谓词和右边表示条件的前提谓词组成 bird X animal X has X feather 表示凡是动物并且有羽毛 那么它就是鸟 目标 问题 目标的结构与事实或规则相同 可以是一个简单的谓词 也可以是多个谓词的组合 目标分内 外两种 内部目标写在程序中 外部目标在程序运行时由用户手工键入 student john 表示 john是学生吗 2020 3 12 9 三 Prolog运行机理 1 自由变量与约束变量自由变量即无值的变量 约束变量即有值的变量 2 匹配合一两谓词可匹配合一 指谓词名相同 参数个数和类型对应相同 另 若两个均为常量 则必须相同 若两个为约束变量 则两约束值相同 若一个为常量 一个为变量 则约束值与常量相同 至少有一个自由变量 例 p ob1 ob2 z p ob1 X Y 只有当1 X被约束为 ob2 2 Y Z的约束值相同或至少有一个自由变量时 才可匹配合一 2020 3 12 10 3 通过提问查询知识库 使用分号 查询多个解 multipleanswers 分号有特定的含义 表示结束当前合一 回溯查找其它可满足的解 2020 3 12 11 四 Prolog实验环境 SWI Prolog 推荐使用 http www swi prolog org 安装文件 注意顺序安装 SWI PrologforMS Windows version5 4 7 SWI Prolog Editor 2020 3 12 12 不安装SWI Prolog Editor 2020 3 12 13 2020 3 12 14 2020 3 12 15 在线资源 1 LearnPrologNow byPatrickBlackburn JohanBos andKristinaStriegnitzhttp www learnprolognow org 2 ON LINEGUIDETOPROLOGPROGRAMMINGbyROMANBART Khttp ktiml mff cuni cz bartak prolog index html提供基于浏览器的Prolog程序在线测试 TestZone W Prolog 2020 3 12 16 合一项的合一归结基于合一编程控制流回溯cut 4 3合一与控制流 2020 3 12 17 一 项的合一 1 项 Term 常量 变量 结构 2 Prolog中 两个项何时匹配 两个项相等 abandon和abandon 原子45和45 整数X和X 变量point 1 2 和point 1 2 结构 变量可以实例化 使两个项合一woman X 和woman vincent X vincent 2020 3 12 18 3 何时可以合一 如果Term1和Term2是常量 那么当且仅当Term1和Term2是相同的原子或整数 如果Term1是变量 Term2是任何类型的项 那么Term1实例化为Term2 注 如果Term2也是变量 互相实例化 共享值 如果Term1和Term2都是结构 两者合一 当且仅当 a 两者有相同的算符 谓词 b 两者对应的参数匹配 即能够递归地合一 c 变量实例化必须保持一致性 当满足前面三种情况时 两者项合一 2020 3 12 19 注意 Prolog中的相等是基于 合一 定义的 内部共享变量 2020 3 12 20 二 基于合一编程 例4 3 长篇小说问题 2020 3 12 21 2020 3 12 22 匹配失败 2020 3 12 23 2020 3 12 24 2020 3 12 25 DRNO Title 2020 3 12 26 DRNO Title 匹配失败 2020 3 12 27 DRNO Title 310 Length 2020 3 12 28 DRNO Title 310 Length 2020 3 12 29 三 Prolog控制流的设计问题 1 思考 基于合一编程的实例中 采用哪种搜索策略搜索 搜索方向 搜索类型 目标 合一失败 如何控制程序继续进行求解问题 需要搜索更多的解 使用分号 时 如何控制程序继续进行求解问题 结论 控制流 Prolog采用基于目标导向的深度优先搜索策略 回溯是Prolog内部最基本的自动的控制流机制 2020 3 12 30 目标导向的搜索有效地裁减了无关的搜索路径 推理方向 2020 3 12 31 程序运行期间 当某一个子目标不能满足 即谓词匹配失败 时 控制就返回到前一个已经满足的子目标 若存在 并撤销其有关变量的约束值 然后再使其重新满足 成功后 再继续满足原子目标 若失败的子目标前再无子目标 则控制返回到该子目标的上一级目标 即该子目标谓词所在规则的头部 使它重新匹配 2 回溯 2020 3 12 32 C X G206 seattle G206 例4 4 使用与 或树解释合一失败后回溯搜索 失败并回溯 cold seattle 2020 3 12 33 C X G206 seattle G206 rochester G206 例4 4 使用与 或树解释合一失败后回溯搜索 2020 3 12 34 X G206 Y G207 a X c Z a Y 例4 5 使用与 或树解释利用回溯搜索多个解 解1 2020 3 12 35 X G206 Y G207 a X c Z a Y b Y 解2 解1 例4 5 使用与 或树解释利用回溯搜索多个解 2020 3 12 36 X G206 Y G207 a X c Z a Y b Y 解2 解1 b X c Z a Y 解3 例4 5 使用与 或树解释利用回溯搜索多个解 2020 3 12 37 例4 5 使用与 或树解释利用回溯搜索多个解 X G206 Y G207 a X c Z a Y b Y 解2 解1 b X c Z a Y 解3 b Y 解4 2020 3 12 38 例4 6 求解以下六个英语单词的纵横字谜问题 abalone abandon anagram connect elegant enhance 2020 3 12 39 a a b l o n e a n a g r a m o c n n e c t a a d n e e e a t h n e a a d n b o n l e e a t n g n e h n e c a a a o e a a r m c n e t 2020 3 12 40 2020 3 12 41 2020 3 12 42 2020 3 12 43 3 递归 在Prolog中 当某个谓词的目标中包含了此谓词本身时 Prolog将进行递归调用 递归定义都包括两个部分 边界条件与递归部分 baseclause recursiveclause 2020 3 12 44 e X b Y 例4 7 使用与 或树分析递归过程 求解问题 2020 3 12 45 e X b Y e X b Y d Z d X 例4 7 使用与 或树分析递归过程 求解问题 2020 3 12 46 e X b Y e X b Y d Z d Z d X b Y c Z 例4 7 使用与 或树分析递归过程 求解问题 2020 3 12 47 4 Prolog程序的顺序性 为什么Prolog不是纯的逻辑式编程语言 Prolog程序查询目标时按照特定的顺序自动执行 Horn子句的排列顺序会影响到Prolog程序的语义 自上而下搜索知识库中的Horn子句 从左向右搜索规则体中的各个项 使用回溯机制尝试新的搜索 2020 3 12 48 例如 修改程序中子句的顺序 从逻辑 说明 的角度考虑 程序的含义有无变化 从过程的角度考虑 程序的含义有无变化 2020 3 12 49 重新实例化 5 Cut 截断 Prolog为什么需要引入cut机制 当确信在谓词中的某一点只有一个答案 或者没有答案时 用cut可提高效率当想让某个谓词强制失败 而不让它去寻找更多的答案时 也可用cut 2020 3 12 50 Prologcut 截断 阻止回溯 机制使用内部无参谓词 可以作为子目标放在规则子句的体内 解释 程序调用cut总是成功 当某个子目标失败回溯时 不允许越过 回溯 a b c d e f g h I j a b c d e f g h I j a b c d e f g h I j 立即失败 2020 3 12 51 关于截断谓词 的语义 若将 插在子句体内作为一个子目标 总是立即成功 若 位于子句体的最后 则它就阻止对它所在子句的头谓词的所有子句的回溯访问 而让回溯跳过该头谓词 子目标 去访问前一个子目标 若有 若 位于其他位置 则当其后发生回溯且回溯到 处时 就在此处失败 且 还使它所在子句的头谓词 子目标 整个失败 即阻止再去访问头谓词的其余子句 若有 即迫使系统直接回溯到该头谓词 子目标 的前一个子目标 若有 2020 3 12 52 例4 8 1 X 1 X 2 X 3 X 2020 3 12 53 例4 9 1 X 1 X 2020 3 12 54 例4 10 1 X 1 Y 2 Y 3 Y 0 X 0 Y 2020 3 12 55 问题 如何在实践中使用cut机制 例 2020 3 12 56 绿色截断 greencut 加入cut后 不改变程序的逻辑含义 效率更高 红色截断 redcut 加入cut后 改变程序的逻辑含义 应当尽量避免 2020 3 12 57 6 fail是一个无参数的内部谓词 当程序调用该谓词时 立即失败并强制回溯 与cut结合 增加程序编写的灵活性 可以在一般规则中 增加特殊性 例 要描述一个人是很健壮的 其条件是 如他没有心脏病 没有肺病 又不是近视眼等 开始写的程序 strong X heart disease X fail 若X有心脏病 则匹配目标失败 strong X tuberculosis X fail 若X有肺病 则匹配目标失败 strong X nearsight X fail 若X近视眼 则匹配目标失败 依次强制回溯 strong X 此句将病人也会判为健康的 2020 3 12 58 程序改为 strong X heart disease X fail 若X有心脏病 则匹配目标失败 回溯遇到 失败 strong X tuberculosis X fail 若X有肺病 则匹配目标失败 回溯遇到 失败 strong X nearsight X fail 若X近视眼 则匹配目标失败 回溯遇到 失败 strong X 若到此句说明上述疾病都没有 病人判为健康 cut failcombination 2020 3 12 59 4 4表处理一 基本概念 1 表 List 有限的元素序列 由方括号 之间由逗号隔开的有序元素组成 表中的元素可以是原子 结构 或任何其它的项 包括表在内 1 2 3 4 5 2020 3 12 60 任何非空的表 表头 head 表尾 tail 表头 表的第一个元素 表尾 除第一个元素 表的其它元素组成的表 2 Prolog内部谓词 用于将表分解为表头和表尾 灵活使用 是写好Prolog表处理程序的关键 2020 3 12 61 谓词 的使用 2020 3 12 62 二 成员 member操作判断任意给定的元素是否是表的成员 2020 3 12 63 从过程的观点分析 2020 3 12 64 三 连接 append L1 L2 L3 如果表L3是L1和L2的连接 则满足 2020 3 12 65 1 定义append L2 L3 T L2 输入 L3 结果 2020 3 12 66 从过程的观点分析 2020 3 12 67 2 使用append 将一个表分解为两个连续的子表 append X Y a b c d 2020 3 12 68 定义一个表的前缀 a b c d 的前缀是 a a b a b c a b c d prefix P L append P L suffix S L append S L 思考 2020 3 12 69 表倒置 reverse reverse X Y L reverse Y L1 append L1 X L 2020 3 12 70 四 举例1 八皇后问题在8X8格的国际象棋上摆放八个皇后 使其不能互相攻击 即任意两个皇后都不能处于同一行 同一列或同一斜线上 问有多少种摆法 2020 3 12 71 双坐标表示方法 12345678X 87654321 Y X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 X6 Y6 X7 Y7 X8 Y8 2020 3 12 72 2 骑士周游问题 Knight stourproblem 在国际象棋中 骑士的移动线路都是L形的 在一个方向上走两格 在竖直方向上走一格 Knight stour问题是 称为骑士的棋子在一个空的棋盘上行进 能否在棋盘上的每个方格都走一次且仅走一次 2020 3 12 73 注意 外部的方格比靠近棋盘中心的方格更麻烦 事实上 最麻烦的或难以接近的方格就是四个角落 最直观的想法是应该先把骑士移动到最难到达的方格 将最容易到达的空出来 这样 在接近周游末期棋盘变得拥挤时 成功的机会就更大 开发一个 可达性试探法 根据每个方格的可到达程度将它们分类 然后总是把骑士移动到最难到达的那个方格 要符合骑士的L形移动规则 骑士周游问题 2020 3 12 74 骑士周游问题 某方格周围有多少个可到达的方格 就在此方格填上相应的数字 在一个空棋盘上 每个中心方格定为8 每个角落方格定为2 其他的方格为3 4或6 如下所示 在任何时候 骑士都应该移动到具有最低可达数的方格 如果满足此条件的方格不止一个 骑士可以移动到其中的任何一个方格 2344443234666643468888644688886446888864468888643466664323444432 2020 3 12 75 3X3的骑士周游问题 Knight stourproblem 2020 3 12 76 4 5实验题目 实验1 野人和传教士过河问题假设有三 N 个传教士和三 N 个野人同在河的左岸 他们都要到河对岸去 河里只有一条渡船 他们都会划船 但每次渡船至多只能乘坐两 K 人 K N 如果在任何一边河岸上的野人数量超过传教士 野人就会吃掉传教士 问怎么才能用船将传教士和野人从左岸都渡到右岸 又不会发生传教士被吃的事件 分析 这是个典型的状态图搜索问题 所以我们首先需要解决的问题就是使用Prolog的数据结构表达两岸的状态 以及对这些状态可能的操作 2020 3 12 77 我们用下面的复合结构来表达问题的某个状态 左岸牧师数 左岸野人数 右岸牧师数 右岸野人数 船的位置 上面的结构中 船的位置为0表示船在左岸 为1表示在右岸 一开始 所有的人都在左岸 所以初始状态如下 3 3 0 0 0 而目标状态则是 0 0 3 3 1 当然 这里只是为了方便起见 才使用了上面的结构 实际上是没有必要包括右岸的人数的 因为可以通过左岸的人数算出右岸的人数来 不过我们这里所选用的数据结构也有其优点 它可以使程序更加容易理解 2020 3 12 78 船上所能够载人的状态就是可能的操作 用谓词move 2表示 move 1 0 表示船上有一位牧师 没有野人 move 0 1 move 0 2 move 2 0 move 1 1 有了上面的表达状态的数据结构以及移动的方法 我们还需要判断状态是否合法 即判断牧师与野人的人数是否会造成牧师受到伤害 另外还要设计状态转移前后相邻状态的转换规则 随后利用广度优先或深度优先进行求解 2020 3 12 79 实验2 八数码问题 很显然 这是一个状态图搜索问题 我们对图中方块的移动可以想象为图中的一条路径 这条路径把两个相邻的状态连接在一起 例如 2020 3 12 80 上表中 9代表空位 可以看出 每一个状态都有它相邻的一些状态 为了能够让Prolog自动地找出从初始状态到目标状态的路径 首先要能够找出某一个状态的相邻的状态 如果能把相邻的状态找出来 那么我们的状态图就做好了 使用过别的程序语言的同学很容易想到使用二维数组来储存方格的状态 但是很可惜Prolog没有提供数组的功能 所以在此我们使用列表来储存方格的状态 目标状态可以写成 1 2 3 4 5 6 7 8 9 而与之相邻的状态分别为 1 2 3 4 5 6 7 9 8 与 1 2 3 4 5 9 7 8 6 由于使用的是列表储存的方格的状态 那么就必须重新定义相邻方格的信息 我们使用link 2谓词来完成这个任务 2020 3 12 81 link 1 2 link 2 3 link 4 5 link 5 6 link 7 8 link 8 9 link 1 4 link 4 7 link 2 5 link 5 8 link 3 6 link 6 9 注意左面的数字不是表示方格中的数字 而是表示方格的位置 例如 link 1 2 表示第一个方格与第二个方格相邻 当为目标状态时 方格的位置与其数