यहां हम एक मैट्रिक्स प्रायिकता समस्या देखेंगे। हमारे पास एक आयताकार मैट्रिक्स है। हम वर्तमान सेल से चार दिशाओं को समान संभावना के साथ स्थानांतरित कर सकते हैं। ये चारों दिशाएँ बाएँ, दाएँ, ऊपर और नीचे हैं। 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
