2

如果我要将一组对象的依赖关系组织到一个 DAG 中，在什么情况下这比另一个数据结构（如 BDD（二元决策图））更可取？

4

2 回答 2

3

DAG 有几个非常适合分析依赖关系的属性。

首先，您可以轻松识别系统的“基本级别”组件。这些是 DAG 中没有边进入它们的节点。了解系统的相关层意味着您了解重构的影响。（一切都在链条上。）

其次，如果您可以生成 DAG，您就知道系统没有奇怪的相互依赖关系。依赖图中的循环意味着你有两个相互依赖的组件——一个奇怪的错误和构建错误的秘诀。在微软，我们使用了一个名为asmmeta的工具来解决这个问题。

于 2010-12-17T19:14:48.650 回答
1

我对二元决策图不是很了解，但维基百科似乎指出它们基本上是有向的、非循环的图。我对 DAG 有点了解。如果您可以将问题表示为 DAG，则可以确保您没有任何循环（如 Chris Smith 之前提到的）。

二叉决策树的另一个可能（或可能不）在这里相关的属性是它们是二元的。但是，我不确定您希望如何将问题建模为二元决策图。看起来 BDD 在每个节点上都有零个、一个或两个选择。我很难看到如何将依赖关系映射到此。将依赖关系映射到图表对我来说更有意义。

主要是，我认为这取决于你想在你的表示上运行什么算法。如果您不确定是否有 DAG，可以运行循环检测算法来告诉您是否存在。如果你想找到最短路径，你可以在上面运行Dijkstra's。我认为这真的取决于你想做什么，而且我知道你可以用一般图表做的事情，主要涉及证明它是一个 DAG。一旦你有了一个有向无环图，我想建立的大部分东西都已经建立起来了。但这只是我。

-Brian J. Stinar-

于 2010-12-17T21:58:06.627 回答