文档介绍：测验 1
1 搜索算法（ 16 点）
游戏
标准的a- B算法对游戏树执行深度优先搜索（在一个预定的深度上） 。
可以对a- B算法进行泛化，在游戏树上作广度优先搜索并仍能找到最优解吗？如果可 以解释如何做， 否则为什么不可以。 如果可以泛化， 指出用广度优先搜索的优点或缺点。
不可以。a- B算法是最小-最大上的一个最优方法。最小 -最大本质上需要在游戏树上 查找当前结点下面的结点（当前结点以下预定的深度） ，以便给那个结点分配值。广度 优先的最小-最大没有这种含义。仅仅考虑 a- B而不考虑最小-最大只会使情况变得更
糟，因为a- B的整个要点就在于使用其中的一棵早期（最左）子树的最小 -最大值，来
决定 我们不需要再搜索其后的（最右）子树。
有些人提出， 最小 -最大本质上需要走遍所有的路径才能达到游戏树的叶子， 而游戏的结
果是已知的。这种说法是不正确的。典型地，人们会选择并搜索到一定的深度，使用静 态估计在那个深度上为所考虑的点计算一个评分。
a- B算法能被泛化，在游戏树上作逐步深化 （PD）的搜索并且仍可以到达最优解吗？ 解释如何作或为什么不可以。如果可以泛化，指出优缺点。
是的。逐步深化包括反复的深度优先搜索来增加深度。 这可以用最小-最大和a- B来做,
同样需要选一个向前搜索的最大深度。 PD 确实两费了一些工作量， 但是我们可以看到，
额外的工作是你所做的工作的很小的一部分， 特别是当分支因数很高的时候 ---而在游戏 树中恰恰就是这种情况。优点就是，在定时情况下你可以保证你总可以有一个合理的移
动可用。
算法
你面临着一个有非常庞大的分支因数的路径搜索问题， 但是结果通常包括一个相对较短
的动作序列（实际的长度是未知的） 。所有的动作有同样的代价。你会用什么搜索算法 来找到最优解？指出是在什么条件下，如果可能，给出遍历或扩展列表。
逐步深度 （PD） , 不需要遍历或扩展列表，很可能是最佳选择。所有的代价都一样，因此 广度优先（BF）和逐步深度搜索（PD）都可以保证在此条件下找到最短路径，而不需要额外 的一致代价搜索。因为分支因数很高，空间就是一个问题，这就是我们为什么宁愿用
PD而不是BF。如果我们用有遍历列表的 PD，空间消耗将和 BF 一样。如果我们放弃了 空间的优点，那么为 PD 付出附加的运行时间的代价就没有意义了。
你面临着一个具有非常庞大的分支因数的路径搜索问题， 但是结果通常包括一个相对较
短的动作序列（实际的长度是未知的） 。然而，这些动作代价具有很大的变动。你会用 什么搜索算法来找到最优解？指出是在什么条件下，如果可能，给出遍历或扩展列表。 既然代价是可变的，我们应该用一致代价搜索保证最优解。 代价是高度变化的事实是
好的，因为我们可以预期能够避免搜索具有高的代价的子树。注意，我们不一定有一个
有用启发，因此 A* 或许不可用。如果搜索空间包括许多环，使用一个扩展列表将是有 意义的，因为环会导致多次重复遍历同一个状态。然而，既然我们知道结果是一个相对 短的路径，额外的空间是值得的。
2 约束（ 16 点）
考虑给棋盘配色的问题，水平或垂直的方块不允许有相同的颜色。我们知道仅用红 （R）和黑
（B） 两种颜色就够了。我们限定