C++ প্রোগ্রাম: মার্কভ চেইনে প্রদত্ত সময়ে স্টেটের প্রোবাবিলিটি

মার্কভ চেইন (Markov Chain) — স্টেটস এবং ট্রানজিশন প্রোবাবিলিটি থাকা একটি র‍্যান্ডম প্রসেস। প্রতিটি ট্রানজিশন ১ ইউনিট টাইম নেয়।

অ্যালগরিদম

1. ট্রানজিশন ম্যাট্রিক্স M তৈরি করুন (M[i][j] = i থেকে j যাওয়ার প্রোবাবিলিটি)।
2. ম্যাট্রিক্স এক্সপোনেনশিয়েশন দিয়ে M^T বের করুন।
3. M^T[F-1][S-1] = সোর্স S থেকে T টাইমে ডেস্টিনেশন F পাওয়ার প্রোবাবিলিটি।

C++ কোড উদাহরণ

#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

আউটপুট
Probability of reaching: 2 in time 100 after starting from: 4 is 0.271464