哈工大人工智能复习题.pdf

1 第一章 人工智能概述 1 请举例说明人工智能这门科学研究的内容 特点 难点 研究目标 答 研究的内容 启发式搜索理论 搜索的方法很多 如回溯 图搜索 启发式等等 主要是给定一些经验做指导提高搜索 效率 该方面的研究已经有了比较成熟的技术 各种推理方法 常识推理有知识不完全 不够用等问题 如鸟会飞 但是鸵鸟不会飞 知识的模型化和表示方法 知识表示很重要 方法主要有逻辑 产生式 语义网络 框架等 现在还不能完全说清 楚知识表示到底是什么 人工智能系统结构及语言 Lisp 语言主要在美国 Prolog 语言主要在欧洲使用比较广泛 机器学习 当前系统大多用归纳的学习 依赖知识库的学习 没有很成熟的方法 神经网络 遗传 算法等理论的应用也在探讨之中 特点 人工智能是一门知识的科学 以知识为对象 研究知识的获取 表示和使用 人工智能的系统过程是 数据处理 知识处理 数据 符号 符号表示的是知识而不 是数值 数据 问题求解过程有启发 有推导 人工智能是引起争论最多的科学之一 难点 知识获取 知识表示 机器学习 实现时的规模扩大问题 应用前景 封闭的专家系统 机器学习问题 研究目标 远期目标 揭示人类智能的根本机理 用智能机器去模拟 延伸和扩展人类智能 近期目标 建造智能计算机代替人类的部分智力劳动 2 请举例说明人工智能有哪些研究及应用领域 参考教材 P12 18 3 人工智能研究有哪此不同学派 它们的基本思想是什么 你认同哪一种观点 为什么 参考教材 P18 20 第二章 知识表示 1 设有如下语句 请用相应的谓词公式分别把他们表示出来 a 有的人喜欢梅花 有的人喜欢菊花 有的人既喜欢梅花又喜欢菊花 b 有的人每天下午都去打篮球 c 新型计算机速度又快 存储容量又大 d 不是每个计算机系的学生都喜欢在计算机上编程序 e 凡是喜欢编程序的人都喜欢计算机 答 a 定义谓词 LIKE x y 表示 x 喜欢 y PERSON x x PERSON x LIKE x 梅花 y PERSON y LIKE y 菊花 x PERSON x LIKE x 梅花 LIKE y 菊花 2 b PLAY x y 表示 x 打 y AFTERNOON t 表示 t 是下午 x t AFTERNOON t PLAY x 篮球 c Computer x x 是计算机 NewType x x 是新型的 HaveSpeed x y x 的速度是 y High y y 是高的 HaveMemory x z x 的存储容量是 z Large z z 是大的 Computer x NewType x High y HaveSpeed x y Large z HaveMemory x z d Computer x x 是计算机系的 Student x x 是学生 Like x y x Computer x Student x Like x programming e x Person x Like x programming Like x computer 2 请画图说明产生式系统的基本结构及其各组成部分 请参考教材 P38 3 设有如下问题 八数码难题 a 在一个 3 3 的方框内放有 8 个编号的小方块 b 紧邻空位的小方块可以移入到空位上 c 通过平移小方块可将某一布局变换为另一布局 请用产生式规则表示移动小方块的操作 解 空格向上移 IF 空格上方有数字 THEN 空格向上移 4 请把下列命题用一个语义网络表示出来 1 树和草都是植物 2 树和草都有叶和根 3 水草是草 且生长在水中 4 果树是树 且会结果 5 梨树是果树中的一种 它会结梨 5 请对下列命题分别写出它们的语义网络 a 每个学生都有一台计算机 b 高老师从 3 月到 7 月给计算机系学生讲 计算机网络 课 c 学习班的学员有男 有女 有研究生 有本科生 d 创新公司在科海大街 56 号 刘洋是该公司的经理 他 32 岁 硕士学位 e 红队与蓝队进行足球比赛 最后以 3 2 的比分结束 第三章 确定性推理 1 下列子句是否可以合一 如果可以 写出最一般合一 3 a P x B B 和 P A y z b P g f v g u 和 P x x c P x f x 和 P y y d P y y B 和 P z x z 解 1 P x B B 和 P A y z 可以合一 Mgu A x B y B z 2 P g f v g u 和 P x x 不可以合一 3 P x f x 和 P y y 不可以合一 4 P y y B 和 P z x z 可以合一 Mgu B x B y B z 2 将下面的公式化成子句集 P Q R P R 解 P Q R P R P Q R P R P Q R P R P R Q R P R 建立子句集 S P R Q R P R 3 Herbrand 定理解决了一个什么意义上的问题 答 将无限的不可数的论域上的问题 转化成为在可数的 H 论域上讨论的问题 该定理在理论上保证 了归结原理的可靠性 4 设 S P x Q f x y 试写出 H 域上的元素 并写出 S 的一个基例 解 H a f a f f a S 中子句的一个基例为 P a Q f a f a 或者 P f a Q f f a a 5 设已知 a 如果 x 是 y 的父亲 y 是 z 的父亲 则 x 是 z 的祖父 b 每个人都有一个父亲 试用归结演绎推理证明 对于某个 u 一定存在一个人 v v 是 u 的祖父 解 定义谓词 father x y 表示 x 是 y 的父亲 Grandfather x y 表示 x 是 y 的祖父 已知条件的谓词公式表示如下 1 1 x y z father x y father y z Grandfather x z 2 y x father x y 结论的谓词公式表示 u v Grandfather v u 将结论取反并入条件形成公式集 F x y z father x y father y z Grandfather x z y x father x y u v Grandfather v u 将公式集 F 化为子句集 S father x y father y z Grandfather x z father f w w 4 Grandfather f u u 对子句集 S 进行归结 对于子句 father x y father y z Grandfather x z 可以先在内部进行合一 6 用归结法证明 存在一个绿色物体 如果有如下条件存在 a 如果可以推动的物体是蓝色的 那么不可以推动的物体是绿色的 b 所有的物体或者是蓝色的 或者是绿色的 但不能同时具有两种颜色 c 如果存在一个不能推动的物体 那么所有的可推动的物体是蓝色的 d 物体 O1 是可以推动的 e 物体 O2 是不可以推动的 解 把上述条件化为逻辑表达式 1 x pushable x blue x x pushable x green x 2 x blue x green x blue x green x 3 x pushable x x pushable x blue x 4 pushable O1 5 pushable O2 将结果命题否定 x green x 将条件表达式和结果命题化为子句形 由条件 1 1 pushable x green x 2 blue a pushable y green x 由条件 2 3 green x blue x 4 green x blue x 由条件 3 5 pushable x pushable y blue y 由条件 4 6 pushable O1 由条件 5 7 pushable O2 由结论 8 green x 归结 9 blue x pushable y 2 8 10 blue x 7 9 11 blue x 4 8 12 10 11 7 已知事实公式为 x y z Gt x y Gt y z Gt x z u v Succ u v Gt u v x Gt x x 求证 Gt 5 2 试判断下面的归结过程是否正确 若有错误应如何改进 5 8 我们来考虑下列一段知识 a Tony Mike 和 John 属于 Alpine 俱乐部 b Alpine 俱乐部的每个成员不是滑雪运动员就是一个登山运动员 c 登山运动员不喜欢雨而且任一不喜欢雪的人不是滑雪运动员 d Mike 讨厌 Tony 所喜欢的一切东西 而喜欢 Tony 所讨厌的一切东西 e Tony 喜欢雨和雪 以谓词演算语句的集合表示这段知识 使得这些语句适合一个逆向的基 于规则的演绎系统 若想利用基于规则的逆向推理回答问题 有没有 Alpine 俱乐部的一个成员 他是一个登山运动员但不是一个滑雪运动员呢 问 题应该如何表示呢 答 我们用 Skier x 表示 x 是滑雪运动员 Alpinist x 表示 x 是登山运动员 Alpine x 表示 x 是 Alpine 俱乐部的成员 问题用谓词公式表示如下 已知 1 Alpine Tony 2 Alpine Mike 3 Alpine John 4 x Alpine x Skier x Alpinist x 5 x Alpinist x Like x Rain 6 x Like x Snow Skier x 7 x Like Tony x Like Mike x 8 x Like Tony x Like Mike x 9 Like Tony Snow 10 Like Tony Rain 目标 x Alpine x Alpinist x Skier x 6 9 一个积木世界的状态由下列公式集描述 ONTABLE A CLEAR E ONTABLE C CLEAR D ON D C HEAVY D ON B A WOODEN B HEAVY B ON E B 下列语句提供了有关这个积木世界的一般知识 每个大的蓝色积木块是在一个绿色积木块上 每个重的木制积木块是大的 所有顶上没有东西的积木块都是蓝色的 所有木制积木块是蓝色的 以具有单文字后项的蕴涵式的集合表示这些语句 绘出能求解 哪个积木块是 在绿积木块上 这个问题的一致解图 用 B 规则 解 知识的谓词表示 x y BIG x BLUE x ON x y GREEN y x HEAVY x WOODEN x BIG x x CLEAR x BLUE x x WOODEN x BLUE x 目标 x y GREEN y ON x y 对规则 Skolem 化 对目标用对偶形式 Skolem 化后 整理得 事实 ONTABLE A CLEAR E ONTABLE C CLEAR D ON D C HEAVY D ON B A WOODEN B HEAVY B ON E B 规则 r1 BIG x1 BLUE x1 ON x1 f x1 r2 BIG x2 BLUE x2 GREEN f x2 r3 HEAVY x3 WOODEN x3 BIG x3 r4 CLEAR x4 BLUE x4 r5 WOODEN x5 BLUE x5 目标 GREEN y ON x y 7 容易验证 只有一个解图是一致的 其合一复合为 B x f B y 带入目标公式 得到解答 GREEN f B ON B f B 其含义是 积木 B 在绿色积木上边 这里的 f B 可以理解为 B 下面那个积木 10 某问题由下列公式描述 1 s P s 2 s P g s 3 x s y P s Q b x s H y 4 x s Q b x s Q b x g s 5 x s y P s Q b x y 求证 x H x 请用基于规则的逆向演绎系统求解 x H x 成立 要求给出一 个求得的一致解图 并说明为什么它是一致的 给出目标的解答 答 对事实和规则进行 skolem 化 1 s P a 2 s P g s P g s 3 x s y P s Q b x s H y P s Q b c s H f s 4 x s Q b x s Q b x g s Q b x s Q b x g s 5 x s y P s Q b x y 8 P s Q b x h x s 经变量换名后 有事实和规则如下 P a P g s1 r1 P s2 Q b c s2 H f s2 r2 Q b x3 s3 Q b x3 g s3 r3 P s4 Q b x4 h x4 s4 用对偶形式对目标 skolem 化 x H x H x 演绎图如下图 这里只给出了一个一致解图 由置换集构造 U1 和 U2 U1 x s2 x3 s2 x4 s3 s4 U2 f s2 g s1 c g s3 c h x4 s4 a 由于 U1 和 U2 是可合一的 因此该解图是一致解图 合一复合为 f g h c a x g h c a s2 c x3 h c a s3 c x4 h c a s1 a s4 将该合一复合带入目标中 得到解答 x f g h c a 9 第四章 不确定性推理 1 什么是不确定性推理 为什么要采用不确定性推理 P122 2 不确定性推理中要解决哪些基本问题 P123 P124 3 已知 规则 R1 E1 H CF H E1 0 9 R2 E2 H CF H E2 0 6 R3 E3 H CF H E3 0 5 R4 E4 E5 E6 E1 CF E1 E4 E5 E6 0 9 初始数据 CF E2 0 8 CF E3 0 6 CF E4 0 5 CF E5 0 6 CF E6 0 8 CF H 0 求 CF H 解 CF E1 0 8 max 0 CF E4 AND E5 OR E6 0 8 max 0 min CF E4 CF E5 OR E6 0 8 max 0 min 0 5 max CF E5 CF E6 0 8 max 0 min 0 5 0 8 0 8 max 0 0 5 0 8 0 5 0 4 CF1 H CF H E1 max 0 CF E1 0 9 0 4 0 36 CF2 H CF H E2 max 0 CF E2 0 6 0 8 0 48 CF3 H CF H E3 max 0 CF E3 0 5 0 6 0 3 CF12 H CF1 H CF2 H CF1 H CF2 H 0 36 0 48 0 36 0 48 0 67 CF123 H CF12 H CF3 H 1 min CF12 H CF3 H 0 67 0 3 1 0 3 0 53 4 当证据 E1 E2 E3 E4 必然发生后 看 H 的概率变化 已知 H 的先验概率为 0 03 而规则 R1 E1 H LS 20 LN 1 R2 E2 H LS 300 LN 1 R3 E3 H LS 75 LN 1 R4 E4 H LS 4 LN 1 解 1 由 P H 0 03 得 O H P H 1 P H 0 03 1 0 03 0 030927 2 根据 R1 得 O H E1 LS O H 20 0 030927 0 61854 P H E1 O H 1 O H 0 382 3 根据 R2 得 3 根据 R2 得 O H E1 E2 O H E1 O H O H E2 O H O H LS O H E1 300 0 61854 185 562 P H E1 E2 O H E1 E2 1 O H E1 E2 0 99464 4 根据 R3 得 10 O H E1 E2 E3 LS O H E1 E2 13917 15 P H E1 E2 E3 0 99993 5 根据 R3 得 O H E1 E2 E3 E4 LS O H E1 E2 E3 55668 6 P H E1 E2 E3 E4 0 99998 5 例 3 当证据 E 必然发生 已知 H1 的先验概率为 0 03 而规则 R1 E H1 LS 20 LN 1 R2 H1 H2 LS 300 LN 0 0001 又知 P H2 的先验概率为 0 01 时 计算 P H2 E 解 1 根据 R1 及已知 P H1 0 03 得 P H1 E LS P H1 LS 1 P H1 1 20 0 03 20 1 0 03 1 0 382 2 由于 H1 是不确定的 所以要用插值法 因为 P H1 E P H1 当 P H1 E P H1 时 有 P H2 E P H2 0 01 当 P H1 E 1 时 有 P H2 E P H2 H1 LS P H2 LS 1 P H2 1 0 75188 3 P H2 E 0 01 0 75188 0 01 1 0 03 0 382 0 03 0 2792 第五章 搜索策略 1 对量水问题给出问题描述即状态和操作定义 并画出状态空间图 有两个无刻度标志的水壶 分别可装 5 升和 2 升的水 设另有一水缸 可用来向水壶灌 水或倒出水 两个水壶之间 水也可以相互倾灌 已知 5 升壶为满壶 2 升壶为空壶 问如何通过倒水或灌水操作 使能在 2 升的壶中量出一升的水来 解 a 定义两元组 L5 L2 其中 0 L5 5 表示容量为 5 升的壶的当前水量 0 L2 2 表示容量为 2 升的壶的当前水量 b 操作规则集 r1 IF L5 L2 THEN 5 L2 将 L5 灌满水 r2 IF L5 L2 THEN L5 2 将 L2 灌满水 r3 IF L5 L2 THEN 0 L2 将 L5 水到光 r4 IF L5 L2 THEN L5 0 将 L2 水到光 r5 IF L5 L2 and L5 L25 THEN 5 L5 L2 5 L2 到入 L5 中 r7 IF L5 L2 and L5 L25 THEN L5 L2 2 2 L5 到入 L2 中 c 初始状态 5 0 d 结束条件 x 1 其中 x 表示不定 当然结束条件也可以写成 0 1 2 对三枚钱币问题给出产生式系统描述及状态空间图 设有三枚钱币 其排列处在 正 正 反 状态 现允许每次可翻动其中任意 11 一个钱币 问只许操作三次的情况下 如何翻动钱币使其变成 正 正 正 或 反 反 反 状态 答 1 定义四元组 x y z n 其中 x y x 0 1 1 表示钱币为正面 0 表示钱币为方面 n 0 1 2 3 表示当前状态是 经过 n 次翻钱币得到的 2 规则库 r1 IF x y z n THEN x y z n 1 r2 IF x y z n THEN x y z n 1 r3 IF x y z n THEN x y z n 1 其中 x 表示对 x 取反 3 初始状态 1 1 0 0 4 结束状态 1 1 1 3 或者 0 0 0 3 3 有一农夫带一条狼 一只羊和一筐菜欲从河的左岸乘船到右岸 但受下列条 件限制 a 船太小 农夫每次只能带一样东西过河 b 如果没有农夫看管 则狼要吃羊 羊要吃菜 请设计一个过河方案 使得农夫 狼 羊和菜都能不受损失的过河 画出相 应的状态空间图 4 图 1 2 是 5 个城市的交通图 城市之间的连线旁边的数字是城市之间路程的 费用 要求从 A 城出发 经过其他各城一次且仅一次 最后回到 A 城 请给 出搜索树 找出一条最优线路 P200 图 5 33 5 请找出图 1 3 的与或树所包含的解树 P200 图 5 34 6 图 1 4 是一个五子棋棋盘 A B 两人轮流走步 谁先布成五子一线 横线 竖线 对角线均可 谁就获胜 请定义估价函数 并站在 A 的立场上 找 出当前的最佳走步 P200 5 36 7 某问题的状态空间图如下图所示 其中括号内标明的是各节点的 h 值 弧线 边的数字是该弧线的代价 试用 A 算法求解从初始节点 S 到目标节点 T 的路 径 要求给出搜索图 标明各节点的 f 值 及各节点的扩展次序 并给出求 得的解路径 12 答 搜索图如图所示 其中括号内标出的是节点的 f 值 圆圈内的数字是扩展的次序 F 16 得到的解路径为 S B F J T 8 有四人过河 只有一条船 最多可乘坐两人