โปรแกรม C++ เพื่อค้นหาความน่าจะเป็นของรัฐในช่วงเวลาที่กำหนดในห่วงโซ่ Markov

ในบทความนี้ เราจะพูดถึงโปรแกรมเพื่อค้นหาความน่าจะเป็นที่จะเข้าถึงจากสถานะเริ่มต้นไปยังสถานะสุดท้ายในช่วงเวลาที่กำหนดในห่วงโซ่ Markov

ห่วงโซ่มาร์คอฟเป็นกระบวนการสุ่มที่ประกอบด้วยรัฐต่างๆ และความน่าจะเป็นที่เกี่ยวข้องในการไปจากรัฐหนึ่งไปยังอีกรัฐหนึ่ง ต้องใช้เวลาต่อหน่วยในการย้ายจากสถานะหนึ่งไปอีกสถานะหนึ่ง

ห่วงโซ่ Markov สามารถแสดงด้วยกราฟกำกับ เพื่อแก้ปัญหานี้ เราสามารถสร้างเมทริกซ์จากห่วงโซ่ Markov ที่กำหนดได้ ในเมทริกซ์นั้น องค์ประกอบที่ตำแหน่ง (a,b) จะแสดงความน่าจะเป็นที่จะเปลี่ยนจากสถานะ 'a' เป็นสถานะ 'b'

สิ่งนี้จะทำให้วิธีการแบบเรียกซ้ำสำหรับการแจกแจงความน่าจะเป็นโดยใช้สูตร

P(t) = Matrix * P(t-1)

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
#define float_vec vector<float>
//to multiply two given matrix
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;
}
//to calculate power of matrix
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;
}
//to calculate probability of reaching from initial to final
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 }
   };
   //number of available states
   int N = 6;
   int 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