Сегодня я хотел бы рассказать вам о написании класса, упрощающего работу с цепями Маркова.
Пожалуйста под кат. Базовые знания: Представление графов в виде матрицы смежности, знание основных понятий о графах.
Знание C++ для практической части.
Теория
Цепь Маркова — это последовательность случайных событий с конечным или счетным числом исходов, характеризующаяся тем свойством, что, грубо говоря, при фиксированном настоящем будущее не зависит от прошлого.Проще говоря, цепь Маркова — это взвешенный граф.Назван в честь А.
А.
Маркова (старшего).
В его вершинах находятся события, а вес ребра, соединяющего вершины A и B, — это вероятность того, что за событием A последует событие B. Об использовании цепей Маркова написано довольно много статей, но мы продолжим развивать класс.
Позвольте мне привести вам пример цепи Маркова: 
В дальнейшем мы будем рассматривать эту схему в качестве примера.
Очевидно, что если из вершины А выходит только одно ребро, то его вес будет равен 1.
Обозначения
В вершинах у нас есть события (из A, B, C, D, E.).По ребрам вероятность того, что после i-го события произойдет событие j > i. Для условности и удобства я пронумеровал вершины (№1, №2 и т. д.).
Матрица — это матрица смежности ориентированного взвешенного графа, которую мы используем для представления цепи Маркова.
(подробнее об этом позже).
В данном конкретном случае эту матрицу еще называют матрицей вероятности перехода или просто матрицей перехода.
Матричное представление цепи Маркова
Мы будем представлять цепи Маркова с помощью матрицы, а именно той матрицы смежности, с помощью которой мы представляем графы.Позвольте мне напомнить вам:
Матрица смежности графа G с конечным числом вершин n (нумерациями от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу ребер из i-й вершины графа до j-й вершины.Подробнее о матрицах смежности читайте в курсе дискретной математики.
В нашем случае матрица будет иметь размер 10х10, напишем ее:
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)
{
Теги: #Цепи Маркова #C++ #теория графов #C++ #Алгоритмы
-
Делирия
19 Oct, 24 -
Мега Сити
19 Oct, 24 -
Проблема, О Которой Вы, Вероятно, Не Знали
19 Oct, 24 -
Windows Vista Рулит!
19 Oct, 24 -
Как Сделать Бомбу Из Xml
19 Oct, 24
