馬爾可夫鏈：查找終端狀態計算

我想弄清楚這個問題。希望有人能告訴我如何完成這一點。我諮詢了以下頁面，但是我無法在java/python中編寫能夠產生正確輸出並通過所有測試用例的代碼。我會很感激任何和所有的幫助。馬爾可夫鏈：查找終端狀態計算

Markov chain probability calculation - Python

Calculating Markov chain probabilities with values too large to exponentiate

寫功能應答（M），其採用非負整數的數組的代表有多少次該狀態已經到下一個狀態，並返回整數的數組，每個數組終端狀態給出每個終端狀態的確切概率，表示爲每個狀態的分子，然後以最簡單的形式表示所有終端的分母。矩陣最多爲10乘10.保證無論礦石處於哪種狀態，都有從該狀態到終端狀態的路徑。也就是說，處理總是會以穩定的狀態結束。礦石從狀態0開始。分子在計算過程中將符合一個有符號的32位整數，只要定期簡化分數即可。例如，考慮矩陣M：

[ 
[0,1,0,0,0,1], # s0, the initial state, goes to s1 and s5 with equal probability 
[4,0,0,3,2,0], # s1 can become s0, s3, or s4, but with different probabilities 
[0,0,0,0,0,0], # s2 is terminal, and unreachable (never observed in practice) 
[0,0,0,0,0,0], # s3 is terminal 
[0,0,0,0,0,0], # s4 is terminal 
[0,0,0,0,0,0], # s5 is terminal 
] 

    So, we can consider different paths to terminal states, such as: 

    s0 -> s1 -> s3 

    s0 -> s1 -> s0 -> s1 -> s0 -> s1 -> s4 

    s0 -> s1 -> s0 -> s5 

    Tracing the probabilities of each, we find that 

    s2 has probability 0 

    s3 has probability 3/14 

    s4 has probability 1/7 

    s5 has probability 9/14

來源

2016-11-05 ezio

我不知道的邊緣情況的結果應該是什麼樣的，但我就是這樣做的這個問題是：

創建第二矩陣它把每個概率的所有分母加起來，將每一行中的所有分子相加。
查找矩陣中用作非終端狀態邊界的第一個終端狀態。
從相同大小的單位矩陣中減去由第一終端界定的矩陣。
找出差異的倒數。有幾種方法可以做到這一點，我決定用差異來擴大匹配的單位矩陣。
將逆矩陣乘以從第一個終端到矩陣尾部的矩陣。
然後，找到結果分母並返回從第一個終端到矩陣尾部的矩陣的第一行分子。

旁註：

你需要編寫簡化分數（您可能還需要編寫GCF和LCM功能，幫助用戶簡化）一個簡化的功能。
您可能還需要對矩陣進行排序，以使終端位於矩陣的末尾，因此它的格式正確。
邊緣情況：1x1矩陣，僅具有1個非終端狀態的矩陣，10x10矩陣，僅具有1個終端狀態的矩陣

來源

2017-04-21 04:12:05

馬爾可夫鏈：查找終端狀態計算

回答

相關問題