行列内確率問題：N回移動後にマトリクス内に留まる確率をDFSで計算する方法

問題の概要

今回は行列（マトリクス）に関する確率問題を取り上げます。長方形の行列が与えられ、現在のセルからは上下左右の4方向へ等しい確率で移動できるものとします。このとき、位置 M[i, j] から N 回移動した後に、行列の内側に留まっている確率を求めるのが目的です。

解法のアプローチ：DFSを活用

この問題は、深さ優先探索（DFS）の考え方を使って解くことができます。具体的には、現在のセルから移動可能な4方向それぞれに対して再帰的に探索を行い、残りの移動回数を1ずつ減らしながら確率を計算していきます。

4つの方向の移動確率はすべて等しいため、各方向は全体の確率に対して 0.25 ずつ寄与します。再帰の過程で行列の境界を越えた場合は 0 を返し、N 回の移動が完了した時点では 1 を返します。これらを合計することで、求める確率が得られます。

アルゴリズム

matProb(m, n, x, y, N)

Begin
    if (x, y) が行列 m×n の境界外であれば 0 を返す
    if N が 0 であれば 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;

// (x, y) が行列内にあるかどうかを判定する関数
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) // N回の移動が完了した場合
        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

結果の解説

この例では、7×8 の行列の位置 (1, 1) から 4 回移動した場合を考えています。実行結果の 0.664062 は、4 回の移動を終えた時点で約 66.4% の確率で行列の内側に留まることを意味します。開始位置が端に近いほど境界の外に出やすいため、確率は低くなる傾向があります。

計算量

各移動ごとに4方向へ分岐するため、時間計算量は O(4^N) となります。また、再帰の深さは最大 N であるため、空間計算量（再帰スタック）は O(N) です。N が大きくなると計算量が急増するため、動的計画法（メモ化）を組み合わせることで効率化することも可能です。