オブジェクトの依存関係のコレクションを DAG にまとめるとしたら、どのような状況で BDD (二分決定図) などの別のデータ構造よりも望ましいでしょうか?
2 に答える
3
DAG には、依存関係の分析に最適なプロパティがいくつかあります。
まず、システムの「基本レベル」のコンポーネントを簡単に識別できます。これらは、エッジが入っていない DAG 内のノードです。システムの相対的なレイヤーを知ることは、リファクタリングの影響を知ることを意味します。（チェーンのすべて。）
次に、DAG を作成できれば、システムに奇妙な相互依存関係がないことがわかります。依存関係グラフのサイクルは、互いに依存している 2 つのコンポーネントがあることを意味します。奇妙なバグやビルド エラーのレシピです。Microsoft では、この問題を回避するためにasmmetaというツールを使用しました。
于 2010-12-17T19:14:48.650 に答える
1
私は二分決定図についてはあまり詳しくありませんが、ウィキペディアには、それらが基本的に有向の非巡回グラフであると記載されているようです。DAGについて少し知っています。問題を DAG として表すことができれば、サイクルがないことを確認できます (Chris Smith が前述したように)。
ここで関連する可能性がある (または関連しない可能性がある) 二分決定木の別の属性は、それらが二分であるということです。ただし、問題を二分決定図にモデル化する方法がわかりません。BDD には、各ノードで 0、1、または 2 つの選択肢があるようです。依存関係をこれにどのようにマッピングするかを理解するのに苦労しています。依存関係をグラフにマッピングすることは、私にとって非常に理にかなっています。
主に、表現で実行したいアルゴリズムに依存すると思います。DAG があるかどうかわからない場合は、サイクル検出アルゴリズムを実行して、DAG があるかどうかを確認できます。最短経路を見つけたい場合は、ダイクストラを実行できます。これは実際に何をしたいかによると思います。一般的なグラフでできることは知っています。主にそれが DAG であることを証明することです。DAG を取得したら、確立したいことのほとんどが確立されています。それは私だけです。
-ブライアン・J・スティナー-
于 2010-12-17T21:58:06.627 に答える