存储错误 - 第一个深度搜索算法

Question

我目前正在研究一个应该解决3D拼图的算法。 但是我遇到了一个问题，我使用的算法是第一个搜索深度，它似乎运行良好，直到我“获得STORAGE_ERROR：EXCEPTION_STACK_OVERFLOW”。我不太确定它为什么不起作用。任何猜测为什么这不起作用？

我想要这个算法： 它需要一个List，一个图形和一个目标。对于这个例子，列表是7部分长。它试图在第一个坐标中输入该部分。如果它不适合，它会旋转直到它合适，然后与其余的（6部分）一起自我调用。如果零件以24种方式旋转（所有可能的方式旋转一个3D零件），然后它移动到另一个坐标，然后重新开始尝试拟合。当所有部分都没有了或没有任何工作时，它应该退出，并且我有另一个算法在同一个列表中发送另一个订单到这个算法中。

我还希望算法看看最后的坐标是否与目标不匹配，那么它应该只是回溯并尝试找到另一个解决方案。

下面是一些代码：

procedure Pseudo(Parts : in out List_Type; Figure : in out Figure_Type; Goal : in out Figure_Type; LastCoord : in out Integer) is 
     Unchanged : Part_Type := Parts.Data; 
     Next : boolean := False; 
     UnchangedFigure : Figure_Type; 
    begin 
    UnchangedFigure := Figure; 
     if Empty(Parts) then 
      raise Finished; 
     else 
      for I in 1..24 loop 
       RotNumber(Parts.Data,I); -- rotera 
       if Check(Parts.Data,Figure) then -- test om den platsar 
        Maincheck(Parts.Data,Figure,Goal,Next); 
        if Next then 
         Unchanged := Parts.Data; 
         Append_Part(Parts.Data,Figure); 
         Remove_First(Parts); 
         Next := False; 
         Pseudo(Parts,Figure,Goal,LastCoord); 
         Next := False; 
         Figure := UnchangedFigure; 
         Insert_First(Unchanged,Parts); 
         Figure.CoordX := 0; 
         Figure.CoordY := 0; 
         Figure.CoordZ := 0; 
        end if; 
       end if; 
       Parts.Data := Unchanged; 
      end loop; 
     end if; 
     -- if LastCoord /= 7 then --(Original 
      -- if To_String(Figure.Data)(LastCoord) /= To_String(Goal.Data)(LastCoord) then 
       -- Put("over"); 
       -- return; 
      -- end if; 
     -- end if; 
     LastCoord := Figure.CoordZ*Figure.X*Figure.Y + (Figure.Y-Figure.CoordY-1)*(Figure.X) + Figure.CoordX +1; 
     if Figure.CoordY < Figure.Y-1 then 
      Figure.CoordY := Figure.CoordY +1; 
      Pseudo(Parts,Figure,Goal,LastCoord); 
     elsif Figure.CoordY = Figure.Y-1 then 
      if Figure.CoordX < Figure.X-1 then 
       Figure.CoordX := Figure.CoordX +1; 
       Figure.CoordY := 0; 
       Pseudo(Parts,Figure,Goal,LastCoord); 
      elsif Figure.CoordX = Figure.X-1 then 
       if Figure.CoordZ < Figure.Z-1 then 
        Figure.CoordZ := Figure.CoordZ +1; 
        Figure.CoordX := 0; 
        Figure.CoordY := 0; 
        Pseudo(Parts,Figure,Goal,LastCoord); 
       elsif Figure.CoordZ = Figure.Z-1 then 
        return; 
       end if; 
      end if; 
     end if; 
    end Pseudo; 

Answer 1

首先，不要使用异常来控制程序流，这是不好的做法。考虑使用额外的out参数而不是raise Finished。

我认为将所有参数声明为in out也是一个错误。看看Parts：在你的循环中，你将数字追加到它的Data成员，然后删除列表的第一个元素。之后，您可以拨打Pseudo，这将再次冲击列表，如果不成功，Parts可能与呼叫之前的内容完全不同。之后你恢复第一个元素，但不管Append_Part确保永久。我无法确定这是否是一个问题。在拨打Pseudo后恢复列表和数字的努力也是一个明显的迹象，表明您不希望这些参数为in out。

看起来很腥的另一件事是，在循环之后，你改变图形的坐标，然后再次调用Pseudo--这将在第一次迭代结束时将坐标重置为0（如果条件匹配）。一个可能的控制流程将是：

• Pseudo开始，Parts是不是空的。循环开始。我们假设图的Coord值最初为0.
• 循环的迭代不会导致Finished。循环结束。
• 算法改变一些坐标并调用Pseudo。现在假设Parts仍然具有与第一次调用Pseudo时相同的值。正如我写的，这似乎并不是这种情况，但应该是，如果我正确理解你的描述。
• 第二个电话Pseudo与第一个电话相同，只是图中的一些坐标不同（可能有Last_Coord，这似乎不重要）。
• Parts不能为空，循环开始。
• 现在让我们假设在循环中的某一点，条件匹配，但是对Pseudo的调用失败（如“不会提高Finished”）。坐标将重置为0.
• 从那里开始，执行过程与第一次调用Pseudo的执行过程相同，因为它操作的数据现在完全相同。因此在循环中将不会产生Finished，此后，Pseudo将被调用第三次，其参数与之前完全相同。

正如你所看到的，这将导致无穷的递归。我无法确定是否会发生这种情况，因为我不知道您的类型或调用的子程序。

在目前的情况下，你的代码很难理解，因为它有一个非常复杂的控制流程。如果你拿走了你的一些代码的复杂性，那么追踪错误将会更容易。我建议使用循环遍历坐标而不是递归。这可能会解决您的问题。