A4B-人工智能基本原理-作业

图搜索与问题求解图搜索与问题求解 第一次作业第一次作业 1 1 什么是状态空间图 状态 节点 什么是状态空间图 状态 节点 状态转换规则 边 状态转换规则 边 状态空间 状态空间 隐式状态图隐式状态图 2 2 状态图搜索问题求解需要哪些知识状态图搜索问题求解需要哪些知识 求解过程的本质是什么 求解过程的本质是什么 3 3 对以下对以下 3 3 个问题 试分别设计该问题的状态 状态转换规则 状态空个问题 试分别设计该问题的状态 状态转换规则 状态空 间 并描述求解过程间 并描述求解过程 1 1 传教士与野人问题 传教士 传教士与野人问题 传教士 M M 与野人 与野人 C C 数目均为五人 渡船 数目均为五人 渡船 B B 最多可乘 最多可乘 3 3 人 人 2 2 翻钱币问题 三枚钱币 能否从下面状态翻动三次后出现全正或全 翻钱币问题 三枚钱币 能否从下面状态翻动三次后出现全正或全 反状态反状态 反反反反正正正正反反反反 正正正正正正正正正正正正 反反反反反反反反反反反反 初始状态初始状态初始状态初始状态 s s s s 目标状态集合目标状态集合目标状态集合目标状态集合 0 0 0 7 7 7 3 3 已知桶 罐和瓶分别能存放水 已知桶 罐和瓶分别能存放水 5000ml5000ml 3500ml3500ml 1500ml1500ml 现在桶 现在桶 中有中有 5000ml5000ml 水 如何只利用这三件容器把水分成两份 每份水 如何只利用这三件容器把水分成两份 每份 2500ml2500ml 4 4 N N 皇后问题就是在皇后问题就是在 N NN N 的棋盘上放置的棋盘上放置 N N 个皇后的方法解 满足每行 个皇后的方法解 满足每行 每列和对角线上只允许出现一个皇后 如以下是每列和对角线上只允许出现一个皇后 如以下是 8 8 皇后问题的解 试解决皇后问题的解 试解决 4 4 皇后问题皇后问题 第二次 1 什么是启发性信息 完备的搜索 启发函数 加权状态图 2 深度优先搜索和广度优先搜索过程的 OPEN 表有何不同 3 深度优先搜索和广度优先搜索的优缺点是什么 4 估价函数综合了哪些信息 5 为 倒水 问题设计一个启发函数 第三次 1 什么是与等价 什么是或等价 试分别用一个例子说明 什么是与等价 什么是或等价 试分别用一个例子说明 2 什么是与或图的本原问题 什么是端节点 什么是与节点 或节点 什么是与或图的本原问题 什么是端节点 什么是与节点 或节点 3 与或图搜索的可见性判别条件是什么 与或图搜索的可见性判别条件是什么 4 设有如下图的与设有如下图的与 或或 树 请分别按和代价法及最大代价法求解树的代价 树 请分别按和代价法及最大代价法求解树的代价 A B C D t2 t3t4 t1 与 或树 5 6 21 7 2 2 3 E 5 设有如图所示的博弈树 其中最下面的数字是假设的估值 请对该博弈树作如下工设有如图所示的博弈树 其中最下面的数字是假设的估值 请对该博弈树作如下工 作 作 1 计算各节点的倒推值 计算各节点的倒推值 2 利用利用 剪枝技术剪去不必要的分枝 剪枝技术剪去不必要的分枝 博弈树 30 5 3 3 6 23 5 4 3 0 6 8 3 3 6 9 S0 A B C D EF G HIJ K L NM 第四次 1 请将下列语句翻译成命题公式 1 如果交通不堵塞 老王将准时到达火车站 2 你去听课 他也去听课 3 如果明天不下雪 我就去登山 4 尽管他参加了考试 但他没有通过考试 2 请将下列语句翻译成谓词公式 1 有的人喜欢梅花 有的人喜欢菊花 有的人既喜欢梅花又喜欢菊花 2 他每天下午都去打篮球 3 西安市的夏天既干燥又炎热 4 并不是每一个人都喜欢吃臭豆腐 5 喜欢读 三国演义 的人必读 水浒 6 欲穷千里目 更上一层楼 第 5 次 1 将下列谓词公式整理为子句集形式 1 x y P x y Q x y 2 x y P x y Q x y 3 x y P x y Q x y R x y 4 x P x y P y R x y 5 x P x x P y R x y 6 x y z u v w p x y z u v w Q x y z u v w R x z w 第 6 次 1 教材课后题 2 寝室有甲 乙 丙三名同学 一天晚自习时 班主任老师巡查寝室发现 该寝室有同学 滞留寝室 没有参加晚自习 班主任调查得知 如甲在寝室并乙不在寝室时 则丙一定 在寝室 如乙在寝室 则丙一定在寝室 班主任得出结论 丙一定在寝室 请试用基于 命题公式的归结证明班主任的结论 3 判断以下公式对是否可合一 若可合一 则求出最一般的合一 1 bfyPyxfP 2 bfafxPxyyfP 3 xyPyxP 第 7 次作业 1 试判断下列子句集中哪些是不可满足的 1 S P y Q y P f x Q y 2 S P x Q x Q y R y P a R a 3 S P x Q y L x y P a R z L a z R b Q b 4 S P x Q x R x P y R y Q a R b 5 S P x Q x Q y R y P z Q z R u 2 对下列各题请分别证明 G 是否可肯定是 F1 F2 的逻辑结论 1 F x P x Q x G x P x Q x 2 F1 x P x y Q y L x y F2 x P x y R y L x y G x R x Q x 3 F1 x P x Q x R x F2 x P x S x G x S x R x 4 设已知 1 凡是清洁的东西就有人喜欢 2 人们都不喜欢苍蝇 用归结原理证明 苍 蝇是不清洁的 5 张某被盗 公安局派出五个侦探去调查 研究案情时 侦察