存儲錯誤 - 第一個深度搜索算法

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將被調用第三次，其參數與之前完全相同。

正如你所看到的，這將導致無窮的遞歸。我無法確定是否會發生這種情況，因爲我不知道您的類型或調用的子程序。

在目前的情況下，你的代碼很難理解，因爲它有一個非常複雜的控制流程。如果你拿走了你的一些代碼的複雜性，那麼追蹤錯誤將會更容易。我建議使用循環遍歷座標而不是遞歸。這可能會解決您的問題。