如何用循环求解图

| 我正在尝试借助Java寻找下一个问题的解决方案。我有一张图,这是一个看起来很好的例子: 有其表示法: [{A = {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}},  {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个节点(谁知道多少个周期)。 你会怎么做?     
已邀请:
解决线性方程似乎是一个很好的方法。 您可以尝试使用高斯消除法。我很确定您可以在网络上找到已经编写的Java代码来为您完成此任务。     
注意:对于循环图,求解一个线性方程组不会给您带来概率。它给您期望的多重性。 好的,为每个节点提供一个图形G,以计算该节点被访问的概率。这是一个精确的算法。 计算图的强连接组件(SCC)。 对于每个SCC C,对于C中的每个可能的起始节点v,通过求解线性方程组来计算(a)离开C的弧的分布,以及(b)访问C中的每个节点的概率。我知道实现(b)的最好方法是考虑一个节点成对的乘积图。该对中的第一个元素是C中的节点。第二个元素是C中已被访问的节点的子集。弧是从C继承的。求解一些线性方程式以找出此新图中最后一个节点的分布。 当v和w在G的不同分量中并且有一条从v到w的路径时,在G的顶点上准备一个新的图形H,其弧线从v到w。该弧的概率由步骤2(a)确定。 解决关于H的无环问题。 对于每个节点,从步骤2(b)计算概率的加权和。 该算法在图的大小上基本上是线性的,但在SCC的大小上是指数的。我不确定您的周期长什么样。     

要回复问题请先登录注册