人工智能课后习题答案 2

84 页 1-6 答案 1。何为状态图和与或图？图搜索与问题求解有什么关系？ 状态图是描述寻找目标或路径问题的有向图，即描述一个实体基于事件反应的动态行为， 显示了该实体如何根据当前所处的状态对不同的时间做出反应的。与或图是一 种 系 统 地 将 问 题 分 解 为 互 相 独 立 的 小 问 题 ， 然 后 分 而 解 决 的 方 法 。 与 或 图 中 有 两 种 代 表 性 的 节 点 ： “与 节 点 ”和 “或 节 点 ”， “与 节 点 ”指 所 有 的 后 续 节 点 都 有 解 时 它 才 有 解 ； “或 节 点 ”指 各 个 后 续 节 点 均 完 全 独 立 ， 只 要 其 中 有 一 个 有 解 它 就 有 解 。 关 系 ： 问 题 求 解 就 是 在 一 个 图 中 寻 找 一 个 从 初 始 节 点 到 目 标 节 点 的 路 径 问 题 ， 图 搜 索 模 拟 的 实 际 是 人 脑 分 析 问 题 ， 解 决 问 题 的 过 程 ， 它 基 于 领 域 知 识 的 问 题 求 解 过 程 。 第 3 章作业题参考答案 2.综述图搜索的方式和策略。 答：用计算机来实现图的搜索，有两种最基本的方式：树式搜索和线式搜索。 树式搜索就是在搜索过程中记录所经过的所有节点和边。 线式搜索就是在搜索过程中只记录那些当前认为是处在所找路径上的节点和边。线式 搜索的基本方式又可分为不回溯和可回溯的的两种。 图搜索的策略可分为：盲目搜索 和启发式搜索。 盲目搜索就是无向导的搜索。树式盲目搜索就是穷举式搜索。而线式盲目搜索， 对于不回溯的就是随机碰撞式搜索，对于回溯的则也是穷举式搜索。 启发式搜索则是利用 “启发性信息”引导的搜索。启发式搜索又可分为许多不同 的策略，如全局择优、局部择优、最佳图搜索等。 1、何为状态图和与或图？图搜索与问题求解有什么关系？ 解：按连接同一节点的各边间的逻辑关系划分，图可以分为状态图和与或图两大类。其中 状态图是描述问题的有向图。在状态图中寻找目标或路径的基本方法就是搜索。 2、综述图搜索的方式和策略。 解：图搜索的方式有：树式搜索，线式搜索。 其策略是：盲目搜索，对树式和不回溯的线式是穷举方式，对回溯的线式是随机碰撞式。 启发式搜索，利用“启发性信息”引导的搜索。 3、什么是问题的解？什么是最优解？ 解：能够解决问题的方法或具体做法成为这个问题的解。其中最好的解决方法成为最优解。 4、什么是与或树？什么是可解节点？什么是解树？ 解：与或树:一棵树中的弧线表示所连树枝为“与”关系,不带弧线的树枝为或关系。这棵树 中既有与关系又有或关系，因此被称为与或树。 可解节点:解树实际上是由可解节点形成的一棵子树,这棵子树的根为初始节点，叶为终止节 点，且这棵子树一定是与树。 解树:满足下列条件的节点为可解节点。 终止节点是可解节点； 一个与节点可解，当 且仅当其子节点全都可解；一个或节点可解，只要其子节点至少有一个可解。 5、设有三只琴键开关一字排开，初始状态为“关、开、关 ”，问连接三次后是否会出现 “开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关，而且只能按一个 开关。请画出状态空间图。 注：琴键开关有这样的特点，若第一次按下时它为“开” ，则第二次按下时它就变成了 “关” 。 解：设 0 为关，1 为开 6、有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制： 1）船太小，农夫每次只能带一样东西过河。2 ）如果没农夫看管，则狼要吃羊，羊要吃菜。 请设计一个过桥方案，使得农夫、狼、羊、菜都不受损失地过河。画出相应状态空间图。 提示：（1）用四元组（农夫、狼、羊、菜）表示状态，其中每个元素都可为 0 或 1，用 0 表示在左岸，用 1 表示在右岸。 （2 ）把每次过河的一次安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。 解：设 A=（A1，A2 ，A3，A4）为状态 A1：表示农夫的位置，=0 ：未过河、=1：已过河 A2：表示狼的位置，=0 ：未过河、=1：已过河 A3：表示菜的位置，=0 ：未过河、=1：已过河 A4：表示羊的位置，=0 ：未过河、=1：已过河 具体的过河方案为： （1 ）农夫、羊从左岸- 右岸，留下羊-一人回到左岸 （2 ）农夫、菜从左岸- 右岸，留下菜-农夫、羊回到左岸 （3 ）农夫、狼从左岸- 右岸，留下菜、狼-农夫一人回到左岸 （4 ）农夫、羊从左岸- 右岸 相应的状态空间图为：（0， 0，0，0 ） (1，0 ，0，1 ） （0，0 ，0 ，1） （1，0，1 ，1） （0 ，0，1，0 ） （1，1 ，1 ，0）