好的 - 我想我明白了。
所有子集的集合（幂集*）正是思考这个问题的正确方法。状态空间是所有状态的集合。
1）状态定义：
“一个状态包含所有必要的信息来预测一个动作的效果并确定它是否是一个目标状态。” ( http://artint.info/html/ArtInt_48.html )
这种情况下的动作很简单：left, right, up, down.它们是错误可能做出的动作。
2) 解决方案的定义：
解决方案是导致目标测试通过的一系列动作。
如果我们只允许MN状态，对于错误所在的每个可能的起始位置都有一个状态，那么我们将拥有一个状态空间，它给出的解决方案仅对离散的起始位置有效。但是，无论错误的初始状态如何，解决方案都必须有效。这意味着该解决方案必须适用于错误可能占据任何MN可用方格的情况。
换句话说，解决方案必须对可能的起始空间的每个子集（组合）都有效，这会产生 的幂集MN，即2^MN。
为什么？因为对给定开始状态有效的解决方案可能不适用于所有其他开始状态。而这个问题要求我们找到对所有起始状态都有效的解决方案。这也是为什么状态空间比MN实际上我们的错误仅在初始化时占据位置大得多1的原因。MN仅仅因为解决方案（移动序列）在错误开始时有效，(1, 1)并不意味着解决方案（移动序列）也适用于从(2, 1).
额外问题：为什么状态空间不只是 1，即每个MN方块“有”一个虫子的完整集合（并且允许虫子在彼此之上移动）？
我很想说，当错误可以在所有可能的位置开始时，仅仅因为一系列移动给出了目标状态MN，这并不意味着当错误开始时，相同的移动序列给出了目标状态(3, 2)或等可能的职位。但根据定义，它必须（所有起点的解决方案必须是起点的每个有限子集的解决方案）。MN - 1MN - 2
因此，我认为您评估“所有框都有错误”以外的起始状态的原因是因为仅评估该状态生成的解决方案可能不是最佳的。事实上，这个解释得到了家庭作业作为这个问题的可接受启发式的证实：
从昆虫可能所在的每个可能位置到目标的曼哈顿距离的最大值。
或者
从昆虫可能所在的每个可能位置到目标的最小曼哈顿距离。
我们只有一个起始状态，所有盒子上都有错误（具有相互叠加的神奇能力）的情况是我们用来定义启发式的轻松问题。再次根据可接受性的定义，由于启发式不能高估动作的真实（弧）成本，并且弧成本由曼哈顿距离给出，因此上述两种启发式都是可接受的。（最大情况是可以接受的，因为实际上每个可能的错误位置都是可能的 - 因此最大成本是可能的）。
*如果你不知道幂集是什么意思，你只需要知道幂集是给定集合的所有子集的集合。它由 给出2^(size of the set)。
换句话说，如果我有一组三个球{red, blue, green}，我想知道我有多少个不同的子集，我可以如下计算。子集要么包含元素 (1)，要么不包含元素 (0)。因此{0, 0, 1}，只有绿球{1, 1, 1}的子集，所有球的子集（是的，从技术上讲，这是一个子集），并且{0, 0, 0}不是任何球的子集（同样，从技术上讲，这是一个子集）。所以我们看到所有子集的数量是2^3 = 8。或者在我们的问题中，2^MN.
