3622
правки
Изменения
м
Нет описания правки
'''for''' i = 0 '''to''' m - 1
'''if''' input[i][0] == input[i][1] '''and''' input[i][2] == 1
absorbing[input[i][0]] = ''true;'' abs++;
</code>
Найдем число несущественных состояний <tex>nonabs = n - abs</tex>. Теперь нужно заполнить матрицы <tex>Q</tex> (переходов между несущественными состояниями) и <tex>R</tex> (переходов из несущественных состояний в поглощающие). Для этого создадим сначала массив <tex>position</tex> где <tex>i</tex>-ый элемент указывает под каким номером будет находиться <tex>i</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
<code style = "display: inline-block;">
count_q = 0; count_r = 0;
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r; count_r++;
'''else'''
position[i] = count_q; count_q++;
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[input[i][1]]
'''if''' !absorbing[input[i][0]]
R[position[input[i][0]]][position[input[i][1]]] = input[i][2];
'''else'''
Q[position[input[i][0]]][position[input[i][1]]] = input[i][2];
</code>
Найдем Матрицу <tex>E = I - Q</tex> и создадим единичную матрицу <tex>N</tex>.
<code style = "display: inline-block;">
'''for''' i = 0 '''to''' nonabs - 1
N[i][i] = 1; E[i][i] = 1;
'''for''' j = 0 '''to''' nonabs - 1
E[i][j] -= Q[i][j];
</code>
Теперь приведем матрицу <tex>E</tex> к единичной методом Гаусса - Жордана, применяя те же преобразования к матрице <tex>N</tex>.
<code style = "display: inline-block;">
'''for''' i = 0 '''to''' nonabs - 1
'''if''' E[i][i] != <tex> \neq </tex> 1 mul = E[i][i];
'''for''' j = 0 '''to''' nonabs - 1
E[i][j] /= mul; N[i][j] /= mul;
'''for''' row = 0 '''to''' nonabs - 1
'''if''' i != <tex> \neq </tex> row mul = E[row][i];
'''for''' j = 0 '''to''' nonabs - 1
E[row][j] -= mul * E[i][j]; N[row][j] -= mul * N[i][j];
</code>
В результате <tex>N = E^{-1}</tex> т.е. <tex>N</tex> - фундаментальная матрица Марковской цепи. Найдем матрицу <tex>G = NR</tex>.
'''for''' i = 0 '''to''' nonabs - 1
'''for''' j = 0 '''to''' abs - 1
G[i][j] = 0;
'''for''' k = 0 '''to''' nonabs - 1
G[i][j] += N[i][k] * R[k][j];
</code>
Выведем ответ: в <tex>i</tex>-ой строке вероятность поглощения в <tex>i</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>p_i=(($$\sum_{k=1}^n G[k][j]$$)+1)/n</tex> где <tex>j</tex> - номер соответствующий <tex>i</tex>-ому состоянию в матрице <tex>G</tex> (т.е. под которым оно располагалось в матрице <tex>R</tex> т.е. значение <tex>position[i]</tex>). Прибавлять 1 нужно т.к. вероятность поглотиться в <tex>i</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна 1.
<code style = "display: inline-block;">
'''for''' i = 0 '''to''' n - 1
prob = 0;
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]; prob++; prob /= n; println(prob);
</code>
