【ITニュース解説】RAM Run

今回のニュース記事は、プログラミングのパズル「Advent of Code」のDay 18で出題された最短経路探索問題に、一人のプログラマーがどのように挑んだかを紹介している。この問題は、迷路のようなグリッドの中からスタート地点からゴール地点まで、最も少ないステップで到達する経路を見つけるというものだ。

筆者は、Dijkstra（ダイクストラ）法やA*（エースター）アルゴリズムといった、最短経路を効率的に見つけるための一般的なアルゴリズムには詳しくないため、自身の得意な「再帰（さいき）」、「初歩的なメモ化（めもか）」、そして「ブルートフォース（力ずくで全ての可能性を試す）」という手法でこの難題に挑戦した。

まず、パズルの入力データを基に「グリッド」と呼ばれるゲーム盤のようなものを作成するところから始める。グリッドは、たくさんのマス目から構成される2次元の配列で、ここではJavaScriptのArrayを使って作られる。makeGrid関数は指定された幅と高さのグリッドを生成し、各マス目を「.」（空のセル）で埋める。次に、入力データから読み込んだX,Y座標に基づいて、特定のマス目を「#」（障害物）に変換するupdateGrid関数が使われる。これにより、迷路の壁が表現されることになる。

さらに、経路探索を簡単にするための工夫として、グリッドの周囲に「#」の境界線を追加する。addGridBorder関数は、既存のグリッドの上下左右に一回り大きな壁を作る。この壁があることで、プログラムがグリッドの端に到達したときに特別な処理をする必要がなくなり、コードがシンプルになるのだ。例えば、右端のマスから右に進もうとしても、そこには壁があるので、それ以上進めないと簡単に判断できるようになる。

次に、いよいよ最短経路を探索するアルゴリズムの中核部分に取り掛かる。筆者は「再帰」というプログラミング手法を用いる。再帰とは、関数が自分自身を呼び出すことで処理を繰り返す方法だ。ここではwalkGridという再帰関数を使って、現在いるマスから次に行けるマスへと進んでいく。

このwalkGrid関数が正しく動作するためには、いくつかの重要な情報を管理する必要がある。一つは「現在いるマス目」の情報、もう一つは「これまでに訪れたマス目」のリストだ。これまでに訪れたマス目を記録しておくのは、同じマス目を何度も循環して無限ループに陥るのを防ぐためと、経路の長さを数えるためだ。ここではJavaScriptのSetオブジェクトが使われる。Setは重複する要素を格納しないコレクションなので、訪問済みの座標（例：[X,Y]）を文字列に変換して追加することで、効率的に管理できる。

再帰関数には必ず「ベースケース（終了条件）」が必要だ。そうでなければ、永遠に自分自身を呼び出し続けてしまう。このアルゴリズムのベースケースは主に二つある。一つは、現在いるマス目がゴールのマス目と同じになった場合。このとき、これまでに訪れたマスの数を数え、それがこれまでの最短ステップ数よりも短ければ、その値を「最短記録」として更新する。もう一つは、現在の経路がすでにこれまでの最短記録よりも長くなってしまった場合だ。この場合、それ以上この経路を進んでも最短にはなり得ないので、そこで探索を打ち切る。

アルゴリズムの初期実装では、いくつかのバグに直面する。 まず、「スタックオーバーフロー」というエラーが発生した。これは、再帰呼び出しが深くなりすぎて、コンピューターが記憶できる関数呼び出しの記録（スタック）の上限を超えてしまったことを意味する。つまり、無限ループに陥っていたのだ。 次に、訪問済みの座標リストが正しく更新されない問題があった。特に、ある経路でデッドエンド（行き止まり）に到達した場合、そのデッドエンドのマスが訪問済みリストに残ってしまい、別の有効な経路を妨げてしまうことが判明する。これを解決するために、デッドエンドになったマスはvisitedセットから削除するvisited.delete()という処理が追加された。これにより、そのマスは別の経路から再度探索される可能性が生まれる。 また、経路のステップ数についても微調整が必要だった。プログラムが数えるvisitedセットの要素数にはスタート地点が含まれるため、実際の「ステップ数」は要素数から1を引いた値になる。 さらに重要な問題として、初期の再帰呼び出しでは、すべての経路が同じvisitedセットを共有していたため、一度通った道が他の探索経路でも「訪問済み」と見なされてしまい、すべての可能性を探索できていなかった。これを解決するために、再帰呼び出しを行う際にnew Set(visited)を使って、visitedセットの「コピー」を渡すように修正された。これにより、各探索経路が独立した訪問履歴を持つことができ、正しくすべての可能性を試せるようになったのだ。 最後に、既に述べた「現在の経路がこれまでの最短記録より長くなったら探索を打ち切る」という条件が追加され、無駄な計算を省くことで処理速度を向上させた。

これらの修正を経て、筆者のアルゴリズムは例題（小さいグリッド）では正しい最短ステップ数「22」を導き出すことに成功した。しかし、いよいよ実際のパズル入力（大規模なグリッド）で試したところ、プログラムは数時間実行し続けても終わらず、正しい答えには到達しなかった。

この結果は、ブルートフォース（力ずく）の手法には限界があることを示している。小規模な問題であれば通用しても、グリッドが大きくなり、経路の選択肢が爆発的に増えると、すべての可能性を試すアプローチでは現実的な時間内に答えを見つけることができなくなる。筆者自身も、このような最短経路探索問題では、より洗練されたDijkstra法やA*アルゴリズムが必要であることを改めて痛感し、この日は一つのゴールドスターも獲得できないかもしれないと認めて、挑戦を終えたのだ。