ocaml - ocamlグラフトラバーサル：訪問したノードを維持するにはどうすればよいですか？

Question

DFSを使用してグラフをトラバースしようとしています。

しかし、訪問したノードのリストを関数のパラメーターとして渡そうとすると、問題があることがわかりました。

前のノード以外に接続されたノードがないノードに到達すると、再帰呼び出しが終了し、訪問したノードに関する情報が消えるので、無限ループに陥ります...

命令型の方法を使用する以外に、訪問したノードに関する情報を保持する方法はありますか？

score 4 · Accepted Answer

ジェフリーの答えを詳しく説明すると、いくつかの異なるスタイルが利用可能です。ここではテストしていないスニペットのみを示しているため、大小の間違いがある可能性があります。

どこでも副作用を使用できます。

module NodeSet = Set.Make(...)

let traverse action graph_root =
  let visited = ref NodeSet.empty in
  let rec loop node =
    action node;
    visited := NodeSet.add node !visited;
    let handle child =
      if not (NodeSet.mem child !visited)
      then loop acc child in
    List.iter handle (children node)
  in loop graph_root

「訪問」はaction、グラフ内のすべてのノードに命令関数を適用します。

訪問したノードを変更可能な参照に保存できますが、acc副作用を直接順序付けするのではなく、トラバーサルの状態をアキュムレータとしてスレッド化します。これは State モナドの使用に対応します。

let traverse action init_state graph_root =
  let visited = ref NodeSet.empty in
  let rec loop acc node =
    let acc = action acc node in
    visited := NodeSet.add node !visited;
    let handle acc child =
      if NodeSet.mem child !visited
      then acc
      else loop acc child in
    List.fold_left handle acc (children node)
  in loop init_state graph_root

この状態を渡すロジックを再利用して、訪問したノード情報も渡すことができます。

let traverse action init_state graph_root =
  let rec loop acc visited node =
    let acc = action acc node in
    let visited = NodeSet.add node visited in
    let handle (acc, visited) child =
      if NodeSet.mem child !visited
      then (acc, visited)
      else loop acc visited child in
    List.fold_left handle (acc, visited) (children node)
  in loop init_state NodeSet.empty graph_root

最後に、最初の再帰呼び出しで次に計算する必要があるノードに関する情報を渡すことで、末尾再帰トラバーサルに移行できます。これは、Continuation Passing Style への一般的な変換に対応しますが、継続のドメイン固有の表現 (単に訪問するノード) を伴います。
```
let traverse action init_state graph_root =
  let rec loop acc visited = function
    | [] -> acc
    | node::to_visit ->
       if NodeSet.mem node visited then loop acc visited to_visit
       else begin
         let acc = action acc node in
         let visited = NodeSet.add node visited in
         let to_visit = children node @ to_visit in
         loop acc visited to_visit
       end
  in loop NodeSet.empty init_state [graph_root]
```
Jeffrey は、このプレゼンテーションでは、更新方法を変更するだけでトラバーサルの順序を DFS から BFS に変更できto_visit 、シーケンスの最初ではなく最後に子ノードを追加することができると述べています (アルゴリズム的に効率的なキュー構造が必要です)。 .

score 2 · Accepted Answer

これを調べる 1 つの方法は、戻るのではなく、グラフ内の他の可能なノードを試すために先に進みたいということです (たとえば、ツリーをトラバースするために行うように)。訪問したノードだけでなく、訪問する予定のノードを記述するパラメータを持つことができます。to-visit パラメーターは、最初は最初のノードです。新しいノードに到達するたびに、未訪問の隣接ノード (訪問済みノードセットを見ればわかります) を未訪問ノードセットに追加し、この方法で再帰的に続行します。したがって、DFS と BFS の違いは、アクセスするノードのリストを順序付ける方法にあります。

関数型プログラミングでは、関数から戻る代わりに関数を呼び出して次のことを行うことがよくあります。(これが、末尾再帰が重要な場合がある理由です。)

ocaml - ocamlグラフトラバーサル：訪問したノードを維持するにはどうすればよいですか？

2 に答える 2

Related

Reference