1、设一平底锅上放有三个烙饼，从上到下依次标记为A、B、C，如果用一个锅铲翻动这些烙饼，每一次翻动是先将锅铲插入到两个烙饼之间或锅与底层烙饼之间，然后将锅铲上的烙饼全部翻过。例如，将锅铲插入到B和C之间，然后翻过A和B，这一操作过程如下图所示。 （1）设开始时锅中烙饼从上到下依次为A、B、C，那么至少需要多少次翻动才能使锅中烙饼变成从上到下依次为A、C、B？请画出状态空间图。 （2）如果开始时锅中有四个烙饼，从上到下依次为A、B、C、D，若要变成从上到下依次为C、A、D、B顺序，请画出有界深度优先搜索树。（设搜索深度的界限为dm= 4）

（1）根据题目要求，每次翻动都是将锅铲插入两个烙饼之间或锅与底层烙饼之间，然后将锅铲上的烙饼全部翻过。因此，每次翻动后，锅中烙饼的相对顺序都不会改变。考虑从初始状态开始，通过翻动操作，逐步到达目标状态。假设当前状态为 ABC，需要将其变成 ACB。

可以先将锅铲插入 AB 之间，翻过 A 和 B，得到状态 BAC。再将锅铲插入 BC 之间，翻过 B 和 C，得到状态 BCA。最后将锅铲插入 AB 之间，翻过 A 和 B，得到目标状态 ACB。因此，至少需要翻动三次。

状态空间图如下所示：

      ABC
     /   \
   BAC  ACB
     \   /
      BCA

（2）如果开始时锅中有四个烙饼，从上到下依次为A、B、C、D，若要变成从上到下依次为C、A、D、B顺序。则可以先将锅铲插入 AB 之间，翻过 A 和 B，得到状态 BADC。再将锅铲插入 CD 之间，翻过 C 和 D，得到状态 BADC。再将锅铲插入 AB 之间，翻过 A 和 B，得到状态 CDAB。最后将锅铲插入 BC 之间，翻过 C 和 D，得到目标状态 CADB。

有界深度优先搜索树如下所示（其中数字表示当前状态下的烙饼编号，箭头表示一次翻动操作）：

           1234
           / | \
        2134 3214 4231
        / |   |   | \
    2314 2413 3412 3412 4231
    / |   |   |   |   | \
  2341 2431 3421 3421 4312 4312
  / |   |   |   |   |   | \
2413 2431 3421 3421 4312 4312 4132