1.树搜索(12分) 考虑下图所示树，在横杠上的数字代表弧的长度。 A 3 E G 假定节点是按凰字母的顺序展开而没有其他方面次序的擅索方式，目标为状态G。没 有用访问成扩展列表。每一类搜索方法会以什么样的次序扩展？当你扩展到G时就停止。 只是写出每类搜索状态展开的次序顺序。 搜索类型 状态列表 广度优先 深度优先 逐步深化瘦索 代价一致搜蜜
1. 树搜索（12 分） 考虑下图所示树，在横杠上的数字代表弧的长度。 假定节点是按照字母的顺序展开而没有其他方面次序的搜索方式，目标为状态 G。没 有用访问或扩展列表。每一类搜索方法会以什么样的次序扩展？当你扩展到 G 时就停止。 只是写出每类搜索状态展开的次序顺序。 搜索类型 状态列表 广度优先 深度优先 逐步深化搜索 代价一致搜索
2.图表搜索(10分) 下面的图中，在连线上的数字表示连接成本，在状态边上的数字表示启发式的估计成 本。考虑到连线没有方向，设A为开始的状态，G为目标状态。 A B c 1 5 2 9 0 G H 1 图示为仿真A·并结合野鸽扩展列表。每一步中，显示状态节点的展开路径，路径的长度， 路径上的整体估计代价（实际的长度十启发式的值）和展开列表的当前值（作为状态的列表）。 你可以用便笺或者考试用纸的后面来模拟搜索。好的，请按要求把信息内容填到表上。 状态扩展路径 路径长度 总体估计代价 扩展列表 0 5 (A)
2. 图表搜索（10 分） 下面的图中，在连线上的数字表示连接成本，在状态边上的数字表示启发式的估计成 本。考虑到连线没有方向，设 A 为开始的状态，G 为目标状态。 图示为仿真A*并结合野鸽扩展列表。每一步中，显示状态节点的展开路径，路径的长度， 路径上的整体估计代价（实际的长度＋启发式的值）和展开列表的当前值(作为状态的列表)。 你可以用便笺或者考试用纸的后面来模拟搜索。好的，请按要求把信息内容填到表上。 状态扩展路径 路径长度 总体估计代价 扩展列表 A 0 5 (A)
3.启发式算法和A*(8分) 1在问题2中的启发式是可接受的吗？请解释， 2在问题2中的启发式是相容的吗？请解释. 3在上面的例子中，用弘运算法辅以严格展开列表能得到最佳的路径了吗？如果己经得到了 最佳的路径，解释一下你为何预料的。如果没有得到最佳的路径，解释一下你的预料并且给 一个简单（特定）的对状态启发式值的政变，使算法能够充分得到正确的行为
3. 启发式算法 和 A* (8 分) 1 在问题2中的启发式是可接受的吗? 请解释. 2 在问题2中的启发式是相容的吗? 请解释. 3 在上面的例子中，用A*运算法辅以严格展开列表能得到最佳的路径了吗？如果已经得到了 最佳的路径，解释一下你为何预料的。如果没有得到最佳的路径，解释一下你的预料并且给 一个简单（特定）的对状态启发式值的改变，使算法能够充分得到正确的行为
4.搜索问题用公式表示(10分) 一个火星探深测器必须离开登陆车，然后从三个地方（依任何次序）来收集岩石样本。然 后回到登陆车上. 假定有一个导航的模型可以带领探测器从任何想去的地方直接到任何目的地。它就会有专 门的行动路线：登陆，到岩石样品1，到岩石样品2。和到岩石样品3 我们知道在任何地点之间穿俊所需要时间，我们的目的就是找到最合适的次序从而在最短 时间内完成这个工作。 1用公式表明这个问题是一个搜索问愿，详细说明其状态空间，初始状态，路径成本的函数， 和目标检测。尽量确保状志空间是足够详细的来支持解决问题，但不是见余的， 2请说明什么搜索是最有效的，并说明原因。 3一种可能的对于状态的启发方式评价是从状态的位置回到登陆车的距离：这很明显是在可 接受的。对于这个问题来说有更有效的，但仍然是可接受的、启发式的函数吗？（不用担心 其是否具有相容性)
4. 搜索问题用公式表示（10 分） 一个火星探测器必须离开登陆车，然后从三个地方（依任何次序）来收集岩石样本，然 后回到登陆车上。 假定有一个导航的模型可以带领探测器从任何想去的地方直接到任何目的地。它就会有专 门的行动路线：登陆，到岩石样品1，到岩石样品2，和到岩石样品3. 我们知道在任何地点之间穿梭所需要时间。我们的目的就是找到最合适的次序从而在最短 时间内完成这个工作。 1 用公式表明这个问题是一个搜索问题，详细说明其状态空间，初始状态，路径成本的函数， 和目标检测。尽量确保状态空间是足够详细的来支持解决问题，但不是冗余的。 2 请说明什么搜索是最有效的，并说明原因。 3 一种可能的对于状态的启发方式评价是从状态的位置回到登陆车的距离；这很明显是在可 接受的。对于这个问题来说有更有效的，但仍然是可接受的、启发式的函数吗？（不用担心 其是否具有相容性）
5.约束搜索问题(16分) 让我们来看一下计算机上允许程序做为满足约束的问题。 我们有一系列的程序（工作）五在计算机中需要确定执行时间。每一个工作都有最大的 运行时间尼。我们先假定这些工作（在任何一台机子上）只能在一些预定设置的时间开始：， 另外，有一个厂的时间爱求所有的工作要在这个时间内运行完成：那健是，开始时间+运行 时间小于或等于最大限定时间。现在，我们假定所有机器可以执行任何工作。 让我们设想采用变量和值对(，店)来解决这个间题，下面是简单的例子： ·八运行时间M2 ·2运行时间2=4 ·B运行时间2=3 ·A运行时间群=3 ·开始时间k=1,2,3.4,5/ 可利用的设各M和2. ·最大时间是7x=7. 例如1=(2,2)，表示的是，在设备规上运行工作刀开始时间为2. 1.对于这种CSP的具体钓束是什么呢？写一个布尔表达式（用遂辑连接和算术运算）来 满足每一对变量的赋值问题。在下列情况下： ·方对应值(，五)】 ·对应值（总别
5. 约束搜索问题（16 分） 让我们来看一下计算机上允许程序做为满足约束的问题。 我们有一系列的程序（工作）Ji 在计算机Mj中需要确定执行时间。每一个工作都有最大的 运行时间Ri。我们先假定这些工作（在任何一台机子上）只能在一些预定设置的时间开始Tk 。 另外，有一个Tmax 的时间要求所有的工作要在这个时间内运行完成；那就是，开始时间+运行 时间小于或等于最大限定时间。现在，我们假定所有机器可以执行任何工作。 让我们设想采用变量和值对(Mj ,Tk )来解决这个问题，下面是简单的例子： •J1运行时间 R1 =2 •J2运行时间 R2 =4 •J3运行时间 R2 =3 •J4运行时间 R4 =3 •开始时间 Tk = {1,2,3,4,5} •可利用的设备 M1 和 M2. •最大时间是 Tmax =7. •例如 J1 =(M2,2), 表示的是, 在设备M2 上运行工作J1 开始时间为 2. 1. 对于这种CSP的具体约束是什么呢？写一个布尔表达式（用逻辑连接和算术运算）来 满足每一对变量的赋值问题。在下列情况下： •Ji 对应值 (Mj ,Tk ) •Jm对应值 (Mn,Tp)
2,对于上面问题写出一个完整而有效的公式 1 2= B= J4= 3,我们首先会选择爆一个变量，如果我们依变量（最多约束》次序做T-F℃（算法）？为什 么？ 4,如果我们在实例的初始状态下做约桌传播，值域中什么值会被除？请解释。 5.如果我们设2=(M,1),当前向检验后怎样的值域内值依燃合法？ "h目 "h∈ .hE ·A
2．对于上面问题写出一个完整而有效的公式 •J1 = •J2 = •J3 = •J4 = 3．我们首先会选择哪一个变量，如果我们依变量（最多约束）次序做BT-FC（算法）? 为什 么? 4． 如果我们在实例的初始状态下做约束传播，值域中什么值会被删除？请解释。 5. 如果我们设J2 =(M1, 1), 当前向检验后怎样的值域内值依然合法？ •J1 ∈ •J2 ∈ •J3 ∈ •J4 ∈
6,我们若用机器好做为变量来间释这个间题。假设你的表上有项工作，有N台机器，这种 表述应该有什么样的取值？ 7.这个公式的不利方面是什么（用机器做为变量）？
6． 我们若用机器Mj 做为变量来阐释这个问题。假设你的表上有K项工作，有N台机器，这种 表述应该有什么样的取值？ 7． 这个公式的不利方面是什么（用机器做为变量）？
6.游戏搜索(10分) 下面是游戏树的图。顶部的节点是最大的节点，弧上的标识代表移步。底部的数字表示游我 选手不同的最大值输出。 Max M R Min R R Max 2 2 4 1,游戏选手获得的最大值是多少？ 2.最大值对应的第一步移动是什么？ 3,定最大值选手朝刚才说的方向移动了，那么最小值选手最好的下一步移动方向是什么，假 定这是一个整体的游戏树。 4.应用alpha-beta修剪，假定节点从右向左，哪一个节点会被去掉？圈起没有被检查的节 点。 Max R M Min R R Max 3 2 4 6
6. 游戏搜索 (10 分) 下面是游戏树的图。顶部的节点是最大的节点，弧上的标识代表移步。底部的数字表示游戏 选手不同的最大值输出。 1．游戏选手获得的最大值是多少？ 2．最大值对应的第一步移动是什么? 3．定最大值选手朝刚才说的方向移动了，那么最小值选手最好的下一步移动方向是什么，假 定这是一个整体的游戏树。 4．应用 alpha-beta 修剪, 假定节点从右向左, 哪一个节点会被去掉? 圈起没有被检查的节 点
1树搜索(10分) 考虑下面的树。在孤上的数字代表其长度：靠近状态B、C和D的数字是启发式估计值： 所有其他状态的启发估计值为0。 A 5 4 3 B 634 6 3 G 假定节点的子节点的扩展顺序是沿着字母颗序而不是其他的指定瘦常顺序，目标状态为 厂没有用访问和扩展列表。每一类搜索会有什么样的顺序进行扩展。只写出每一个搜索对应 的扩展状态的颗序。 搜索类型 状态列表 广度优先 深度优先 逐步深化搜索 最优优先搜索 A·搜索
1 树搜索 (10 分) 考虑下面的树。在弧上的数字代表其长度；靠近状态 B、C和 D 的数字是启发式估计值； 所有其他状态的启发估计值为0。 假定节点的子节点的扩展顺序是沿着字母顺序而不是其他的指定搜索顺序，目标状态为 J。没有用访问和扩展列表。每一类搜索会有什么样的顺序进行扩展。只写出每一个搜索对应 的扩展状态的顺序。 搜索类型 状态列表 广度优先 深度优先 逐步深化搜索 最优优先搜索 A* 搜索
2图表搜索(8分) 假定有下面的图。连接弧没有方向。设为起始状态，G为目标状态。 2 5 B 6 G 基于严格的扩展列表在这个图形中仿真代价一致搜索，在每一步，写出节点的扩展状态， 对应路径的长度，和当前扩展列表的值（做为状志的列表）。 状态扩展 路径长度 扩展列表 A 0 A
2 图表搜索 (8 分) 假定有下面的图。连接弧没有方向。设A为起始状态，G为目标状态。 基于严格的扩展列表在这个图形中仿真代价一致搜索。在每一步, 写出节点的扩展状态， 对应路径的长度，和当前扩展列表的值(做为状态的列表)。 状态扩展 路径长度 扩展列表 A 0 A