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.

怪しげに見えるもう 1 つのことは、ループの後で Figure の座標を変更してからPseudo再度呼び出すことです。これにより、最初の反復の最後に座標が 0 にリセットされます (条件が一致する場合)。可能な制御フローは次のとおりです。

  • PseudoParts空ではありません。ループが始まります。CoordFigure の値が最初は 0であると仮定しましょう。
  • につながるループの繰り返しはありませんFinished。ループ終了。
  • アルゴリズムは、いくつかの座標を変更して を呼び出しますPseudo。ここでは、最初に呼び出されPartsたときと同じ値をまだ持っていると仮定しましょう。Pseudo私が書いたように、そうではないようですが、あなたの説明を正しく理解すればそうなるはずです.
  • それへの 2 番目の呼び出しPseudoは、図の一部の座標が異なることを除いて、最初の呼び出しと同じです (おそらくLast_Coord、問題ではないようです)。
  • Parts空にすることはできません。ループが開始されます。
  • ここで、ループのある時点で条件が一致するが、への呼び出しがPseudo失敗すると仮定しましょう (「Finished を発生させない」のように)。座標は 0 にリセットされます。
  • それ以降は、操作対象のデータが同じになるため、実行は最初のPseudo呼び出しと同じになります。そのため、ループ内でnoFinishedが発生し、その後、Pseudo前とまったく同じパラメーターで 3 回目が呼び出されます。

ご覧のとおり、これは無限の再帰につながります。あなたのタイプやあなたが呼び出すサブプログラムについて何も知らないので、これが起こるかどうかはわかりません。

現在の状態では、コードの制御フローが非常に複雑であるため、コードを理解するのは困難です。コードの複雑さの一部を取り除くと、エラーを追跡しやすくなります。再帰ではなく、ループを使用して座標を反復処理することをお勧めします。これで問題が解決する場合があります。

于 2013-03-28T09:32:55.760 に答える