前回の記事の続きです。 astrostory.hatenablog.com この記事ではマルコフ連鎖をグラフとして見ていきます。なお、今回も例は前回の記事の天気の例を利用します。 簡単に再度説明しますと 晴れ、曇り、雨という3つの状態があり、そのいずれかの状態から別の…

マルコフ連鎖というグラフ理論を用いた確率の考え方があり、これはプログラムの実装も可能で便利だと思うのでこの記事で詳しく説明できればと思います。 いつものように数学的な厳密性は少し欠けていても分かりやすい記事を目指します。 マルコフ連鎖とは マ…

Gale-shapleyアルゴリズムはマッチングに関するアルゴリズムです。 合コンでの男女のマッチング、研修医と病院のマッチングなどのグループAとグループB、そして全ての参加者がそのマッチング対象のグループの参加者に対して順位がある場合、Gale-shapleyアル…

今回の記事ではグラフ理論のSpanning Tree(全域木)を扱います。 まずそもそもグラフとは？の人はこちらの記事から入られることをお勧めします。 astrostory.hatenablog.com また今回は分かりやすくするために無向グラフを使います。 全域木 全域木はかなり平…