バックトラッキングとは?基本概念からN-クイーン問題などの応用例まで徹底解説

バックトラッキングとは

バックトラッキング(Backtracking)は、問題を解決するためのアルゴリズム技法の一つです。再帰呼び出しを活用し、解となる候補を一歩ずつ構築しながら探索を進めていきます。探索の過程で、与えられた制約条件を満たさない候補――すなわち最終的な解につながらない選択肢――はその時点で切り捨て、ひとつ前の分岐点に戻って別の道を試します。この「行き詰まったら引き返す」という動作が、バックトラッキングという名前の由来です。

バックトラッキングが適用される主な問題の種類

• 決定問題: 問題に対して実行可能な解が存在するかどうかを判定し、一つの実行可能解を見つけます。

• 最適化問題: 適用可能な解の中から、最良の解を見つけます。

• 列挙問題: 問題に対するすべての実行可能な解の集合を見つけます。

バックトラッキングでは、アルゴリズムは解へ至る経路(シーケンス)を探索します。この経路上には小さなチェックポイント(分岐点)が設けられており、ある地点から先に実行可能な解が見つからない場合、そのチェックポイントまで引き返して別の経路を試すことができます。

例として、下図のような探索の流れを考えてみましょう。

上図では、緑が開始点、青が中間地点、赤が実行可能な解のない地点、濃い緑が最終的な解を表しています。

アルゴリズムは末端まで進んで、その地点が解かどうかを確認します。解であれば結果を返し、そうでなければひとつ手前のチェックポイントに戻り(バックトラック)、次の経路を探索して解を探します。

基本的なアルゴリズム

Step 1 − 現在位置がゴールであれば、成功を返す
Step 2 − そうでなければ、
Step 3 − 現在位置が行き止まり(末端)であれば、失敗を返す
Step 4 − 行き止まりでなければ、探索を続け、上記の手順を繰り返す

N-クイーン問題への適用

ここからは、バックトラッキングを使ってN-クイーン問題を解く方法を見ていきましょう。

N-クイーン問題とは、N×Nのチェス盤の上に、互いに攻撃し合わないようにN個のクイーンを配置するという古典的な問題です。クイーンは縦・横・斜めの直線上にある駒を攻撃できるため、同じ行・列・対角線上に2つのクイーンが存在してはいけません。ここでは、理解しやすいよう規模を小さくした4-クイーン問題を扱います。

解の一例は以下の通りです。

このとき、クイーンが置かれた位置を1で表したバイナリ出力は次のようになります。

{0 , 1 , 0 , 0}
{0 , 0 , 0 , 1}
{1 , 0 , 0 , 0}
{0 , 0 , 1 , 0}

N-クイーン問題を解くには、まず1行目のさまざまな位置にクイーンを置いてみて、他のクイーンと衝突(攻撃関係)していないかを確認します。もし2つのクイーンが互いに攻撃し合う配置になっていた場合は、直前のクイーンの位置へバックトラックして位置を変更し、再度衝突の有無を確認します。この手順を繰り返すことで、無駄な組み合わせを排除しながら、衝突のない正しい配置を効率的に見つけることができます。

N-クイーン問題のアルゴリズム

Step 1 − 配列の最初の位置から開始する
Step 2 − 盤面にクイーンを配置して確認する。以下を繰り返す。
    Step 2.1 − クイーンを配置したら、その位置を解の一部としてマークし、再帰的にこの配置が解に至るかどうかを調べる
    Step 2.2 − 配置しても解に至らない場合はバックトラックし、手順(a)に戻って他の行にクイーンを配置し直す
    Step 2.3 − クイーンの配置が解に至る見込みであれば TRUE を返す
Step 3 − すべてのクイーンが配置できたら TRUE を返す
Step 4 − すべての行を試しても解が見つからなければ FALSE を返す

迷路のネズミ問題(Rat in a Maze)への適用

次に、バックトラッキングを使って迷路のネズミ問題(Rat in a Maze)を解いてみましょう。

この問題では、N×Nの迷路が与えられ、スタート地点である [0][0] から出発し、終点である [n-1][n-1] の位置を目指します。経路上には、解に至らない行き止まりの道がいくつも存在します。

バックトラッキングを用いることで、行き止まりに出会うたびに引き返しながら、一歩ずつ迷路のゴール地点へ向かって進むことができます。

以下の2次元配列は、この問題の様子を示したものです。

破線で示された部分が、実際に移動した経路を表しています。