猫をお願いします。
初期知識：
隣接行列の形式でのグラフの表示、グラフに関する基本概念の知識。 実用的な部分のC ++の知識。
理論
マルコフ連鎖-有限または可算数の結果を伴うランダムなイベントのシーケンス。固定された現在では固定された現在では、未来は過去から独立しているという特性によって特徴付けられます。 A.A.マルコフ（シニア）にちなんで名付けられました。
簡単に言えば、マルコフ連鎖は重み付きグラフです。 頂点にはイベントがあり、頂点AとBを接続するエッジの重みは、イベントBがイベントAに続く確率です。
マルコフ連鎖の使用に関してかなり多くの記事が書かれていますが、私たちはクラスの開発を続けていきます。
マルコフ連鎖の例を挙げます。
将来的には、このスキームを例として考えます。
明らかに、頂点Aから出るエッジが1つしかない場合、その重みは1になります。
指定
上部にはイベントがあります（A、B、C、D、Eから）。 エッジには、i番目のイベントの後にイベントj> iが発生する確率があります。 便宜上、便宜上、ピークに番号を付けました（1番、2番など）。
行列は、方向付けられた重み付きグラフの隣接行列であり、これによりマルコフ連鎖を表します。 （これについては後で詳しく説明します）。 この特定の場合、この行列は遷移確率行列または単に遷移行列とも呼ばれます。
マルコフ連鎖の行列表現
マトリックスの助けを借りてマルコフ連鎖を表現します。つまり、グラフを表現する隣接行列です。
思い出させてください：
有限数の頂点n（1からnまでの番号）を持つグラフGの隣接行列は、aijの値がグラフのi番目の頂点からj番目の頂点までのエッジの数に等しいサイズnの正方行列Aです。
隣接行列の詳細-離散数学の過程で。
この場合、マトリックスのサイズは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）頂点が有限でない場合、マトリックスの行kの確率分布に基づいて0 ... n-1から数mを生成します。ここで、nは頂点の数、mは次のイベントの数（！）です。 そうでなければ、私たちは去ります
3）現在位置kの数は、生成された頂点の数に等しい
4）ステップ2へ
注：確率分布がゼロの場合、頂点は有限です（行列の6行目を参照）。
かなりエレガントなアルゴリズムですよね？
実装
この記事では、説明した回避策の実装コードを個別に作成します。 マルコフ連鎖の初期化と充填はほとんど関心がありません（最後の完全なコードを参照してください）。
バイパスアルゴリズムの実装
template <class Element> Element *Markov<Element>::Next(int StartElement = -1) { if (Markov<Element>::Initiated) // { 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
ジェネレーターの結果として、それぞれ0.5の確率で1または6を返します。 つまり、さらに移動を続ける列番号（チェーン内の頂点の数に相当）を返します。
クラスを使用するサンプルプログラム：
例からマルコフ連鎖のバイパスを行うプログラムの実装
#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; }
プログラムが生成する出力例：
おわりに
ABDFZ
ACGTZ
ACGTZ
ABDFZ
ACHTZ
ABDFZ
ACGTZ
ACGTZ
ACGTZ
ABDFZ
ABDFZ
ACGTZ
ABDFZ
ABDFZ
ACHTZ
ACGTZ
ACHTZ
ACHTZ
ABEFZ
ACHTZ
ABEFZ
ACGTZ
ACGTZ
ACHTZ
ABDFZ
ABDFZ
ACHTZ
ABDFZ
ACGTZ
ABDFZ
ABDFZ
ABDFZ
ABDFZ
ACGTZ
ABDFZ
ACHTZ
ACHTZ
ABDFZ
ACGTZ
ABDFZ
アルゴリズムが非常にうまく機能することがわかります。 値として何でも指定できます。
マルコフ連鎖の図から、ABDFZが最も可能性の高い一連のイベントであることがわかります。 最も頻繁に現れます。 イベント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
おわりに
したがって、グラフ上のアルゴリズムはマルコフ連鎖に適用可能であり、これらのアルゴリズムはかなり見栄えが良いことがわかります。 誰かがより良い実装を知っているなら、コメントの購読を止めてください。
GitHubの完全なコードとReadme： コード
ご清聴ありがとうございました。