人工智能练习题_2.pdf

一 填空题 1 人工智能三大学派是 符号主义 联结主义 和 行为主义 2 设 P 是谓词公式 对于 P 的任何论域 存在 P 为真的情况 则称 P 为 永真式 3 谓词公式 G 是不可满足的 当且仅当对所有的解释 G 都为假 4 广度优先搜索算法中 OPEN 表的数据结构实际是一个 二叉树 深度优先搜索算法中 OPEN 表的 数据结构实际是一个 单链表 5 产生式系统由三部分组成 综合数据库 知识库 和推理机 其中推理可分为 正向推理 和 反 向推理 6 专家系统的结构包含人机界面 知识库 推理机 动态数据库 知识库答理系统 和解释模块 7 开发专家系统所要解决的基本问题有三个 那就是知识的获取 知识的表示和知识的运用 知识表示 的方法主要有 逻辑表示法或称谓词表示法 框架 产生式 和语义网络等 在语义网络表示知识时 所使用的推理方法有 AKO 和 ISA 8 从已知事实出发 通过规则库求得结论的产生式系统的推理方式是 正向推理 9 AI 是 ArtificalInteligence 的缩写 10 在谓词公式中 紧接于量词之后被量词作用的谓词公式称为该量词的 辖域 而在一个量词的辖域 中与该量词的指导变元相同的变元称为 约束变元 其他变元称为 自由变元 11 假言推理 A B A B 假言三段论 A B B C A C 12 在诸如走迷宫 下棋 八数码游戏等游戏中 常用到的一种人工智能的核心技术称为 图搜索 技术 解这类问题时 常把在迷宫的位置 棋的布局 八数码所排成的形势用图来表 这种图称为 状 态空间图或状态图 13 在启发式搜索当中 通常用 启发函数 来表示启发性信息 14 某产生式系统中的一条规则 A x B x 则前件是 A x 后件是 B x 15 在框架和语义网络两种知识表示方法中 框架 适合于表示结构性强的知识 而 语义网络 则适合表示一些复杂的关系和联系的知识 面向对象 不仅仅是一种知识表示方法 也是一种流行 的软件设计和开发技术 16 产生式系统的推理可以分为 正向推理 和 反向推理 两种基本方式 17 产生式系统是由 综合数据库 知识库 和 推理机 三部分组成的 18 人工智能的远期目标是 制造智能机器 近期目标是 实现机器智能 19 机器学习系统由环境 学习 知识库 和 执行 几部分构成 20 人工智能是计算机科学中涉及研究 设计和应用 智能机器 的一个分支 它的近期目标在于研究用 机器来 模仿和执行人脑 的某些智力功能 21 规则演绎系统根据推理方向可分为 规则正向演绎系统 规则逆向演绎系统 以及 规则双向演绎 系统 等 22 计算智能是人工智能研究的新内容 涉及 神经计算 模糊计算 和 进化计算 等 23 启发式搜索是一种利用 启发式信息 的搜索 估价函数在搜索过程中起的作用是 估计节点位于解 路径上的希望 24 在与或图中 没有后裔的非终叶节点为不可解节点 那么含有或后继节点且后裔中至少有一个为可解 的非终叶节点是 可解节点 含有与后继节点且后裔中至少有一个为不可解的非终叶节点是 不可解节 点 二 选择题 1 如果把知识按照作用来分类 下述 B 不在分类的范围内 A 用控制策略表示的知识 即控制性知识 B 可以通过文字 语言 图形 声音等形式编码记录和传播的知识 即显性知识 C 用提供有关状态变化 问题求解过程的操作 演算和行动的知识 即过程性知识 D 用提供概念和事实使人们知道是什么的知识 即陈述性 2 下述 A 不是知识的特征 A 复杂性和明确性B 进化和相对性 C 客观性和依附性D 可重用性和共享性 3 人类智能的特性表现在哪 4 个方面 B A 聪明 灵活 学习 运用 B 能感知客观世界的信息 能对通过思维对获得的知识进行加工处理 能通过学习积累知识增长才 干和适应环境变化 能对外界的刺激作出反应传递信息 C 感觉 适应 学习 创新 D 能捕捉外界环境信息 能够利用利用外界的有利因素 能够传递外界信息 能够综合外界信息进 行创新思维 4 人工智能的目的是让机器能够 D 以实现某些脑力劳动的机械化 A 具有智能B 和人一样工作 C 完全代替人的大脑D 模拟 延伸和扩展人的智能 5 下列关于人工智能的叙述不正确的是 C A 人工智能技术它与其他科学技术相结合极大地提高了应用技术的智能化水平 B 人工智能是科学技术发展的趋势 C 因为人工智能的系统研究是从上世纪五十年代才开始的 非常新 所以十分重要 D 人工智能有力地促进了社会的发展 6 人工智能研究的一项基本内容是机器感知 以下列 C 不属于机器感知的领域 A 使机器具有视觉 听觉 触觉 味觉 嗅觉等感知能力 B 让机器具有理解文字的能力 C 使机器具有能够获取新知识 学习新技巧的能力 D 使机器具有听懂人类语言的能力 7 尽管人工智能学术界出现 百家争鸣 的局面 但是 当前国际人工智能的主流派仍属于 B A 连接主义B 符号主义 C 行为主义D 经验主义 8 被誉为国际 人工智能之父 的是 A A 图灵 Turing B 费根鲍姆 Feigenbaum C 傅京孙 K S Fu D 尼尔逊 Nilsson 9 人工智能的含义最早由 C 于 1950 年提出 并且同时提出一个机器智能的测试模型 A 明斯基B 扎德 C 图灵D 冯 诺依曼 10 下列哪个不是人工智能的研究领域 D A 机器证明B 模式识别 C 人工生命D 编译原理 11 AI 是 B 的英文缩写 A Automatic IntelligenceB Artifical Intelligence C Automatice InformationD Artifical Information 12 为了解决如何模拟人类的感性思维 例如视觉理解 直觉思维 悟性等 研究者找到一个重要的信息 处理的机制是 B A 专家系统B 人工神经网络 C 模式识别D 智能代理 13 下述 D 不是人工智能中常用的知识格式化表示方法 A 框架表示法B 状态空间表示法 C 语义网络表示法D 形象描写表示法 14 关于 与 或 图表示法的叙述中 正确的是 D A 与 或 图就是用 AND 和 OR 连续各个部分的图形 用来描述各部分的因果关系 B 与 或 图就是用 AND 和 OR 连续各个部分的图形 用来描述各部分之间的不确定关系 C 与 或 图就是用 与 节点和 或 节点组合起来的树形图 用来描述某类问题的层次关系 D 与 或 图就是用 与 节点和 或 节点组合起来的树形图 用来描述某类问题的求解过程 15 神经网络研究属于下列 B 学派 A 符号主义B 连接主义 C 行为主义D 都不是 16 已知初始问题的描述 通过一系列变换把此问题最终变为一个子问题集合 这些子问题的解可以直接 得到 从而解决了初始问题 这是知识表示法叫 B A 状态空间法B 问题归约法 C 谓词逻辑法D 语义网络法 17 在公式中 y xP x y 存在量词是在全称量词的辖域内 我们允许所存在的 x 可能依赖于 y 值 令这 种依赖关系明显地由函数所定义 它把每个 y 值映射到存在的那个 x 这种函数叫做 B A 依赖函数B Skolem 函数 C 决定函数D 多元函数 18 A A B A 称为 C A 结合律B 分配律 C 吸收律D 摩根律 19 A B A B 称为 D A 结合律B 分配律 C 吸收律D 摩根律 20 如果问题存在最优解 则下面几种搜索算法中 A 必然可以得到该最优解 A 广度优先搜索B 深度优先搜索 C 有界深度优先搜索D 启发式搜索 21 如果问题存在最优解 则下面几种搜索算法中 D 可以认为是 智能程度相对比较高 的算法 A 广度优先搜索B 深度优先搜索 C 有界深度优先搜索D 启发式搜索 22 产生式系统的推理不包括 D A 正向推理B 逆向推理 C 双向推理D 简单推理 23 下列哪部分不是专家系统的组成部分 A A 用户B 综合数据库 C 推理机D 知识库 24 要想让机器具有智能 必须让机器具有知识 因此 在人工智能中有一个研究领域 主要研究计算 机如何自动获取知识和技能 实现自我完善 这门研究分支学科叫 B A 专家系统B 机器学习 C 神经网络D 模式识别 25 命题是可以判断真假的 D A 祈使句B 疑问句 C 感叹句D 陈述句 26 下列哪个系统属于新型专家系统 D A 多媒体专家系统B 实时专家系统 C 军事专家系统D 分布式专家系统 27 人工智能应用研究的两个最重要最广泛领域为 B A 专家系统 自动规划B 专家系统 机器学习 C 机器学习 智能控制D 机器学习 自然语言理解 28 下列搜索方法中不属于盲目搜索的是 D A 等代价搜索B 宽度优先搜索 C 深度优先搜索D 有序搜索 29 语义网络的组成部分为 C A 框架和弧线B 状态和算符 C 节点和链D 槽和值 30 自然语言理解是人工智能的重要应用领域 下面列举中的 C 不是它要实现的目标 A 理解别人讲的话 B 对自然语言表示的信息进行分析概括或编辑 C 欣赏音乐 D 机器翻译 三 简答 1 什么是人工智能 人工智能与计算机程序的区别 答答 综合综合各种不同的观点各种不同的观点 可以从可以从 能力能力 和和 学科学科 两个方面对人工智能进行两个方面对人工智能进行定义定义 从能力从能力的的 角度看 人工智能是指用人工的角度看 人工智能是指用人工的方法方法在机器 在机器 计算机计算机 上上实现的智能 从学科实现的智能 从学科的的角度看 人角度看 人 工智能是一门研究如何构造智能机器或智能系统工智能是一门研究如何构造智能机器或智能系统 使它能模拟使它能模拟 延伸和扩展人类智能的学科延伸和扩展人类智能的学科 2 当前人工智能有哪些学派 他们对人工智能在理论上有何不同观点 答答 当前人工智能当前人工智能有符号有符号主义主义 联结主义 联结主义 和行为主义三大学派 和行为主义三大学派 符号主义符号主义在理论上认为在理论上认为 认知的基元是认知的基元是符号符号 认知认知的过程就是符号运算过程的过程就是符号运算过程 智能行为的充要条件是物智能行为的充要条件是物 理符号系统理符号系统 人脑人脑 计算机都是物理计算机都是物理符号符号系统系统 智能的基础智能的基础是是知识知识 其核心是知识表示其核心是知识表示和知识推理和知识推理 知识知识 可用符号表示 也可用符号进行推理 因而可以可用符号表示 也可用符号进行推理 因而可以建立建立基于知识的人类智能和机器智能的统一的理论体系基于知识的人类智能和机器智能的统一的理论体系 联接主义联接主义认为认为 思维的思维的基元基元是神经元是神经元 而不是而不是符号符号 思维过程是神经元的联结活动过程思维过程是神经元的联结活动过程 而不是而不是符号运符号运 算过程 反对符号主义关于物理符号系统的假设 认为人脑不同于电脑 算过程 反对符号主义关于物理符号系统的假设 认为人脑不同于电脑 提出提出联结主义的人脑工作模式联结主义的人脑工作模式 以取代符号主义的电脑工作模式 以取代符号主义的电脑工作模式 行为主义认为行为主义认为 智能取决于感知和行动智能取决于感知和行动 提出提出了了智能行为的智能行为的 感知感知 动作动作 模型模型 智能不需要知识智能不需要知识 不需不需 要表示要表示 不需要推理不需要推理 人工人工智能智能可以像人类智能那样逐步进化可以像人类智能那样逐步进化 智能只有在现实世界中通过与周围环境的智能只有在现实世界中通过与周围环境的 交互作用才能表现出来交互作用才能表现出来 指责传统人工智能指责传统人工智能 主要指符号主义主要指符号主义 也涉及联结主义也涉及联结主义 对现实世界中客观对现实世界中客观事物事物 的描述和复杂智能行为的工作模式做了虚假的的描述和复杂智能行为的工作模式做了虚假的 过于简单呢的抽象过于简单呢的抽象 因而因而 是不能真实反映现实世界的客是不能真实反映现实世界的客 观观事物的 事物的 3 为什么要研究知识表示 试述状态空间法 问题归约法 谓词演算法的要点 并比较它们的关系 4 请阐述状态空间的一般搜索过程 OPEN 表与 CLOSED 表的作用是什么 答答 先把问题的初始状态作为当前扩展节点对其进行扩展先把问题的初始状态作为当前扩展节点对其进行扩展 生成一组子节点生成一组子节点 然后检查问题的目标状态然后检查问题的目标状态 是否出现在这些子节点中是否出现在这些子节点中 若出现若出现 则搜索成功则搜索成功 找到了问题的解找到了问题的解 若没出现若没出现 则再按照某种搜索策略从则再按照某种搜索策略从 已生成的子节点中选择一个节点作为当前扩展节点已生成的子节点中选择一个节点作为当前扩展节点 重复上述过程重复上述过程 直到目标状态出现在子节点中或者没直到目标状态出现在子节点中或者没 有可供操作的节点为止有可供操作的节点为止 所谓对一个节点进行所谓对一个节点进行 扩展扩展 是指对该节点用某个可用操作进行作用是指对该节点用某个可用操作进行作用 生成该节点生成该节点 的一组子节点 的一组子节点 OPEN 表用于存放刚生成的节点 对于不同的搜索策略 节点在表用于存放刚生成的节点 对于不同的搜索策略 节点在 OPEN 表中的排序是不同的 表中的排序是不同的 CLOSED 表用于存放将要扩展或者已扩展的节点 表用于存放将要扩展或者已扩展的节点 5 广度优先搜索与深度优先搜索各有什么特点 答 广度优先搜索也称为宽度优先搜索 它是一种先生成的节点先扩展的策略 广度优先搜索是一种答 广度优先搜索也称为宽度优先搜索 它是一种先生成的节点先扩展的策略 广度优先搜索是一种 完备的策略完备的策略 即只要问题有解即只要问题有解 它就一定可以找到解它就一定可以找到解 并且并且 广度优先搜索找到的解广度优先搜索找到的解 还不一定是路径最还不一定是路径最 短的解短的解 广度优先搜索的缺点是盲目性较大广度优先搜索的缺点是盲目性较大 尤其是当目标节点距初始节点较远时尤其是当目标节点距初始节点较远时 将产生许多无用的节将产生许多无用的节 点 因此其搜索效率较低 点 因此其搜索效率较低 深度优先搜索是一种非完备策略深度优先搜索是一种非完备策略 即对某些本身有解的问题即对某些本身有解的问题 采用深度优先搜索可能找不到最优解采用深度优先搜索可能找不到最优解 也也 可能根本找不到解可能根本找不到解 常用的解决方法是增加一个深度限制常用的解决方法是增加一个深度限制 当搜索达到一定深度但还没有找到解时当搜索达到一定深度但还没有找到解时 停止停止 深度搜索 向宽度发展 深度搜索 向宽度发展 6 简述广度优先搜索算法 对下图给出广度优先搜索序列 7 简述深度优先算法 对下图给出深度优先搜索序列 8 何谓估价函数 在估价函数中 g x 和 h x 各起什么作用 9 什么是产生式 产生式规则的语义是什么 10 简单阐述产生式系统的组成 11 什么是置换 置换是可交换的吗 12 什么叫做专家系统 它具有哪些特点与优点 答 专家系统是一种具有大量专门知识和经验的智能程序系统 它是人工智能能走向实际应用的一个成 功典范 对它的进一步认识 有助加深对人工智能的认识和理解 特点 可具有一个或多个专家的知识和经验 能以接近于人类专家的水平在特定领域工作 能高效 准确 迅速 13 专家系统由哪些部分构成 各部分的作用为何 四 应用题 1 设有如下语句 请用相应的谓词公式分别把他们表示出来 1 有的人喜欢梅花 有的人喜欢菊花 有的人既喜欢梅花又喜欢菊花 解 定义谓词 P x x 是人 L x y x 喜欢 y 其中 y 的个体域是 梅花 菊花 将知识用谓词表示为 x P x L x 梅花 L x 菊花 L x 梅花 L x 菊花 5 1 4 23 6 7 8 9 10 11 12 13 5 1 4 23 6 7 8 9 10 11 12 13 2 有人每天下午都去打篮球 解 定义谓词 P x x 是人 B x x 打篮球 A y y 是下午 将知识用谓词表示为 x y A y B x P x 3 新型计算机速度又快 存储容量又大 解 定义谓词 NC x x 是新型计算机 F x x 速度快 B x x 容量大 将知识用谓词表示为 x NC x F x B x 4 不是每个计算机系的学生都喜欢在计算机上编程序 解 定义谓词 S x x 是计算机系学生 L x pragramming x 喜欢编程序 U x computer x 使用计算机 将知识用谓词表示为 x S x L x pragramming U x computer 5 凡是喜欢编程序的人都喜欢计算机 解 定义谓词 P x x 是人 L x y x 喜欢 y 将知识用谓词表示为 x P x L x pragramming L x computer 2 用谓词逻辑形式化下列描述 不存在最大的整数 解 定义谓词 G x x 为整数 D x y x 大于 y 形式化为 yxDyGyxGx 或者 xyDyGyxGx 3 将下列自然语言转化为谓词表示形式 1 所有的人都是要呼吸的 2 每个学生都要参加考试 3 任何整数或是正的或是负的 解 设M x x 是人 H x x 要呼吸 P x x 是学生 Q x x 要参加考试 J x x 是整数 R x x 是正数 N x x 是负数 则上述三题就记为 1 x M x H x 2 x P x Q x 3 V x I x R x N x 4 用框架表示下述报导的沙尘暴灾害事件 虚拟新华社 3 月 16 日电 昨日 沙尘暴袭击韩国汉城 机场与高速公路被迫关闭 造成的损失不详 韩国官方示 如果需要直接损失情况 可待一周后的官方公布 的字 此次沙尘暴起因中日韩专家认为是由于中国内蒙古区过分垦牧破坏植被所 致 提示 分析概括用下划线标出的要点 经过概念化形成槽 Slot 并拟出槽的名称 选填侧面 face 值 侧面包含 值 value 默认值 default 如果需要值 if needed 如果附加值 if added 几个 方面 用不到的侧面值可删除 建议框架采用如下形式 FRAME Slot1 Value Default If needed If added Slot2 Value Default If needed If added Slot3 Value Default If needed If added 解 FRAME 沙尘暴 Slot1 时间 Value 3 月 15 日 Default If needed If added Slot2 地点 Value 韩国汉城 Default If needed If added Slot3 损失 Value 不详 Default If needed 一周后 官方公布数字 If added Slot4 起因 Default 中国内 蒙古区 5 试实现一个 大学教师 的框架 大学教师类属于教师 包括以下属性 学历 学士 硕士 博士 专业 计算机 电子 自动化 职称 助教 讲师 副教授 教授 解 框架名 类属 学历 学士 硕士 博士 专业 计算机 电子 自动化 职称 助教 讲师 副教授 教授 假设有以下一段天气预报 北京地区今天白天晴 偏北风 3 级 最高气温 12 最低气温 2 降水 概率 15 请用框架表示这一知识 解 解 Frame 地域 北京 时段 今天白天 天气 晴 风向 偏北 风力 3 级 气温 最高 12 度 最低 2 度 降水概率 15 2 26 按 师生框架 教师框架 学生框架 的形式写出一个框架系统的描述 解 解 师生框架 Frame Name Unit Last name First name Sex Area male female Default male Age Unit Years Telephone HomeUnit Number MobileUnit Number 教师框架 Frame AKO Major Unit Major Name Lectures Unit Course Name Field Unit Field Name Project Area National Provincial Other Default Provincial Paper Area SCI EI Core General Default Core 学生框架 Frame AKO Major Unit Major Name Classes Unit Classes Name Degree Area doctor mastor bachelor Default bachelor 6 用语义网络表示下列信息 1 胡途是思源公司的经理 他 35 岁 住在飞天胡同 68 号 2 清华大学与北京大学进行蓝球比赛 最后以 89 102 的比分结束 7 用语义网络表示下面的知识 1 我是一个人 2 我有一台计算机 3 我的计算机是 PC PIV1 8G 4 PC 机是计算机 5 PC PIV1 8G 是 PC 机 6 PC PIV1 8G 包括硬盘 显示器 CPU 内存 解答 请对下列命题分别写出它们的语义网络 1 每个学生都有一台计算机 解 解 2 高老师从 3 月到 7 月给计算机系学生讲 计算机网络 课 解 解 ISAPARTOF 有ISA 计算机人我PC PIV 机PC 机计算机 硬盘显示器CPU内存 ISAISAISA GS gso c 学生占有权 计算机 Owner Owns F GS g GS g 7 月 8 月 Start End ISA ISAAKO 请把下列命题用一个语义网络表示出来 1 树和草都是植物 解 解 2 树和草都有叶和根 解 3 水草是草 且生长在水中 解 4 果树是树 且会结果 解 5 梨树是果树中的一种 它会结梨 解 7 将命题 某个学生读过三国演义 分别用谓词公式和语义网络表示 答 谓词公式表示 x student x read x 三国演义 ISA 讲课事件 高老师老师 Subjec 计算机系学生 Object 讲课计算机网络 Action Caurse 植物 草 树 AKOAKO 草树 是一种是一种 植物 叶根 Have Have 草 水草 水中 AKO Live 植物 AKO 树 果树 结果 AKOCan 植物 AKO 果树 梨树 结梨 AKOCan 树 AKO 语义网络表示如图 8 给 1 9 九个数字排一个序列 使得该序列的前 n n 1 9 个数字组成的整数能被 n 整除 1 讨论哪些知识可以帮助该问题的求解 2 用产生式系统描述该问题 答 如下的知识可以帮助求解该问题 1 序列中偶数在偶数位置 奇数在奇数位置 2 第五个数为 5 综合数据库 用一个 1 到 9 的序列表示 N x 其中 x 为 1 到 9 的数字之一 规则集 r1 IF len N 4 THEN x 5 r2 IF len N 为偶数 and n In 1 3 7 9 THEN x n r3 IF len N 为奇数 and n In 2 4 6 8 THEN x n 其中 len N 为求序列的长度 In a b c d 为取 a b c d 之一 初始状态 结束条件 得到的序列 N 前 i 个数组成的整数能被 i 整除 8 某企业欲招聘一个 JAVA 程序员 定义如下产生式规则 要求 r1 IF 有工作经验 or 本科以上学历and 有相关知识背景 then 录用 0 9 r2 IF 工作两年以上 and 作过相关工作 then 有工作经验 0 8 r3 IF 学过数据结构 and 学过 JAVAand 学过数据库 and学过软件工程 then 有相关知识背景 0 9 r4 学过数据结构 相关课程的成绩 100 r5 学过 JAVA 相关课程的成绩 100 r6 学过数据库 相关课程的成绩 100 r7 学过软件工程 相关课程的成绩 100 r8 做过相关工作 JAVA 程序员 1 项目经理 1 数据库开发工程师 0 9 数据库管理员 0 7 网络管理员 0 6 客 服人员 0 4 设有一本科毕业生甲 其相关课程的成绩为数据结构 85 JAVA 80 数据库 40 软件工程 90 另有一社会招聘人员乙 参加工作三年 曾做过数据库管理员和数据库开发人员 根据确定性理论 问该公司应该招聘谁 如果你是该本科生 为了能在招聘中胜出 你应该加强哪门课程 并使该门课程的成绩至少达到多少 解 1 对于本科毕业生 由 r4 r5 r6 r7 CF 学过数据结构 0 6 CF 学过 JAVA 0 8 CF 学过数据库 0 4 CF 学过软件工程 0 9 由 r3 CF 有相关知识背景 0 9 min 0 85 0 8 0 4 0 9 0 36 CF 本科学历 1 由 r1 CF 录用 0 9 min 0 36 1 0 324 2 对于社会招聘人员 由 r8 CF 相关工作 0 9 CF 工作两年以上 1 由 r2 CF 有工作经验 0 8 min 1 0 9 0 72 由 r1 CF 录用 0 9 0 72 0 648 所以 该公司应录用社会招聘人员乙 3 可以看出 应该加强数据库的学习 并使该门课程达到 80 分以上 9 对于八数码难题按下式定义估价函数 f x d x h x 其中 d x 为节点 x 的深度 h x 是所有棋子偏离目标位置的曼哈顿距离 棋子偏离目标位置的水平距 离和垂直距离和 例如下图所示的初始状态 S0 8 的曼哈顿距离为 2 2 的曼哈顿距离为 1 1 的曼哈顿 距离为 1 6 的曼哈顿距离为 1 h S0 5 初始状态 S0 目标状态 1 用 A 搜索法搜索目标 列出头三步搜索中的 OPEN CLOSED 表的内容和当前扩展节点的 f 值 2 画出搜索树和当前扩展节点的 f 值 解答 循环OPENCLOSED 初始化S0 1S2S1S3S0 2S6S1S3S4S5S0S2 3S7S1S3S4S5 S8 S0S2S6 搜索树如左图 右上角的数字是其估价函数值 11 设有 3 个传教士和 3 个野人来到河边 打算乘一只船从右岸渡到左岸去 该船的负载能力为两人 在 任何时候 如果野人人数超过传教士人数 那么野人就会把传教士吃掉 他们怎样才能用这条船安全地把 所有人都渡过河去 解答 2 8 3 1 6 4 75 1 2 3 84 7 6 5 2 8 3 1 6 4 75 2 8 3 1 6 4 57 2 8 3 14 756 2 8 3 1 6 4 7 5 S0 5 S1 7 S2 5 S3 7 2 8 3 1 4 756 2 8 3 1 4 756 23 1 8 4 756 S4 7 S5 7 S6 5 2 3 1 8 4 756 2 3 1 8 4 756 S7 5 S8 7 1 2 3 8 4 756 S9 5 1 2 3 84 756 用 Si nC nY 表示第 i 次渡河后 河对岸的状态 nC 表示传教士的数目 nY 表示野人的数目 由于 总人数的确定的 河对岸的状态确定了 河这边的状态也即确定了 考虑到题目的限制条件 要同时保证 河两岸的传教士数目不少于野人数目 故在整个渡河的过程中 允许出现的状态为以下 3 种情况 1 nC