Bài toán xác suất trên ma trận

Ở đây chúng ta sẽ xem một bài toán xác suất trên ma trận. Chúng ta có một ma trận hình chữ nhật. Chúng ta có thể di chuyển theo bốn hướng từ ô hiện tại với xác suất như nhau. Bốn hướng này là trái, phải, lên và xuống. Chúng ta phải tính xác suất sau N bước di chuyển từ vị trí M[i, j].

Ở đây chúng ta sẽ làm một điều gì đó liên quan đến DFS. Chúng ta sẽ duyệt đệ quy qua mỗi trong bốn ô có thể từ ô hiện tại. Sau đó chúng ta sẽ tính xác suất với một bước ít hơn. Vì mỗi trong bốn hướng có xác suất bằng nhau, mỗi hướng sẽ đóng góp 0.25 của tổng xác suất. Nếu vượt ra khỏi biên ma trận, ta trả về 0, và trả về 1 khi đã hoàn thành N bước. Hãy xem thuật toán để hiểu ý tưởng.

Thuật toá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

Ví dụ

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

Kết quả

Matrix Probability is 0.664062