2つの経路探索でグリッドから最大ポイントを収集するアルゴリズム

各セルにポイントが割り当てられた行列があります。このグリッドから2つの経路探索(トラバーサル)を用いて、収集できるポイントの最大値を求める方法を解説します。

問題の条件

• 1回目の経路はグリッドの左上のセルからスタートし、左下の角を目指して進みます。2回目の経路は右上の角からスタートし、右下の角を目指して進みます。
• あるセルから移動できるのは、真下・左下・右下のいずれかのセルのみです。
• 片方の経路ですでにポイントを獲得したセルからは、もう片方の経路ではポイントを獲得できません(同じセルを2重に数えることはできません)。

入力と出力

入力:
ポイントが割り当てられたグリッド
3 6  8  2
5 2  4  3
1 1 20 10
1 1 20 10
1 1 20 10

出力:
2つの経路で収集した最大ポイントは 73
1回目の経路で獲得: 3 + 2 + 20 + 1 + 1 = 27
2回目の経路で獲得: 2 + 4 + 10 + 20 + 10 = 46

解法のアプローチ:動的計画法とメモ化

この問題は、2つの経路の位置(行 x、1回目の経路の列 y1、2回目の経路の列 y2)を1つの状態として扱う動的計画法で効率的に解くことができます。同じ状態 (x, y1, y2) は探索の過程で何度も現れるため、3次元のメモ化テーブル mTable[x][y1][y2] に計算結果をキャッシュすることで、無駄な再計算を省き、計算量を大幅に削減できます。

アルゴリズム

findMaxVal(mTable, x, y1, y2)

入力: メモ化テーブルとしての3次元配列、x の値、y1、y2

出力: 最大値

Begin
   if x, y1, y2 が有効な範囲外ならば
      return -∞
   if 両方の経路が完了したら
      if y1 = y2 ならば
         return grid[x, y1]
      else
         return grid[x, y1] + grid[x, y2]
   if 両方の経路が最終行に達した(が完了していない)ならば
      return -∞
   if 部分問題がすでに解かれていれば
      return mTable[x, y1, y2]
   res := -∞ で初期化

   if y1 = y2 ならば
      temp := grid[x, y1]
   else
      temp := grid[x, y1] + grid[x, y2]

   // 9通りの移動の組み合わせをすべて試し、最大値を求める
   res := res と (temp + findMaxVal(mTable, x+1, y1, y2-1)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1, y2+1)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1, y2)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1-1, y2)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1-1, y2-1)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1-1, y2+1)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1+1, y2)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1+1, y2-1)) の最大値
   res := res と (temp + findMaxVal(mTable, x+1, y1+1, y2+1)) の最大値

   mTable[x, y1, y2] = res を保存して返す
End

C++による実装例

#include<iostream>
#define ROW 5
#define COL 4
using namespace std;

int grid[ROW][COL] = {
    {3, 6, 8, 2},
    {5, 2, 4, 3},
    {1, 1, 20, 10},
    {1, 1, 20, 10},
    {1, 1, 20, 10},
};

bool isValidInput(int x, int y1, int y2) {
    return (x >= 0 && x < ROW && y1 >=0 && y1 < COL && y2 >=0 && y2 < COL);
}

int max(int a, int b) {
    return (a>b)?a:b;
}

int findMaxVal(int mTable[ROW][COL][COL], int x, int y1, int y2) {
    if (!isValidInput(x, y1, y2))     // 無効なセルの場合は負の無限大を返す
        return INT_MIN;

    if (x == ROW-1 && y1 == 0 && y2 == COL-1)     // 両方の経路が完了した場合
        return (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2];

    if (x == ROW-1)       // 両方の経路が最終行に達したが完了していない場合
        return INT_MIN;

    if (mTable[x][y1][y2] != -1)     // 部分問題がすでに解かれている場合
        return mTable[x][y1][y2];

    int answer = INT_MIN;      // 初期値は負の無限大

    int temp = (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2];     // 現在のセルで獲得するポイント

    // すべての移動パターンを試し、その最大値を求める

    answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2-1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2+1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2));

    answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2-1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2+1));

    answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2-1));
    answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2+1));

    return (mTable[x][y1][y2] = answer); // 答えをmTableに保存して返す
}

int findMaxCollection() {
    // メモ化テーブルを作成し、すべての値を -1 で初期化
    int mTable[ROW][COL][COL];

    for(int i = 0; i<ROW; i++)
        for(int j = 0; j<COL; j++)
            for(int k = 0; k<COL; k++)
                mTable[i][j][k] = -1;

    return findMaxVal(mTable, 0, 0, COL-1);
}

int main() {
    cout << "Maximum collection is " << findMaxCollection();
    return 0;
}

実行結果

Maximum collection is 73

まとめ

2つの経路を独立に探索すると膨大な組み合わせが必要になりますが、両者の位置を1つの状態としてまとめて扱うことで、状態数は O(ROW × COL × COL) に抑えられます。各状態からの遷移は9通りなので、全体の計算量は O(ROW × COL²) となり、メモ化と組み合わせることで非常に効率的に最大ポイントを求められます。