令 G 为包含循环的加权有向图。我正在寻找一种算法来通过删除循环的最小权重边缘来查找和删除这些循环。
我想我可能会做几个 DFS，但想知道是否有更完善的解决方案。
谢谢您的帮助 ：）
问问题
2411 次
1 回答
1
您尝试解决的问题称为（最小）反馈弧集。这是一个 NP 难题，因此您不会找到任何有效的、确定性的、最优算法。此外，没有“好的”近似算法是已知的。如果您知道您的反馈弧设置得很小，那么可以使用 FPT 算法。有关详细信息，请参阅https://en.wikipedia.org/wiki/Feedback_arc_set#Minimum_feedback_arc_set。
不过，反馈弧集的启发式是一个活跃的研究领域。这篇论文似乎是一个很好的起点：https ://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230200102
于 2018-08-02T14:45:47.110 回答