-2

このリンクの下にある再帰的アルゴリズムを実装しました。3d配列が10x10x10の場合、非常にうまく機能します。

私はそれを200x200x200アレイで実行しようとしていますが、Visual Studioは、無限の復活を使用している可能性があると言っています（私のプログラムは大丈夫だと確信しています）。それを処理する方法はありますか？[DebuggerNonUserCode]再帰メソッドの直前に配置しようとしましたが、うまくいきませんでした。

言及するのを忘れました、それはVisualStudio2010です。

これが私のプログラムの再帰関数です。未訪問としてマークされているすべてのセルに対してこれを実行しています。

    public static int tmp_lowest_floor = 0;
    public static int tmp_maks_size = 0;

    static void function1(Point[, ,] array, int pos_y, int pos_z, int pos_x) // recursive function
    {
        Point cell = array[pos_y, pos_z, pos_x];

        if (cell.Visited == false && cell.IsCave)
        {
            cell.Visited = true; // changing to visited so we do not count anything for this cell anymore
            tmp_maks_size++; // increasing for each cell in this cave (in this run)

            if (tmp_lowest_floor < pos_y) { tmp_lowest_floor = pos_y; }
            cell.FillNeighbourList(array, pos_y, pos_z, pos_x);// adds neighbours into cell's list (max 6) up, down, north, east, south, west

            foreach (Point p in cell.neighbours) // max 6 times recursion in here (I know it sounds horrible, but once I check all the neighbours for a cell, I'll not have to check it ever again)
            {
                if (p != null)
                {
                    if (p.IsCave == true && p.Visited == false)
                    {
                        function1(tablica, p.pos_y, p.pos_z, p.pos_x);
                    }
                }
            }

        }

    }

ps私はそれを反復的に行うことができることを知っていますが、宿題はそれが再帰的に行われなければならないと言っています

4

3 に答える 3

7

無視することはできません。文字通りスタックを吹き飛ばしました。

あなたがすることは、スタックを増やす（したがって問題を遅らせる）か、目前の問題がアルゴリズムの本当にひどい実装であることに気づき、代わりにそれを修正することです（たとえば、反復アプローチを使用するか、テールコール再帰を利用することによって） .

余談ですが、200x200x200 配列内のすべてのセルを通過するために使用しているスタックの量を知りたい場合は、x、y、z 座標のみを追跡します。96MB。Windows は、デフォルトで 1MB 幅のスタックを提供します。

編集:特定の問題を解決するために、非常に基本的な塗りつぶしアルゴリズムがあります。反復形式では、キューとリストを使用します。擬似コード:

list visited=[];
queue q=[];

q.push(startnode);           // the starting point
while(!q.empty())
{
  // make sure we don't revisit nodes
  if(visited.contains(node))
     continue;

  visited.add(node=q.pop()); // we just visited the top

  // do your conditions here, the cave thing? no clue what that is
  // if it passes your filter, do any extra operations on your node here (none in your code)

  // and push the neighbours in the queue
  q.push_all(node.get_neighbours());
}
于 2012-11-06T20:15:33.030 に答える
4

ランタイム環境のスタックは有限です。メソッドを呼び出すたびに、より多くのデータがそのスタックに追加されます。メソッドが戻るたびに、データはスタックから削除されます。メソッド内のメソッド内でメソッドを呼び出し続け、それらのメソッドが返されない場合、最終的にスタックのスペースが不足し、スタック オーバーフローが発生します。

これを回避したい場合は、アルゴリズムを変更して再帰を少なくする (メソッド内でメソッドを呼び出す) か、スタックが大きくなりすぎないように十分に小さいデータ セットを使用することに満足する必要があります。

于 2012-11-06T20:15:51.320 に答える
1

次の方法でスタック サイズを増やすことができます。

  • プロジェクトを右クリック
  • [プロパティ] -> [構成プロパティ] -> [リンカー] -> [システム] を選択します。
  • 「Stack Reserve Size」と「Stack Commit Size」(バイト単位) に異なる値を設定します。ここから、ヒープ サイズを変更することもできます。

この質問の末尾再帰で同様の問題がありました。

于 2015-09-11T12:35:00.563 に答える