Ein Matrixwahrscheinlichkeitsproblem?

Hier sehen wir ein Matrixwahrscheinlichkeitsproblem. Wir haben eine rechteckige Matrix. Wir können uns von der aktuellen Zelle aus mit gleicher Wahrscheinlichkeit in vier Richtungen bewegen. Die vier Richtungen sind links, rechts, oben und unten. Wir wollen die Wahrscheinlichkeit nach N Bewegungen ausgehend von der Position M[i,j] berechnen.

Hier werden wir einige Dinge im Zusammenhang mit DFS tun. Wir werden die vier möglichen Räume ausgehend vom aktuellen Raum rekursiv durchqueren. Dann berechnen wir die Wahrscheinlichkeit, einen Schritt weniger zu machen. Da die vier Richtungen die gleiche Wahrscheinlichkeit haben, trägt jede Richtung 0,25 zur Gesamtwahrscheinlichkeit bei. Wir geben 0 zurück, wenn eine Matrixgrenze überschritten wird, und 1, wenn N Züge abgeschlossen sind. Schauen wir uns den Algorithmus an, um auf diese Idee zu kommen.

Algorithmus

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

Beispiel

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

Ausgabe

Matrix Probability is 0.664062

Das obige ist der detaillierte Inhalt vonEin Matrixwahrscheinlichkeitsproblem?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!