Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎Псевдокод: исправлен псевдокод)
м (→‎Псевдокод: добавлена инициализация Q и R)
Строка 29: Строка 29:
 
     '''int''' count_q = 0
 
     '''int''' count_q = 0
 
     '''int''' count_r = 0
 
     '''int''' count_r = 0
 +
    '''float''' Q[n][n]
 +
    '''float''' R[n][n]
 +
    '''int''' position[n]
 
   
 
   
 
     '''for''' i = 0 '''to''' n - 1
 
     '''for''' i = 0 '''to''' n - 1
Строка 38: Строка 41:
 
           count_q++
 
           count_q++
 
   
 
   
−
     '''for''' i = 0 '''to''' m - 1
+
     '''for''' '''jump''' i '''in''' transition
−
       '''if''' absorbing[transition[i].to]
+
       '''if''' absorbing[i.to]
−
           '''if''' !absorbing[transition[i].from]
+
           '''if''' !absorbing[i.from]
−
             R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
+
             R[position[i.from]][position[i.to]] = i.prob
 
       '''else'''
 
       '''else'''
−
           Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
+
           Q[position[i.from]][position[i.to]] = i.prob
 
   
 
   
 
     '''return''' Q
 
     '''return''' Q

Версия 16:15, 24 июня 2018

Подсчет количества поглощащих состояний

Для хранения переходов марковской цепи создадим структуру [math] \mathtt{jump}[/math].

Введем [math]\mathtt{transition}:[/math] [math] \mathtt{jump}[\mathtt{m}] [/math], где [math]\mathtt{transition}[\mathtt{i}]\mathtt{.prob}[/math] — вероятность перехода из состояния [math]\mathtt{transition}[\mathtt{i}]\mathtt{.from}[/math] в [math]\mathtt{transition}[\mathtt{i}]\mathtt{.to}[/math].

Тогда, по определению поглощающего состояния, если [math]\mathtt{j}[/math] — поглощающее состояние, то [math]\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1[/math]. По этому признаку можно определить все поглощающие состояния в цепи.

Псевдокод

  • [math]\mathtt{absorbing}[\mathtt{n}][/math] — массив состояний. Если [math]\mathtt{i}[/math] — посглощающее состояние [math]\mathtt{absorbing}[\mathtt{i}] = true[/math] иначе [math]\mathtt{absorbing}[\mathtt{i}] = false[/math]
  • [math]\mathtt{n}[/math] — количество состояний
  • [math]\mathtt{m}[/math] — количество переходов
boolean[] findAbsorbings(transition: jump[m]):
   boolean absorbing[n] 

   for jump i in transition 
      absorbing[i.from] = i.from == i.to and i.prob == 1

   return absorbing

Построение матриц переходов

Cоздадим сначала массив [math]\mathtt{position}[/math] где [math]\mathtt{i}[/math]-ый элемент указывает под каким номером будет находиться [math]\mathtt{i}[/math]-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.

Псевдокод

  • [math]\mathtt{position}[\mathtt{n}][/math] — массив нумерации состояний относительно существенной/несущественной матрицы.
  • [math]\mathtt{Q}[/math] — матрица перехода мужду несущественными состояниями.
  • [math]\mathtt{R}[/math] — матрица из несущественных состояний в поглощающие.
float[][] buildTransitionMatrix(absorbing: boolean[n], transition: jump[m]):
   int count_q = 0
   int count_r = 0
   float Q[n][n]
   float R[n][n]
   int position[n]

   for i = 0 to n - 1
      if absorbing[i]
         position[i] = count_r
         count_r++
      else 
         position[i] = count_q
         count_q++

   for jump i in transition
      if absorbing[i.to]
         if !absorbing[i.from]
            R[position[i.from]][position[i.to]] = i.prob
      else
         Q[position[i.from]][position[i.to]] = i.prob

   return Q

См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Подсчёт_количества_поглощающих_состояний_и_построение_матриц_переходов_марковской_цепи&oldid=66168»