如何解决带周期的图形

Question

我正在尝试通过Java的帮助找到下一个问题的解决方案。我有一个曲线图，这是它如何能看一个很好的例子：

有其符号：

[{甲 = {C = 0.7}，{d = 0.3 }}， {C = {out = 0.2}，{F = 0.8}}， {D = {C = 0.1}，{F = 0.2}，{G = 0.3}，{E = 0.4 }}， {S = {A = 0.4}，{B = 0.6}}，
{Ê = {G = 0.3}，{出= 0.7}}，{ ģ = {B = 0.2} {出= 0.8}}，...

小号 - 是一个起始节点（S = 1），out - 是一种出图的方式。

我想跟踪图表并知道每个节点有多少百分比。 在例如，甲 = 0.4 * S（S = 1），Ç = 0.7A + 0.1D，d = 0.3A + 0.7B

我认为这是可能的递归来做到这一点（有向图的DFS，特别是Tarjan的alg。），但是有些周期我不认为会有帮助。另一个解决方案是解决一个线性方程组。 我不知道什么是更好的工作，也许有一些解决方案存在这种任务。 这个例子只是一个例子，但我应该考虑，我喜欢appr。 2000个节点（以及谁知道多少个周期）。

你会怎么做？

Answer 1

解线性方程似乎是一个非常好的方法。

您可以尝试使用Gaussian Elimination。我非常肯定你可以找到已经编写好的Java代码，在网络上为你做。

Answer 2

注意：对于循环图，求解一个线性方程组不会给出概率。它给你预期的多样性。

好的，问题给出了图G，为每个节点计算访问该节点的概率。这是一个确切的算法。

1. 计算图的强连通分量（SCC）。
2. 对于每个SCC Ç，对于每个可能的起始节点v在Ç，通过求解线性方程组计算的（a）弧的分布离开Ç和（b）的概率与每个访问节点C。我知道要实现（b）的最佳方式是考虑节点是成对的产品图。该对中的第一个元素是C中的节点。第二个元素是已访问的C中的节点子集。弧从继承，C。求解一些线性方程来找出这个新图中最后一个节点的分布。
3. 从v准备上的ģ顶点与弧一个新的图ħ到瓦特当v和瓦特是在不同组件ģ并且存在从v程序的一个路径至w。这个弧的概率在步骤2（a）中确定。
4. 解决H上的非循环问题。
5. 对于每个节点，计算来自步骤2（b）的概率的加权和。

该算法在该图的大小基本上是线性的，但指数在SCC的大小。我不确定你的周期是什么样的。