将加权直接循环图转换为等效非循环图 [英] Convert weighted direct cyclic graph to equivalent acyclic graph
问题描述
我有一个循环加权有向图，目标是删除路径中存在的循环。
例如：路径如下，
来自|到|重量
------------------
a-> b | 0.5
a-> c | 0.5
c-> e | 1
b-> d | 1
d->一个| 0.25
d-> f | 0.75
图中的循环由路径d-> a引入。谁能建议一种算法，通过调整其他节点的权重来消除周期d-> a。
感谢，
Vivek
从您的评论到David的答案，再从图形的权重，在我看来，权重是从一个节点移动到另一个节点的概率（或从一个节点移动到另一个节点的单位的百分比，无论哪种方法都相同）。如果是这样，可以将其建模为马尔可夫链，更具体地讲，应将其建模为吸收马尔可夫链。但是首先，我们需要添加两条路径以符合正式定义：
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-> b | 0.4286
a-> c | 0.5714
I have a cyclic weighted directed graph and the goal is to remove the cycle present in the path.
eg: the paths are as below,
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
the cycle in the graph is introduced by the path d -> a. Can anyone suggest an algorithm to remove the cycle d -> a by adjusting the weights of the other nodes. The resulting acyclic graph to be equivalent in terms of passing on the weights to the end nodes e, f.
Thanks, Vivek
From your comment to David's answer and from the weights of the graph, it looks to me like the weights are probabilities to move from one node to the other (or percentage of a unit that moves from on node to another, either way the math is the same). If so, this can be modeled as a Markov chain, and more specifically as an absorbing Markov chain. But first, we need to add two paths to fit the formal definition:
e -> e | 1.0
f -> f | 1.0
I'm not sure if you need a general algorithm for multiple graphs similar to this one or this is the only graph you need to solve. I'll give an overview of the math involved for this particular graph, and hopefully you can generalize it into an algorithm if you need it.
The arithmetic is pretty cumbersome, follow along on the absorbing Markov chain link.
First, we need the adjacency matrix, more commonly called the state transition matrix when dealing with Markov chains:
| 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
The top left portion of the matrix are the transitions between the transient (non-ending) states (symbolized by Q), the bottom right are the absorbing states. The top right will be symbolized by R.
The fundamental matrix, is calculated as N = (I - Q)-1. While the absorbing probabilities (i.e. given infinite time, the percentage that will end up in each of the absorbing states) is given as B = NR. Using my best ASCII matrices, the numbers for this graph are:
+- -+ +- -+
| 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 |
+- -+ +- -+
The top row of the B matrix is read, starting from state a, there's a 4/7 (approx. 0.5714) chance of ending up in state e, and a 3/7 (approx. 0.4286) chance of ending up in state f. You can ignore the other three rows, since those are the probabilities when starting in states b, c, and d.
Therefore if you want an equivalent graph where the end chance of ending up in states e and f are the same, but without the cycle, you can remove the d -> a path, and use the following weights:
a -> b | 0.4286
a -> c | 0.5714
这篇关于将加权直接循环图转换为等效非循环图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
