Розробка класу для роботи з ланцюгами Маркова

Сьогодні я хотів би розповісти вам про написання класу для спрощення роботи з ланцюгами Маркова.

Прошу під кат.

Початкові знання:

Представлення графів у формі матриці суміжності, знання основних понять про графах. Знання C++ для практичної частини.

Теорія

Ланцюг Маркова — послідовність випадкових подій з кінцевим або рахунковим числом результатів, характеризується тим властивістю, що, кажучи нестрого, при фіксованому цьому майбутнє незалежно від минулого. Названа на честь А. А. Маркова (старшого).
Якщо говорити простими словами, то Ланцюг Маркова — це зважений граф. В його вершинах знаходяться події, а в якості ваги ребра, що з'єднує вершини A і B — ймовірність того, що після події A піде подія B.

Про застосування ланцюгів Маркова написано досить багато статей, ми ж продовжимо розробку класу.

Наведу приклад ланцюга Маркова:



Надалі ми будемо розглядати в якості прикладу цю схему.

Очевидно, що якщо з вершини A є тільки одне вихідне ребро, то його вага буде дорівнює 1.

Позначення
У вершинах у нас знаходяться події (від A, B, C, D, E...). На ребрах ймовірність того, що після i-го події буде подія j > i. Для умовності та зручності я пронумерував вершини (№1, №2 і т. д ).

Матрицею будемо називати матрицю суміжності орієнтованого зваженого графа, яким зображуємо ланцюг Маркова. ( про це далі ). В даному окремому випадку ця матриця називається матрицею перехідних ймовірностей або просто матрицею переходу.

Матричне уявлення ланцюга Маркова
Представляти ланцюга Маркова ми будемо за допомогою матриці, саме тієї матриці суміжності, якій представляємо графи.

Нагадаю:
Матриця суміжності графа G з кінцевим числом вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, в якій значення елемента aij дорівнює числу ребер з i-ї вершини графа в j-ту вершину.
Детальніше про матрицях суміжності — курс дискретної математики.

У нашому випадку матриця буде мати розмір 10x10, напишемо її:

0 50 0 0 0 0 50 0 0 0
 
0 0 80 20 0 0 0 0 0 0
 
0 0 0 0 100 0 0 0 0 0
 
0 0 0 0 100 0 0 0 0 0
 
0 0 0 0 0 100 0 0 0 0
 
0 0 0 0 0 0 0 0 0 0
 
0 0 0 0 0 0 0 70 30 0
 
0 0 0 0 0 0 0 0 0 100
 
0 0 0 0 0 0 0 0 0 100
 
0 0 0 0 0 100 0 0 0 0
 

Ідея
Подивіться уважніше на нашу матрицю. У кожному рядку у нас є ненульові значення в тих стовпцях, чий номер збігається з наступним подією, а саме ненульове значення — вірогідність, що ця подія настане.

Таким чином, ми маємо значення ймовірності настання події з номером, рівним номеру стовпця після події з номером, рівним рядка.

Ті хто знають теорію ймовірностей могли здогадатися, що кожен рядок — це функція розподілу ймовірностей.

Алгоритм обходу ланцюга Маркова

1) ініціалізуємо початкову позицію k нульовою вершиною.
2) Якщо вершина не кінцева, то генеруємо число m від 0...n-1 на основі розподілу ймовірності у рядку k матриці, де n — число вершин, а m — номер наступного події (!). Інакше виходимо
3) Номер текующей позиції k прирівнюємо до номеру згенерованої вершині
4) На крок 2

Зауваження: вершина кінцева якщо розподіл ймовірностей нульове (див. 6-ю рядок в матриці).

Досить витончений алгоритм, так адже?

Реалізація

В цю статтю я хочу окремо винести код реалізації описаного обходу. Ініціалізація та заповнення ланцюга Маркова не несуть особливого інтересу (повний код див. в кінці).

Реалізація алгоритму обходу
template < class Element> Element *Markov<Element>::Next(int StartElement = -1)
{

if (Markov<Element>::Ініціював) // якщо матриця суміжності створена
{

if (StartElement == -1) // якщо стартовий елемент за замовчуванням
StartElement = Markov<Element>::Current; // то продовжуємо ( в конструкторі Current = 0 )

std::random_device rd;
std::mt19937 gen(rd());
std::discrete_distribution<> dicr_distr(Markov<Element>::AdjacencyMatrix.at(Current).begin(),
Markov<Element>::AdjacencyMatrix.at(Current).end()); // ініціалізуємо контейнер для генерації числа на основі розподілу ймовірності


int next = dicr_distr(gen); // генеруємо наступну вершину
if (next == Markov<Element>::size()) // тонкощі роботи генератора, якщо розподіл ймовірностей нульове, то він повертає кількість елементів 
return NULL;

Markov<Element>::Current = next; // змінюємо поточну вершину
return &(Markov<Element>::elems.at(next)); // повертаємо значення у вершині
}
return NULL;
}



Даний алгоритм виглядає особливо просто завдяки особливостям контейнера discrete_distribution. На словах описати, як працює цей контейнер досить складно, тому візьмемо в приклад 0-ю рядок нашої матриці:

0 50 0 0 0 0 50 0 0 0

В результаті роботи генератора він поверне або 1, або 6 з ймовірностями в 0.5 для кожної. Тобто повертає номер стовпця ( що еквівалентно номером вершини в ланцюзі ) куди слід продовжити рух далі.

Приклад програми, що використовує клас:

Реалізація програми, яка робить обхід ланцюга Маркова з прикладу
#include < iostream>
#include "Markov.h"
#include < string>
#include < fstream>

using namespace std;

int main()
{
Markov<string> chain;
ofstream outs;
outs.open("out.txt");
ifstream ins;
ins.open("matrix.txt");

int num;
double Prob = 0;
(ins >> num).get(); // кількість вершин
string str;
for (int i = 0; i < num; i++)
{
getline(ins, str);
chain.AddElement(str); // додаємо вершину
}
if (chain.InitAdjacency()) // ініціалізуємо матрицю нулями
{
for (int i = 0; i < chain.size(); i++)
{
for (int j = 0; j < chain.size(); j++)
{
(ins >> Prob).get();
if (!chain.PushAdjacency(i, j, Prob)) // вводимо матрицю
{
cerr << "Adjacency matrix write error" << endl;
}
}
}

outs << chain.At(0) << " "; // виводимо 0-ю вершину
for (int i = 0; i < 20 * chain.size() - 1; i++) // генеруємо 20 ланцюжків
{
string *str = chain.Next();
if (str != NULL) // якщо попередня не кінцева
outs << (*str).c_str() << " "; // виводимо значення вершини
else
{
outs << std::endl; // якщо кінцевий, то починаємо з початку
chain.Current = 0;
outs << chain.At(0) << " ";

}
}

chain.UninitAdjacency(); // зрозуміло
}
else
cerr << "Can not initialize Adjacency matrix" << endl;;

ins.close();
outs.close();
cin.get();
return 0;
}


Приклад виводу, який генерує програма:

Висновок
A B D F Z 
 
A C G T Z 
 
A C G T Z 
 
A B D F Z 
 
A C H T Z 
 
A B D F Z 
 
A C G T Z 
 
A C G T Z 
 
A C G T Z 
 
A B D F Z 
 
A B D F Z 
 
A C G T Z 
 
A B D F Z 
 
A B D F Z 
 
A C H T Z 
 
A C G T Z 
 
A C H T Z 
 
A C H T Z 
 
A B E F Z 
 
A C H T Z 
 
A B E F Z 
 
A C G T Z 
 
A C G T Z 
 
A C H T Z 
 
A B D F Z 
 
A B D F Z 
 
A C H T Z 
 
A B D F Z 
 
A C G T Z 
 
A B D F Z 
 
A B D F Z 
 
A B D F Z 
 
A B D F Z 
 
A C G T Z 
 
A B D F Z 
 
A C H T Z 
 
A C H T Z 
 
A B D F Z 
 
A C G T Z 
 
A B D F Z 
 


Ми бачимо, що алгоритм працює цілком стерпно. В якості значень можемо вказувати що завгодно.

З ілюстрації ланцюга Маркова видно, що A B D F Z найбільш ймовірна послідовність подій. Вона ж найчастіше проявляється. Подія E зустрічається рідше всього

Конфігураційний файл, що використовувався в прикладі:

файл
10
 
A
 
B
 
D
 
E
 
F
 
Z
 
C
 
G
 
H
 
T
 
0 50.0 0 0 0 0 50 0 0 0
 
0 0 80.0 20.0 0 0 0 0 0 0
 
0 0 0 0 100.0 0 0 0 0 0
 
0 0 0 0 100.0 0 0 0 0 0
 
0 0 0 0 0 100.0 0 0 0 0
 
0 0 0 0 0 0 0 0 0 0
 
0 0 0 0 0 0 0 70.0 30.0 0
 
0 0 0 0 0 0 0 0 0 100.0
 
0 0 0 0 0 0 0 0 0 100
 
0 0 0 0 0 100.0 0 0 0 0
 


Висновок

Таким чином ми бачимо, що до ланцюгів Маркова застосовуються алгоритми на графах і виглядають ці алгоритми досить красиво. Якщо хтось знає більш кращу реалізацію, то прошу відписуватися в коментарях.

Повний код та readme на гітхабі: код

Всім дякую за увагу.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.