令 G 为包含环的未加权有向图。我正在寻找一种算法，它可以找到/创建所有非循环图 G'，由 G 中的所有顶点和 G 的边子集组成，足够小以使 G' 非循环。
更正式：所需的算法消耗 G 并创建一组非循环图 S，其中 S 中的每个图 G' 满足以下属性：
- G'包含G的所有顶点。
- G' 包含 G 的边的子集，因此 G' 是非循环的。
- G' 的边数最大化。这意味着：不存在满足性质 1 和 2 的 G''，使得 G'' 包含的边数多于 G' 和 G'' 是无环的。
背景：原始图 G 对元素之间的成对排序进行建模。由于图中存在循环，因此不能将其用作对所有元素的排序。因此，最大无环图 G' 应该对该排序建立尽可能最好的近似模型，尝试尽可能多地尊重成对排序关系。
在一种简单的方法中，可以删除所有可能的边缘组合，并在每次删除后检查非循环性。在这种情况下，存在强烈的变化分支树，这意味着时间和空间复杂度很差。
注意：问题可能与生成树有关，您可以将 G' 图定义为一种directed生成树。但请记住，在我的场景中，G' 中的一对边可能具有相同的起始或相同的结束顶点。这与一些有向生成树的定义相冲突文学 http://research.nii.ac.jp/~uno/papers/isaac96web.pdf.
编辑：添加了与生成树相关的直观描述、背景信息和注释。
这个问题被称为反馈弧集 http://en.wikipedia.org/wiki/Feedback_arc_set。由于它是 NP 难的，因此您不太可能找到可扩展的快速算法。但是，如果您的实例很小，那么诸如 B. Schwikowski 和 E. Speckenmeyer 所著的论文“枚举反馈问题的所有最小解决方案”中的算法可能会起作用。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
