2

次の図のようなグラフを保持するデータ構造があります。 ツリー データ構造

このツリーでは、ノードはその下のレベルから任意の数の一意の子を持つことができます。写真のツリー内は一連のパスを表します。すべてのパスは、レベル 1 のノードで開始し、「*」マークのノードで終了する必要があります。したがって、図のツリーのパスは次のとおりです。

A then C then G

A then C then G then J

A then D then G

A then D then G the J

A then D then K, and so on...

実際、私の元のツリーは巨大 (約 200 万シーケンス) で、レベルあたりの最大ノード数は 61 (11 レベル中) です。そのため、私のアプリケーション (SAMSUNG 用のコンピューター ビジョン アプリケーション) で多くのメモリ消費の問題が発生します。

私の目標は、これらのパスをよりコンパクトな文字列形式で表す反復アルゴリズムを持つことです。ですから、問題は次のように 3 つのステップに分けられると思います。ツリー データ構造を構築しました (ステップ 2)が、ステップ 3 でツリーから出力文字列/シーケンスを取得する反復アルゴリズムを導出できません。

1- 入力文字列:

(A C G) | (A C G J) | (A D G) | (A D G J ) | (A D K) | ....、

ここで「|」代替手段を表します。

2- これらのパスのツリー データ構造の構築。

3- 必要な出力文字列:

(A (C G [J]) | (D (G [J]) | K)) | (B ....).

どこどこ "|" は選択肢を表し、「[ ]」はオプションを囲みます。ターゲット出力文字列は、より単純化するために使用できる一般的な要因がないように最適化する必要があります。

4

2 に答える 2

2

スタックを利用して未処理のノードを追跡する反復 DFS の変更を使用できます。このアルゴリズムは、1 つのノードのスタックに 6 文字を超える文字を格納することはありません* 。スタック上のノードは常に N 未満です (N はグラフ内のノードの数)。N が最大で 61*11=671 になることを示したので、スタックで最大約 4000 の要素が可能になります。

以下の疑似コードでは、「宛先」ノードは、上記の例のスター付きノード、たとえば G *です。

初期化:

ダミー ノード Φ は、Φ から「ルート」ノードのそれぞれ、たとえば上のノード A と B へのエッジで導入されます。Φ のトークンは非印刷文字であると見なされます。または、出力文字列に追加する前に明示的に確認できます。ノード Φ は、関数を呼び出す前にスタックにプッシュされます。

outString := ""
while stack not empty
   pop token
   if token is node
      outString := outString + node(token)  // Line 5 - explanation below
      if node(token) has children
         if node(token) is destination
            outString := outString + "["
            push "]"
         end
         if node(token) has multiple children
            for each child of node(token), from right to left
               push ")"
               push child
               push "("
               push "|"
            end
            pop // remove last "|"
         else
            push child
         end
      end

   else // token is ()[]|
      outString := outString + token
   end
end

グラフの最初の部分 (A とその子) に対するこのアルゴリズムの出力は次のとおりです (わかりやすくするために余分なスペースが追加されています。スペースはコードに簡単に追加できます)。

A (C G [J]) | (D (G [J]) | (K))

あなたの結果と私の結果の違いに気付くでしょう: 最終ノード K は、私のソリューションでは括弧で囲まれています。これが望ましくない場合 ( のような醜さになる可能性がA[(B)|(C)]あります)、ノード トークンをスタックからポップするときに追加のチェックを実行することで、これを排除できますが、追加のオーバーヘッドが発生します。上記の 5 行目を次のように置き換えるだけです。

if (node(token) has no children
    AND last character of outString is "("
    AND next token on stack is ")")
      remove trailing "(" from outString
      concatenate token to outString
      pop ")" from stack and ignore
else
   outString := outString + node(token) // as above
end

ご不明な点がございましたら、お気軽にお問い合わせください。

*これは、(おそらく非常にありそうもない) ノードが と書かれている場合に発生します|[(A)]。ほとんどのノードは、スタック内で 4 文字以下しか占有しません。

于 2013-05-03T00:38:34.127 に答える
1

これは完全な答えではないことに注意してください。ただし、画像とすべてをコメントに入れることはできませんでした。

このグラフを考えると：

グラフ

解決策 1

(A (B | C) E*) | (A B D*) | (A C F*)

解決策 2

(A B (D* | E*)) | (A C (E* | F*))

解決策 3

(A (B (D* | E*) | C (E* | F*)))

質問

このあいまいさをどのように解決したいですか？「その」答えとして探しているものを正確に定義する必要があります。

于 2013-05-02T16:38:15.820 に答える