0

Objective-C で迷路を生成しようとしています。グラフを作成し、すべてのエッジを接続しました (と思います)。しかし、実際の迷路を作ろうとすると行き詰まります。

私が使用しているコードは次のとおりです。

- (void)visitFromCurrentPoint:(GridPoint *)point fromPreviousVertex:(Vertex *)prev {

if ([grid allVerticiesVisited]) {
    NSLog(@"done!");
    return;
}
Vertex *cur = [grid vertexAtPoint:point];
[grid setVertextVisited:cur];
NSArray *borderingVerticies = [grid verticiesBorderingPoint:point];
Vertex *randomVertex;
int random = arc4random()%[borderingVerticies count];
randomVertex = [borderingVerticies objectAtIndex:random];
if (![randomVertex visited]) {
    [cur.edgeList removeObject:prev];
    [prev.edgeList removeObject:cur];
    [self visitFromCurrentPoint:[randomVertex point] fromPreviousVertex:cur];
}
else {
     [self visitFromCurrentPoint:point fromPreviousVertex:cur];
}
}

ただし、これは機能せず、スタック オーバーフローが発生します。私が間違っていることがわかりますか？

前もって感謝します！

4

1 に答える 1

0

これは再帰が多すぎることが原因です。反復解法を試してください。

明確にするために：各関数呼び出しは、スタックスペースのビットを使用して、引数を渡したり、呼び出された関数のスコープ中に変更されるCPUレジスタの状態を保存したりします。本当に深い再帰を行っている場合、すべてのスタック スペースを使用してしまう可能性があるため、クラッシュが発生します。

反復的な解決策では、システム スタックを動的にサイズ変更された配列またはキューに置き換えることで問題を回避します。これは、スタック スペースの代わりにシステム メモリを使用します。

(基本的には、関数内でキューまたは配列を使用して、再帰関数呼び出しを介して取得する自動簿記の代わりになる再帰ソリューション)

別のオプションとして、幅優先再帰と深さ優先があります。

于 2012-08-03T19:30:16.470 に答える