22

私の webapp には、他のフィールドを合計する多くのフィールドがあり、それらのフィールドはさらに多くのフィールドを合計します。これが有向非巡回グラフであることは知っています。

ページが読み込まれると、すべてのフィールドの値が計算されます。私が実際にやろうとしているのは、フィールドを計算するための効率的な順序を含む 1 次元のリストに DAG を変換することです。

例: A = B + D、D = B + C、B = C + E 効率的な計算順序: E -> C -> B -> D -> A

現在、私のアルゴリズムは List への単純な挿入を繰り返し行うだけですが、それが壊れ始める状況に遭遇しました。代わりに、すべての依存関係をツリー構造に変換し、そこからそれを 1 次元形式に変換する必要があると考えています。このようなツリーを効率的な順序付けに変換するための簡単なアルゴリズムはありますか?

4

2 に答える 2

29

トポロジカルソートをお探しですか? これにより、DAG に順序付け (シーケンスまたはリスト) が課されます。たとえば、計算のためにセル間の依存関係を把握するために、スプレッドシートで使用されます。

于 2009-07-28T06:24:20.513 に答える
9

必要なのは、深さ優先検索です。

function ExamineField(Field F)
{
    if (F.already_in_list)
        return

    foreach C child of F
    {
        call ExamineField(C)
    }

    AddToList(F)
}

次に、各フィールドで ExamineField() を順番に呼び出すだけで、リストは仕様に従って最適な順序で入力されます。

フィールドが循環的である場合 (つまり、A = B + C、B = A + D のようなものがある場合)、無限ループに入らないようにアルゴリズムを変更する必要があることに注意してください。

あなたの例では、呼び出しは次のようになります。

ExamineField(A)
  ExamineField(B)
    ExamineField(C)
      AddToList(C)
    ExamineField(E)
      AddToList(E)
    AddToList(B)
  ExamineField(D)
    ExamineField(B)
      (already in list, nothing happens)
    ExamineField(C)
      (already in list, nothing happens)
    AddToList(D)
  AddToList(A)
ExamineField(B)
  (already in list, nothing happens)
ExamineField(C)
  (already in list, nothing happens)
ExamineField(D)
  (already in list, nothing happens)
ExamineField(E)
  (already in list, nothing happens)

リストは C、E、B、D、A となります。

于 2009-07-28T06:31:47.550 に答える