Un problème de probabilité matricielle ?

Ici, nous verrons un problème de probabilité matricielle. Nous avons une matrice rectangulaire. Nous pouvons nous déplacer dans quatre directions à partir de la cellule actuelle avec une probabilité égale. Les quatre directions sont gauche, droite, haut et bas. Nous voulons calculer la probabilité après N mouvements à partir de la position M[i,j].

Ici, nous allons faire certaines choses liées à DFS. Nous allons parcourir récursivement les quatre salles possibles en partant de la salle actuelle. Ensuite, nous calculons la probabilité de faire un pas de moins. Puisque les quatre directions ont des probabilités égales, chaque direction contribuera à hauteur de 0,25 à la probabilité totale. Nous renverrons 0 si une frontière matricielle est franchie et 1 lorsque N mouvements sont effectués. Regardons l'algorithme pour avoir cette idée.

Algorithme

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

Exemple

#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);
}

Sortie

Matrix Probability is 0.664062

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!