โปรแกรม C++ หาความน่าจะเป็นของสถานะใน Markov Chain ที่เวลาที่กำหนด

หาความน่าจะเป็นจากสถานะเริ่มต้นไปสถานะสุดท้ายในเวลาที่กำหนดใน Markov Chain

Markov Chain = กระบวนการสุ่มที่มีสถานะต่างๆ และความน่าจะเป็นการเปลี่ยนสถานะ ใช้เวลา 1 หน่วยต่อการเปลี่ยนสถานะ แสดงเป็น Directed Graph สร้างเมทริกซ์จาก Markov Chain โดย element (a,b) = ความน่าจะเป็นจากสถานะ a ไป b

สูตร遞歸: P(t) = Matrix × P(t-1)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;
#define float_vec vector<float>

vector<float_vec> multiply(vector<float_vec> A, vector<float_vec> B, int N) {
    vector<float_vec> C(N, float_vec(N, 0));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < N; ++k)
                C[i][j] += A[i][k] * B[k][j];
    return C;
}

vector<float_vec> matrix_power(vector<float_vec> M, int p, int n) {
    vector<float_vec> A(n, float_vec(n, 0));
    for (int i = 0; i < n; ++i) A[i][i] = 1;
    while (p) {
        if (p % 2) A = multiply(A, M, n);
        M = multiply(M, M, n);
        p /= 2;
    }
    return A;
}

float calc_prob(vector<float_vec> M, int N, int F, int S, int T) {
    vector<float_vec> matrix_t = matrix_power(M, T, N);
    return matrix_t[F - 1][S - 1];
}

int main() {
    vector<float_vec> G{
        {0, 0.08, 0, 0, 0, 0},
        {0.33, 0, 0, 0, 0, 0.62},
        {0, 0.06, 0, 0, 0, 0},
        {0.77, 0, 0.63, 0, 0, 0},
        {0, 0, 0, 0.65, 0, 0.38},
        {0, 0.85, 0.37, 0.35, 1.0, 0}
    };
    int N = 6, S = 4, F = 2, T = 100;
    cout << "Probability of reaching: " << F << " in time " << T << " after starting from: " << S << " is " << calc_prob(G, N, F, S, T);
    return 0;
}

ผลลัพธ์

Probability of reaching: 2 in time 100 after starting from: 4 is 0.271464