假设G是一个包含循环的加权有向图。我正在寻找一种算法，通过删除循环中最小权重的边来查找并删除这些循环。
我认为可能可以进行多个深度优先搜索，但想知道是否存在更成熟的解决方案。
谢谢帮助 :)
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。
反馈弧集的启发式算法是一个活跃的研究领域。这篇论文似乎是一个很好的起点：https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230200102。
- Lukas Barth
2
这个问题似乎是针对非加权有向图的，因此加权图的版本也必须是NP难的，但不完全是同一个问题。 - kaya3
1哦，是的 - 我显然在问题中忽略了“加权”这个词。因此，这个问题是“加权反馈弧集”。:) 仍然是NP难问题，仍然没有好的近似解法，但恐怕现在可用的启发式算法可能会更少。 - Lukas Barth
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
p_i, i=1..4，除了它们的端点之外互不相交的情况，其中p_1、p_2连接顶点v和w，而p_3、p_4连接w和v。还假设p_1、p_3分别包含全局最小权重的两条边中的一条。根据你是选择C1={p_1, p_3}, C2={p_2, p_4}还是C1'={p_1, p_4}, C2'={p_2, p_3}，你将移除不同的边，并得到一个不同的无环图的总权重。 - collapsar