一千萬個為什麽

搜索

查找具有約束的循環

給出一個圖形,其中每個頂點$ A_i $的浮點值$ B(i)$介於0和1之間。 如何找到一個具有頂點$ [C_1,C_2,...,C_k] $的循環(如果存在的話)違反以下條件:$ \ sum(B(C_i)])\ le k/2 $(整數除法) )? 謝謝。

最佳答案

我假設您的圖表是無向的。

If you allow $k/2$ without integer division, then you can reduce your problem to computing the maximum mean weight cycle. Replace every undirected edge by two directed egdes. Every edge leaving a node $A_i$ gets value $B(i)$. Compute a cycle of maximum mean weight (i.e., with maximum average edge weight). You condition is violated if and only if the maxium mean weight is $> 1/2$.

可以計算最大平均重量循環以及最小平均重量循環 在Karp算法的多項式時間內,見Cormen,Leiserson,Rivest,Stein。

如果你堅持整數除法,事情會變得更加微妙,因為可能有幾個 最大平均重量循環和較長的循環可以滿足界限,但較短的循環不需要。你可以略微減少權重(通過一個可忽略不計的常數$ \ epsilon $) 與你的邊緣權重相比)。這將有利於更短的周期,你可能會逃避這一點。

轉載註明原文: 查找具有約束的循環