এখানে আমরা একটি ম্যাট্রিক্স প্রোবাবিলিটি সমস্যা দেখব। একটি রেক্ট্যাঙ্গুলার ম্যাট্রিক্স আছে। বর্তমান সেল থেকে চার দিকেই সমান প্রোবাবিলিটিতে যাওয়া যায়। চার দিক হলো বাম, ডান, উপর, নিচ। M[i, j] পজিশন থেকে N মুভ করার পর প্রোবাবিলিটি কত তা বের করতে হবে।
এখানে আমরা DFS-এর মতো কিছু করব। বর্তমান রুম থেকে চারটি সম্ভাব্য রুমে রিকার্সিভলি ট্রাভার্স করব। তারপর এক কম মুভের সাথে প্রোবাবিলিটি ক্যালকুলেট করব। যেহেতু চার দিকের প্রোবাবিলিটি সমান, তাই প্রতিটি দিক ০.২৫ প্রোবাবিলিটি দেবে। যদি ম্যাট্রিক্সের বাউন্ডারি পার করা হয়, তবে ০ রিটার্ন করব, এবং N মুভ সম্পন্ন হলে ১ রিটার্ন করব। স্পষ্ট ধারণার জন্য অ্যালগরিদমটি দেখি।
অ্যালগরিদম
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
