একটি ম্যাট্রিক্স সম্ভাব্যতা প্রশ্ন?

এখানে আমরা একটি ম্যাট্রিক্স সম্ভাব্যতা সমস্যা দেখতে পাব। আমাদের একটি আয়তক্ষেত্রাকার ম্যাট্রিক্স আছে। আমরা বর্তমান ঘর থেকে সমান সম্ভাবনার সাথে চারটি দিক সরাতে পারি। এই চারটি দিক বাম, ডান, উপরে এবং নীচে। N অবস্থান M[i, j] থেকে সরে যাওয়ার পর আমাদের সম্ভাব্যতা গণনা করতে হবে।

এখানে আমরা ডিএফএস সম্পর্কিত কিছু করব। বর্তমান রুম থেকে সম্ভাব্য চারটি কক্ষের প্রতিটিতে আমরা পুনরাবৃত্তিমূলকভাবে অতিক্রম করব। তারপরে আমরা একটি কম চাল দিয়ে সম্ভাব্যতা গণনা করব। যেহেতু চারটি দিকের প্রতিটির সমান সম্ভাবনা রয়েছে, তাই প্রতিটি দিক মোট সম্ভাব্যতার 0.25 অবদান রাখবে। যদি আমরা ম্যাট্রিক্স সীমানা অতিক্রম করি, আমরা 0 ফেরত দেব, এবং N সরানো সম্পূর্ণ হলে 1 ফেরত দেওয়া হবে। আসুন ধারণা পেতে অ্যালগরিদম দেখি।

অ্যালগরিদম

matProb(m, n, x, y, N)

Begin
   if x,y is not in matrix boundary m, n, then return 0
   if N is 0 , then return 1
   prob := 0
   prob := prob + matProb(m, n, x-1, y, N-1) * 0.25
   prob := prob + matProb(m, n, x+1, y, N-1) * 0.25
   prob := prob + matProb(m, n, x, y+1, N-1) * 0.25
   prob := prob + matProb(m, n, x, y-1, N-1) * 0.25
   return prob
End

উদাহরণ

#include<iostream>
using namespace std;
bool isSafe(int x, int y, int m, int n) { //function to check whether (x,y)
   is in matrix or not
   if(x >= 0 && x < m && y >= 0 && y < n){
      return true;
   }
   return false;
}
double matProb(int m, int n, int x, int y, int N) {
   if (!isSafe(x, y, m, n)) //if coundary is crossed
      return 0.0;
   if (N == 0) //when N is 0, or N is completed, return 1
      return 1.0;
   double probability = 0.0;
   probability += matProb(m, n, x - 1, y, N - 1) * 0.25; //move left
   probability += matProb(m, n, x, y + 1, N - 1) * 0.25; //move up
   probability += matProb(m, n, x + 1, y, N - 1) * 0.25; //move right
   probability += matProb(m, n, x, y - 1, N - 1) * 0.25; //move down
   return probability;
}
int main() {
   int m = 7, n = 8;
   int x = 1, y = 1;
   int N = 4;
   cout << "Matrix Probability is " << matProb(m, n, x, y, N);
}

আউটপুট

Matrix Probability is 0.664062