저장 오류 - 최초 심도 검색 알고리즘

Question

현재 3D 퍼즐을 해결해야하는 알고리즘을 연구 중입니다. 그러나 문제가 발생했습니다. 사용하는 알고리즘은 첫 번째 검색 심도이며 "STORAGE_ERROR 제기 : EXCEPTION_STACK_OVERFLOW"까지는 제대로 작동하는 것 같습니다. 왜 그것이 작동하지 않는지 나는 잘 모르겠다. 왜 이것이 작동하지 않는지 추측 할 수 있습니까?

이 알고리즘에서 수행하고자하는 것 : 목록, 그림 및 목표를 취합니다. 이 예제의 경우 목록은 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

첫째, 프로그램의 흐름을 제어하기 위해 예외를 사용하지 않는, 그것의 나쁜 관행 :

여기에 코드의 일부이다. raise Finished 대신 out 매개 변수를 사용하는 것이 좋습니다.

모든 매개 변수를 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에 대한 호출이 실패했다고 가정 해 봅시다. 좌표는 0으로 재설정됩니다.
• 거기에서 작동하는 데이터는 이제 동일하기 때문에 첫 번째 Pseudo 호출의 실행과 동일합니다. 따라서 Finished은 루프에서 발생하고 이후에는 Pseudo이 이전과 완전히 동일한 매개 변수를 사용하여 세 번째로 호출됩니다.

알다시피, 이렇게하면 끝없는 재귀가 발생합니다. 내가 당신의 타입이나 당신이 부르는 서브 프로그램에 관해서 아무 것도 모르기 때문에 이것이 일어날 지 확신 할 수 없다.

매우 복잡한 제어 흐름이 있기 때문에 코드를 이해하기 어렵습니다. 코드의 복잡성을 일부 제거하면 오류를 쉽게 추적 할 수 있습니다. 재귀가 아닌 좌표를 반복 할 때 루프를 사용하는 것이 좋습니다. 이것은 귀하의 문제를 해결할 수 있습니다.