我正在通过edX课程CS 188.1x学习人工智能。由于课程在一年前已经结束，现在处于“归档模式”，没有教职员工可以帮助解答问题。这也意味着我完成课程不会获得学分，所以希望在这里寻求“作业”问题的帮助是可以的。

在第一次作业中提出了以下问题：

问题9：夜晚迷失的蜂巢思维 现在是夜晚，你控制着一只昆虫。你知道迷宫的布局，但不知道昆虫会从哪个方格开始。你必须提出一个搜索问题，其解决方案是一系列通用的动作序列，这样，在执行这些动作后，无论初始位置如何，昆虫都会到达出口方格。昆虫会无意识地执行这些动作，并且不知道其移动是否成功：如果它使用了一个会将其移动到被阻挡方向的动作，它将留在原地。例如，在下面的迷宫中，向右移动两次可以保证昆虫无论从哪里开始都会到达出口。

然后它询问状态空间的大小。答案给出为2^MN，其中M和N是迷宫的水平和垂直维度。为什么答案是MN的幂集？在我看来，昆虫在开始时只能在一个方格内，我们只有一只昆虫，所以我知道起始状态的数量是MN。但起始状态的数量 != 状态空间，这就是我感到困惑的地方。

仅供参考 – 每次移动的成本为1，昆虫一次只能向左、右、上或下移动一个方格。目标是到达X（目标方格）。

回答：

好的 – 我想我明白了。

所有子集的集合（幂集*）正是思考这个问题的正确方式。状态空间是所有状态的集合。

1) 状态的定义：

“一个状态包含预测一个动作效果所需的所有信息，并确定它是否为目标状态。”（http://artint.info/html/ArtInt_48.html）

在这种情况下，动作很简单：左、右、上、下。它们是昆虫可能进行的移动。

2) 解决方案的定义：

解决方案是导致通过目标测试的动作序列。

如果我们只允许MN个状态，每个可能的起始位置一个，那么我们将得到一个状态空间，其解决方案仅对离散的起始位置有效。但是，解决方案必须对昆虫的初始状态无效。这意味着解决方案必须适用于昆虫可能占据MN个可用方格中的任何一个的场景。

换句话说，解决方案必须对每个可能的起始空间的每个子集（组合）有效，这就产生了MN的幂集，即2^MN。

为什么？因为对给定起始状态有效的解决方案可能对所有其他起始状态无效。而问题要求我们找到对所有起始状态都有效的解决方案。这也是为什么即使实际上我们的昆虫在初始化时只占据MN个位置中的1个，状态空间也远大于MN。仅仅因为一个解决方案（移动序列）在昆虫从(1, 1)开始时有效，并不意味着该解决方案（移动序列）也会在昆虫从(2, 1)开始时有效。

附加问题：为什么状态空间不是1，即每个MN方格都“有”一只昆虫（并且允许昆虫互相叠加）的完整集合？

我曾想说，仅仅因为一个移动序列在昆虫可以从MN个可能位置中的所有位置开始时给出目标状态，并不意味着当昆虫从(3, 2)或MN - 1或MN - 2等可能位置开始时，同样的移动序列也会给出目标状态。但根据定义，它必须（覆盖所有起始点的解决方案必须是覆盖每个有限子集的起始点的解决方案）。

所以我想你评估除“所有方格都有昆虫”之外的起始状态的原因是，仅评估那个状态生成的解决方案可能不是最优的。实际上，这种解释得到了作业中给出的这个问题的可接受启发式方法的支持：

从昆虫可能所在的每个可能位置到目标的曼哈顿距离的最大值。

或者

从昆虫可能所在的每个可能位置到目标的曼哈顿距离的最小值。

我们只有一个起始状态，昆虫在所有方格上（具有在彼此之上移动的魔法能力）的案例是我们用来定义启发式方法的放松问题。同样根据可接受性的定义，由于启发式方法不得高估动作的真实（弧）成本，并且由于弧成本由曼哈顿距离给出，上述两种启发式方法都是可接受的。（最大值案例是可接受的，因为昆虫的每个可能位置实际上是可能的 – 因此最大成本是可能的）。

*如果你不知道幂集是什么，你只需要知道幂集是一个给定集合的所有子集的集合。它由2^(集合的大小)给出。

换句话说，如果我有一组三个球{红色，蓝色，绿色}，我想知道有多少不同的子集，我可以这样计算。一个子集要么包含该元素（1），要么不包含（0）。所以{0, 0, 1}将是只有绿色球的子集，{1, 1, 1}将是所有球的子集（是的，技术上这是一个子集），而{0, 0, 0}将是没有球的子集（同样，技术上是一个子集）。所以我们看到所有子集的数量是2^3 = 8。或者在我们的问题中，是2^MN。