एक मैट्रिक्स संभाव्यता प्रश्न?

यहां हम एक मैट्रिक्स प्रायिकता समस्या देखेंगे। हमारे पास एक आयताकार मैट्रिक्स है। हम वर्तमान सेल से चार दिशाओं को समान संभावना के साथ स्थानांतरित कर सकते हैं। ये चारों दिशाएँ बाएँ, दाएँ, ऊपर और नीचे हैं। N के स्थान M[i, j] से चले जाने के बाद हमें प्रायिकता की गणना करनी होगी।

यहां हम डीएफएस से संबंधित कुछ करेंगे। हम वर्तमान कमरे से चार संभावित कमरों में से प्रत्येक में पुनरावर्ती रूप से पार करेंगे। फिर हम एक कम चाल के साथ प्रायिकता की गणना करेंगे। चूँकि चारों दिशाओं में से प्रत्येक की प्रायिकता समान है, तो प्रत्येक दिशा कुल प्रायिकता का 0.25 योगदान देगी। यदि हम मैट्रिक्स की सीमा को पार करते हैं, तो हम 0 वापस आ जाएंगे, और जब एन चाल पूरी हो जाएगी तो 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