5

我有一个循环加权有向图，目标是消除路径中存在的循环。

例如：路径如下，

from | to | weight
------------------
a    -> b | 0.5
a    -> c | 0.5
c    -> e | 1
b    -> d | 1
d    -> a | 0.25
d    -> f | 0.75

图中的循环由路径 d -> a 引入。任何人都可以通过调整其他节点的权重来建议一种算法来消除循环 d -> a。得到的无环图在将权重传递给端节点 e、f 方面是等价的。

谢谢，维维克

4

2 回答 2

4

Sleator–Tarjan 将此称为非循环流问题，并在他们关于动态树的第一篇论文的第 389 页上描述了 O(m log n) 时间的解决方案。如果你不需要最快的算法，重复使用深度优先搜索找到一个流循环，然后反向发送取消一个或多个弧的最小流。

在您的图表上：

a    -> b | 0.5
a    -> c | 0.5
c    -> e | 1
b    -> d | 1
d    -> a | 0.25
d    -> f | 0.75

DFS 找到一个循环a -0.5> b -1> d -0.25> a。-0.25在同一个周期发送。

a    -> b | 0.5 - 0.25 = 0.25
a    -> c | 0.5
c    -> e | 1
b    -> d | 1 - 0.25 = 0.75
d    -> f | 0.75

我们删除

d    -> a | 0.25 - 0.25 = 0

流动是非循环的，所以我们停止。

于 2013-05-22T11:53:19.050 回答
2

从您对大卫答案的评论以及图表的权重来看，在我看来，权重是从一个节点移动到另一个节点的概率（或从一个节点移动到另一个节点的单位的百分比，无论数学是相同）。如果是这样，则可以将其建模为马尔可夫链，更具体地说，可以将其建模为吸收马尔可夫链。但首先，我们需要添加两条路径以符合正式定义：

e -> e | 1.0
f -> f | 1.0

我不确定您是否需要针对多个类似于此的图形的通用算法，或者这是您需要解决的唯一图形。我将概述此特定图表所涉及的数学，并希望您可以在需要时将其推广到算法中。

算法相当繁琐，请按照吸收马尔可夫链环进行。

首先，我们需要邻接矩阵，在处理马尔可夫链时更常称为状态转移矩阵：

  |  a     b     c     d  |  e     f
--+-----------------------+------------
a |  0     0.5   0.5   0  |  0     0
b |  0     0     0     1  |  0     0
c |  0     0     0     0  |  1     0
d |  0.25  0     0     0  |  0     0.75
--+-----------------------+------------
e |  0     0     0     0  |  1     0
f |  0     0     0     0  |  0     1

矩阵的左上部分是瞬态（非结束）状态（由Q表示）之间的转换，右下部分是吸收状态。右上角将由R表示。

基本矩阵，计算为N = ( I - Q ) -1。而吸收概率（即给定无限时间，将最终处于每个吸收状态的百分比）为B = NR。使用我最好的 ASCII 矩阵，该图的数字是：

         +-          -+             +-    -+  
         | 8  4  4  4 |             | 4  3 |
         | 2  8  1  8 |             | 1  6 |
N = (1/7)| 0  0  7  0 |    B = (1/7)| 7  0 |
         | 2  1  1  8 |             | 1  6 |
         +-          -+             +-    -+

读取B矩阵的顶行，从状态 a 开始，有 4/7（大约 0.5714）的机会进入状态 e，有 3/7（大约 0.4286）的机会进入状态 f . 您可以忽略其他三行，因为它们是从状态 b、c 和 d 开始时的概率。

因此，如果您想要一个等效图，其中结束状态 e 和 f 的最终机会相同，但没有循环，您可以删除 d -> a 路径，并使用以下权重：

a -> b | 0.4286
a -> c | 0.5714
于 2013-05-24T22:51:55.987 回答