【C++】行列がマルコフ行列かどうかを判定するプログラムの作り方

r 行 × c 列の行列 M[r][c] が与えられたとき、それがマルコフ行列であるかどうかを判定します。マルコフ行列であれば「It is a Markov matrix（マルコフ行列です）」と出力し、そうでなければ「it's not a Markov matrix（マルコフ行列ではありません）」と出力するプログラムを作成しましょう。

マルコフ行列とは？

マルコフ行列（Markov Matrix）とは、各行の要素の合計がちょうど 1 になる行列のことです。確率遷移行列とも呼ばれ、状態間の遷移確率を扱うマルコフ連鎖などの確率モデルで広く利用されています。

たとえば、次のような行列を見てみましょう。

この行列の各行の合計を計算すると、以下のようになります。

1行目の合計 = 0.2 + 0.3 + 0.5 = 1.0
2行目の合計 = 0.1 + 0.7 + 0.2 = 1.0
3行目の合計 = 0.4 + 0.5 + 0.1 = 1.0

すべての行の合計が 1.0 となっているため、この行列はマルコフ行列だと言えます。

入出力例

入力：m[][] = { {0.2, 0.3, 0.5},
      {0.1, 0.7, 0.2},
      {0.4, 0.5, 0.1}}
出力：It is a Markov matrix（マルコフ行列です）

入力：m[][] = { {0, 0, 1},
      {0, 0.7, 0.3},
      {0.5, 0.5, 0}}
出力：It is a Markov matrix（マルコフ行列です）

考え方（アプローチ）

1. 各行の合計値を格納するための 1 次元配列を用意します。
2. 行列を走査しながら、各行ごとに要素を足し合わせていきます。
3. 最後に配列全体を確認し、すべての要素が 1 になっていれば「マルコフ行列」、1 つでも 1 でない行があれば「マルコフ行列ではない」と判定します。

なお、実際の実装では 1 次元配列を別途用意せず、行ごとに合計を計算してその場で判定する方が効率的です（後述のコードではこの方式を採用しています）。この場合の時間計算量は O(n²)、空間計算量は O(1) となります。

アルゴリズム

開始
ステップ1 → マクロを定義：#define n 3
ステップ2 → マルコフ行列を判定する関数を宣言
　　bool check(double arr[][n])
　　　　ループ For int i = 0、i <n の間 i++
　　　　　　double sum = 0 を宣言
　　　　　　ループ For int j = 0、j < n の間 j++
　　　　　　　　sum = sum + arr[i][j]
　　　　　　　　もし (sum != 1) ならば
　　　　　　　　　　return false
　　　　　　　　ここまで
　　　　　　ここまで
　　　　Return true
ステップ3 → main() 内で
　　double arr[3][3] = { { 0, 0, 1 },
　　　　{ 0.5, 0, 0.5 },
　　　　{ 0.9, 0, 0.1 } } を宣言
　　もし (check(arr)) ならば
　　　　「マルコフ行列です」と出力
　　そうでなければ
　　　　「マルコフ行列ではありません」と出力
終了

C++ による実装

#include <iostream>
using namespace std;
#define n 3
// マルコフ行列かどうかを判定する関数
bool check(double arr[][n]){
    for (int i = 0; i <n; i++){
        double sum = 0;
        for (int j = 0; j < n; j++)
            sum = sum + arr[i][j];
        if (sum != 1)
            return false;
    }
    return true;
}
int main(){
    double arr[3][3] = { { 0, 0, 1 },
        { 0.5, 0, 0.5 },
        { 0.9, 0, 0.1 } };
    if (check(arr))
        cout << "its a markov matrix";
    else
        cout << "its not a markov matrix";
}

実行結果

its a markov matrix

補足：浮動小数点数の比較には注意が必要

上記のコードでは sum != 1 という比較を行っていますが、double 型の演算には丸め誤差が伴います。0.1 のような小数は 2 進数で正確に表現できないため、合計が厳密に 1 にならず、意図しない判定結果になるケースがあります。実務では、微小な許容誤差（イプシロン）を考慮して次のように記述するのが安全です。

#include <cmath>
// ...
if (fabs(sum - 1.0) > 1e-9)
    return false;

このように書くことで、丸め誤差の影響を受けることなく、正確にマルコフ行列かどうかを判定できます。