এখানে আমরা একটি ম্যাট্রিক্স সম্ভাব্যতা সমস্যা দেখতে পাব। আমাদের একটি আয়তক্ষেত্রাকার ম্যাট্রিক্স আছে। আমরা বর্তমান ঘর থেকে সমান সম্ভাবনার সাথে চারটি দিক সরাতে পারি। এই চারটি দিক বাম, ডান, উপরে এবং নীচে। 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