19
правок
Изменения
sta
==Описание алгоритмаПодсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> - массив переходов марковской цепи, где <tex>\mathtt{transition[i][2]}</tex> - вероятность перехода из состояния <tex>\mathtt{transition[i][0}</tex> в <tex>\mathtt{transition[i][1]}</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> - поглощающее состояние, то <tex>\mathtt{transition[j][2] = 1}</tex>. По этому признаку помно определить все поглощающие состояния в цепи.
===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> - массив состояний. Если i - посглощающее состояние absorbing[i] = true
*<tex>\mathtt{n}</tex> - количество состояний
absorbing[transition[i][0]] = ''true''
'''return''' absorbing
==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position[n]}</tex> - массив нумерации состояний относительно существенной/ несущественной матрицы.
*<tex>\mathtt{Q}</tex> - матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> - матрица из несущественных состояний в поглощающие.
'''procedure''' buildTransitionMatrix()
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[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia: Absorbing Markov chain]
