树搜索(12VIP专享

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 用 公 式 表 明 这 个 问 题 是 一 个 搜 索 问 题 ， 详 细 说 明 其 状 态 空 间 ， 初 始 状 态 ， 路 径 成 本 的 函 数 ，...