0

我目前正在研究一种应该解决 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;
4

1 回答 1

1

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

我认为将所有参数声明为in out. 查看Parts：在您的循环中，将图形附加到其Data成员，然后删除列表的第一个元素。之后，您调用Pseudowhich 将再次与列表混淆，如果它不成功，Parts则可能具有与调用之前完全不同的内容。在那之后你恢复了第一个元素，但无论Append_Part做什么都是永久的。我无法确定这是否真的是一个问题。调用后恢复列表和图形的努力Pseudo也是一个明显的迹象，表明您不希望这些参数成为in out.

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

  • Pseudo开始，Parts不为空。循环开始。假设该图形的Coord值最初为 0。
  • 没有循环迭代导致Finished. 循环结束。
  • 该算法改变了一些坐标并调用Pseudo。现在让我们假设它仍然具有与第一次调用Parts时相同的值。Pseudo正如我所写，情况似乎并非如此，但如果我正确理解您的描述，应该是这样。
  • 第二次调用Pseudo它与第一次调用相同，只是图形的某些坐标不同（并且可能Last_Coord，这似乎无关紧要）。
  • Parts不能为空，循环开始。
  • 现在让我们假设在循环中的某个时刻，条件匹配，但调用Pseudo失败（如“不引发 Finished”）。坐标将重置为 0。
  • 从那里开始，执行与第一次Pseudo调用的执行相同，因为它操作的数据现在是相同的。所以 noFinished将在循环中引发，之后Pseudo将使用与之前完全相同的参数第三次调用。

如您所见，这将导致无限递归。我无法确定这是否会发生，因为我对您的类型或您调用的子程序一无所知。

在当前情况下，您的代码很难理解，因为它具有非常复杂的控制流。如果您消除了代码的一些复杂性，则更容易追踪错误。我建议使用循环来迭代坐标而不是递归。这可能会解决您的问题。

于 2013-03-28T09:32:55.760 回答