如何解有环的图

Question

我正在尝试在 Java 的帮助下找到下一个问题的解决方案。我有一个图表，这是它的外观的一个很好的例子：

有它的符号：

[ {A = {C = 0.7}，{D = 0.3}}， {C = {输出 = 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}},
{E = {G = 0.3},{out = 0.7}}, {G = {B = 0.2}{out = 0.8}}， ...

S - 是起始节点（S = 1），out - 是离开图表的路。

我想跟踪图表并知道每个节点有多少百分比。 例如，A = 0.4*S (S = 1)、C = 0.7A + 0.1D、D = 0.3A + 0.7B

我认为可以通过递归（有向图的 DFS，特别是 Tarjan 的算法）来做到这一点，但是虽然存在循环，但我认为这没有帮助。另一种解决方案是求解线性方程组。 我不知道什么更好，也许有一些针对此类任务的解决方案。 这个例子只是一个例子，但我应该考虑到我有类似的appr。 2000 个节点（谁知道有多少个周期）。

你会怎么做？

Answer 1

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

您可以尝试使用高斯消除。我非常确定您可以在网络上找到已经编写的 Java 代码来为您完成此操作。

Answer 2

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

好的，问题给出了一个图G，对于每个节点来计算该节点被访问的概率。这是一个精确的算法。

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

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