1

二分木トラバーサルの方法でアプローチしようとしましたが、反復オクトツリートラバーサルの手順を理解できません。私の問題では、子ポインターと親ポインターを持つ octree ノードがあり、反復してリーフノードのみをスタックに格納したいと考えています。また、反復トラバーサルは再帰トラバーサルよりも高速ですか?

4

2 に答える 2

5

これは確かに二分木トラバーサルに似ていますが、中間情報を少し保存する必要があります。再帰アルゴリズム自体は遅くはありませんが、O(log8) 再帰呼び出しにはもう少し多くのスタック スペースを使用します (octree の 10 億要素に対して約 10 レベル)。反復アルゴリズムも効率的にするために同じ量のスペースが必要ですが、スタックがオーバーフローするのではないかと心配している場合は、ヒープに配置できます。

再帰的に行う（疑似コード）：

function traverse_rec (octree):
    collect value  // if there are values in your intermediate nodes
    for child in children:
         traverse_rec (child)

反復アルゴリズムに到達する最も簡単な方法は、スタックまたはキューを使用して、深さ優先または呼吸優先トラバーサルを行うことです。

 function traverse_iter_dfs(octree):
     stack = empty
     push_stack(root_node)
     while not empty (stack):
         node = pop(stack)
         collect value(node)
         for child in children(node):
             push_stack(child)

スタックをキューに置き換えると、ブレス ファースト検索が得られます。ただし、まだトラバースしていない O(7*(log8 N)) ノードの領域に何かを格納しています。あなたがそれについて考えるならば、あなたが本当に大きな木を横断する必要がない限り、それはそれほど悪いことではありません. 他の唯一の方法は、子で完了したときに親ポインターを使用することです。その後、何らかの形で次の兄弟を選択する必要があります。

ただし、現在のノードのインデックスを (その兄弟に関して) 事前に保存しない場合は、次の兄弟を見つけるために親のすべてのノードしか検索できず、基本的に作業量が 2 倍になります。完了します (ノードごとに、子だけでなく兄弟もループします)。また、少なくとも、すでに訪れたノードを覚えておく必要があるようです。それ以外の場合、ツリーをさらに下に降りるか、ツリーに戻るかは一般的に決定できないためです（誰かが間違っていることを証明してください）。

全体として、そのような解決策を探すことはお勧めしません。

于 2013-03-05T15:01:16.470 に答える
0

あなたの目標が何であるかによって異なります。ノードが表示されているかどうか、光線がその境界ボックスと交差するかどうか、またはポイントがノードに含まれているかどうかを確認しようとしていますか?

ポイントがノードに含まれているかどうか、または含まれている必要があるかどうかを確認するために、最後の作業を行っていると仮定しましょう。ポイントを取得し、それが Octnode のバウンディング ボックス内にあるかどうかをチェックするメソッドを Octnode に追加します。それが true を返す場合、それ以外の場合は false を返します。非常に単純です。ここから、ヘッド ノードから開始するドリル ダウン メソッドを呼び出し、単純な「for」ループで各子をチェックして、それがどの Octnode にあるかを確認します。最大でも 1 つです。

ここで、反復対再帰アルゴリズムの出番です。反復が必要な場合は、現在のノードへのポインターを保存し、このポインターをヘッド ノードからポイントを含むノードに交換します。次に、最大の深さに達するか、それを含む Octnode が見つからなくなるまでドリルダウンを続けます。再帰的なソリューションが必要な場合は、ポイントを見つけた Octnode でこのドリル ダウン メソッドを呼び出します。

反復と再帰は、速度の点でパフォーマンスに大きな違いがあるとは言えませんが、メモリ パフォーマンスの点では違いがある可能性があります。再帰するたびに、別の呼び出し深度をスタックに追加します。オクトリーが大きい場合、これにより多数の呼び出しが発生し、スタックが吹き飛ばされる可能性があります。

于 2013-03-05T14:51:20.947 に答える