5

最近、より複雑なアルゴリズム、正確には Tarjan のアルゴリズムの一部として非再帰的 DFS を実装する必要がありました。再帰的な実装は非常に洗練されていますが、大きなグラフには適していません。反復バージョンを実装したとき、それが最終的にいかに洗練されていないものになってしまったかにショックを受け、何か間違ったことをしたのではないかと思いました。

反復 DFS には 2 つの基本的なアプローチがあります。まず、ノードのすべての子を一度にスタックにプッシュできます (はるかに一般的なようです)。または、1 つだけプッシュすることもできます。誰もがそうしているように見えるので、最初のものに焦点を当てます。

このアルゴリズムにはさまざまな問題がありましたが、最終的には、効率的に行うには、1 つではなく 2 つではなく 3 つのブール値フラグが必要であることに気付きました (必ずしも 3 つの明示的なブール変数が必要であるとは限りません。情報を間接的に保存することもできます)。通常は整数である変数の特別な値を使用しますが、何らかの方法でこれら 3 つの情報にアクセスする必要があります.3 つのフラグは: 1) 訪問済みです。これは、子が非常に冗長にスタックにプッシュされるのを防ぐためでした。2) 完了。同一ノードの重複処理を防止する。3) 昇順/降順。子がすでにスタックにプッシュされているかどうかを示します。擬似コードは次のようになります。

while(S)
    if S.peek().done == True
        S.pop()
        continue

    S.peek().visited = True

    if S.peek().descending == True
        S.peek().descending = False
        for c in S.peek().children
            if c.visited == False
                S.push(c)
        doDescendingStuff()    
    else
        w = S.pop()
        w.done = True
        doAscendingStuff()

いくつかのメモ: 1) 技術的に昇順/降順は必要ありません。子がすべて完了しているかどうかを確認するだけでよいからです。しかし、密なグラフではかなり非効率的です。

2) 主なキッカー: 訪問/完了は必要ないように見えるかもしれません。これが（私が思うに）あなたがそれを必要とする理由です。スタック上でそれらを訪問するまで、訪問済みのものをマークすることはできません。もしそうなら、物事を間違った順序で処理することができます。たとえば、A が B と C にリンクされ、B が D にリンクされ、D が C にリンクされているとします。次に、A から B と C をスタックにプッシュします。B から D をスタックにプッシュします。スタックにプッシュするときに訪問したものをマークしている場合は、ここで C をスタックにプッシュしません。しかし、これは間違っています。このグラフでは、A からではなく、D から C にアクセスする必要があります (A が C の前に B にアクセスすると仮定)。したがって、それらを処理するまで、訪問したものをマークしません。ただし、スタックに C が 2 回あります。したがって、完全に完了したことを示す別のフラグが必要なので、C を 2 回処理する必要はありません。

このすべてを回避して、巻き戻しと巻き戻しの両方のアクションをサポートする完全に正しい非再帰的 DFS を作成する方法がわかりません。しかし、本能的にそれは不器用に感じます。より良い方法はありますか？私がオンラインで調べたほとんどすべての場所で、非再帰的 DFS を実際に実装する方法について、実際に行うことができ、非常に基本的なアルゴリズムを提供していると述べています。アルゴリズムが正しい場合 (同じノードへの複数のパスを適切にサポートするという点で) はまれですが、ワインディングとアンワインドの両方で処理を適切にサポートすることはめったにありません。

4

7 に答える 7

2

最も洗練されたスタックベースの実装では、ノードではなく、スタック上に子のイテレータが存在すると思います。イテレータは、ノードとその子の位置を格納するのと同じように考えてください。

while (!S.empty)
  Iterator i = S.pop()
  bool found = false
  Iterator temp = null
  while (i.hasNext())
    Node n = i.next()
    if (n.visited == false)
      n.visited = true
      doDescendingStuff(n)
      temp = n.getChildrenIterator()
      break
  if (!i.hasNext())
    doAscendingStuff(i.getNode())
  else
    S.push(i)
  if (temp != null)
    S.push(temp)

上記は、ノードと位置を2つのスタックに分離することにより、ストレージスペースに最適化できます。

于 2013-02-03T02:36:40.767 に答える
1

あなたのコードは、再帰的な DFS 実装で何が起こるかを完全にはエミュレートしていません。再帰的な DFS の実装では、すべてのノードは常にスタックに 1 回だけ表示されます。

Dukeling によって与えられた解決策は、それを繰り返し行う方法です。基本的に、一度にすべてのノードをプッシュするのではなく、一度に 1 つのノードのみをスタックにプッシュする必要があります。

これにはより多くのストレージが必要であるというあなたの主張は間違っています。あなたの実装では、ノードはスタック上に複数回存在する可能性があります。実際、非常に密集したグラフ (すべての頂点の完全なグラフ) から開始すると、これが発生します。Dukeling ソリューションでは、スタックのサイズは O(頂点の数) です。あなたのソリューションでは、それは O(エッジの数) です。

于 2015-06-06T07:53:51.867 に答える
0

Robert Sedgewick の cpp book のアルゴリズムでは、アイテムのコピーを 1 つだけ保持し、古いコピーを忘れる特別なスタックについて説明しています。これを行う方法については完全にはわかりませんが、スタックに複数のアイテムがあるという問題が解消されます。

于 2015-02-18T13:33:28.217 に答える