1 . 树搜索(1 2 分) 考虑下图所示树,在横杠上的数字代表弧的长度。 假定节点是按照字母的顺序展开而没有其他方面次序的搜索方式,目标为状态 G 。没有用访问或扩展列表。每一类搜索方法会以什么样的次序扩展?当你扩展到 G 时就停止。只是写出每类搜索状态展开的次序顺序。 搜索类型 状态列表 广度优先 深度优先 逐步深化搜索 代价一致搜索 2 . 图表搜索(1 0 分) 下面的图中,在连线上的数字表示连接成本,在状态边上的数字表示启发式的估计成本。考虑到连线没有方向,设 A 为开始的状态,G 为目标状态。 图示为仿真A*并结合野鸽扩展列表。每一步中,显示状态节点的展开路径,路径的长度,路径上的整体估计代价(实际的长度+启发式的值)和展开列表的当前值(作为状态的列表)。你可以用便笺或者考试用纸的后面来模拟搜索。好的,请按要求把信息内容填到表上。 状态扩展路径 路径长度 总体估计代价 扩展列表 A 0 5 (A) 3. 启发式算法 和 A * (8 分) 1 在问题2中的启发式是可接受的吗? 请解释. 2 在问题2中的启发式是相容的吗? 请解释. 3 在上面的例子中,用A*运算法辅以严格展开列表能得到最佳的路径了吗?如果已经得到了最佳的路径,解释一下你为何预料的。如果没有得到最佳的路径,解释一下你的预料并且给一个简单(特定)的对状态启发式值的改变,使算法能够充分得到正确的行为。 4 . 搜索问题用公式表示(1 0 分) 一 个 火 星 探 测 器 必 须 离 开 登 陆 车 , 然 后 从 三 个 地 方 ( 依 任 何 次 序 ) 来 收 集 岩 石 样 本 , 然后 回 到 登 陆 车 上 。 假 定 有 一 个 导 航 的 模 型 可 以 带 领 探 测 器 从 任 何 想 去 的 地 方 直 接 到 任 何 目 的 地 。它 就 会 有 专门 的 行 动 路 线 : 登 陆 , 到 岩 石 样 品 1, 到 岩 石 样 品 2, 和 到 岩 石 样 品 3. 我 们 知 道 在 任 何 地 点 之 间 穿 梭 所 需 要 时 间 。我 们 的 目 的 就 是 找 到 最 合 适 的 次 序 从 而 在 最 短时 间 内 完 成 这 个 工 作 。 1 用 公 式 表 明 这 个 问 题 是 一 个 搜 索 问 题 , 详 细 说 明 其 状 态 空 间 , 初 始 状 态 , 路 径 成 本 的 函 数 ,...