โจทย์ความน่าจะเป็นบนเมทริกซ์

ที่นี่เราจะดูโจทย์ความน่าจะเป็นบนเมทริกซ์ เรามีเมทริกซ์สี่เหลี่ยมผืนผ้า สามารถเคลื่อนที่ 4 ทิศทางจากเซลล์ปัจจุบันได้ด้วยความน่าจะเป็นเท่ากัน (ซ้าย, ขวา, บน, ล่าง) ต้องคำนวณความน่าจะเป็นหลังจากเคลื่อนที่ N ครั้งจากตำแหน่ง M[i, j]

เราจะใช้แนวคิด DFS เรียกซ้ำไปใน 4 ทิศทางที่เป็นไปได้จากเซลล์ปัจจุบัน คำนวณความน่าจะเป็นด้วยการเหลือการเคลื่อนที่ลดลง 1 แต่ละทิศทางมีส่วนร่วม 0.25 ของความน่าจะเป็นรวม หากออกนอกขอบเขตเมทริกซ์ คืนค่า 0 และคืนค่า 1 เมื่อครบ 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

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

bool isSafe(int x, int y, int m, int n) {
    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))
        return 0.0;
    if (N == 0)
        return 1.0;
    double probability = 0.0;
    probability += matProb(m, n, x - 1, y, N - 1) * 0.25; // ซ้าย
    probability += matProb(m, n, x, y + 1, N - 1) * 0.25; // บน
    probability += matProb(m, n, x + 1, y, N - 1) * 0.25; // ขวา
    probability += matProb(m, n, x, y - 1, N - 1) * 0.25; // ล่าง
    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