如何解決帶週期的圖形

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的大小。我不確定你的週期是什麼樣的。