54
правки
Изменения
м
Косметические изменения, введена структура jump, исправлен псевдокод
==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex> jump. Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи<tex> \mathtt{jump}[\mathtt{m}], где <tex>\mathtt{transition}[\mathtt{i}][2]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]\mathtt{.to}</tex>.Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] \mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.
===Псевдокод===
*<tex>\mathtt{m}</tex> — количество переходов
'''boolean[]''' findAbsorbings(transition: '''floatjump'''[m][3]):
'''boolean''' absorbing[n]
'''for''' jump i = 0 '''to''' m - 1: transition absorbing[transition[i][0].from] = transition[i][0] .from == transition[i][1] .to '''and''' transition[i][2] .prob == 1
'''return''' absorbing
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.
'''procedurefloat[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1].to] '''if''' !absorbing[transition[i][0].from] R[position[transition[i][0].from]][position[transition[i][1].to]] = transition[i][2].prob
'''else'''
Q[position[transition[i][0].from]][position[transition[i][1].to]] = transition[i][2].prob '''return Q'''
== См. также ==
