バックトラッキングとは

問題に対して解決できる組み合わせが複数存在する場合があります。
その解決できる組み合わせを見つける為に、選択肢の中から様々な組み合わせを試さなければいけません。
バックトラッキングは、選択肢の中から全ての可能な構成を調べるための体系的な方法です。

まず、選択肢の中から1つ選択する場合、以下のような特性があります。

1. 選択肢の中から何を選べばいいか知るための情報がない。
2. それぞれの選択が、次の選択につながる。
3. 1つ以上のいくつかの選択が問題を解決するかもしれない。

具体的に例をあげると、

例1. 迷路

迷路でスタートからゴールまでの道を見つける場合。
各交差点では、以下の3つの選択肢から選択する必要がある。

直進
左折
右折

このとき、以下のような特性があります。

1. この3つの選択肢から正しい選択をするために十分な情報がない。
2. それぞれの選択が、次の選択につながる。
3. 1つ以上のいくつかの選択が問題を解決するかもしれない。

例2. 地図

地図の色を以下の4色に分ける場合。

隣接する国は異なる色でなければならないとする。

このとき、以下のような特性があります。

1. この4つの選択肢から正しい選択をするために十分な情報がない。
2. それぞれの選択が、次の選択につながる。
3. 1つ以上のいくつかの選択が問題を解決するかもしれない。

これらの問題を解決する唯一の方法は、全ての可能性をチェックすることです。

全ての可能性をチェックするために、体系的な方法であるバックトラッキングを使います。

実装

解は、各要素a(i)が有限全順序集合Sから選ばれるベクトル(a(1), a(2), a(3), ...a(n))であると仮定します。(つまり、Sは可能な選択肢の集合)

部分解Aを作成し、それをA =(a(1), a(2), ... , a(k))のように拡張しながらテストする。
部分解が解である場合は、出力する。そうでない場合、S(k)からa(k)を削除して、別の可能な選択を試す。
可能な選択が尽きた場合、k-1してSの最初の選択を消して、次の選択を試す。

擬似コード


def BACKTRACK(S):
  # S: 可能な選択を保持したリスト
  S(1) = S
  k = 1
  while(k > 0):
    while S(k) != empty:  #　進める
      a(k) = an element in S(k)
      S(k) = S(k) - a(k)
      if(a(1), a(2), ..., a(k)) is a solution:
        print(a(1), a(2), ..., a(k))
      k = k + 1
      S(k) = S
    k = k - 1  # バックトラック

再帰を使用した実装


def BACKTRACK(A, k, S):
  # A = a(1), ..., a(k): 部分解
  if A is a solution:
    print A = a(1), ..., a(k)
  else:
    k = k + 1
    S(k) = S
    while S(k) != empty:
      a(k) = an element in S(k)
      S(k) = S(k) - a(k)
      A = A + a(k)
      BACKTRACK(A, k, S)

例

3-bitの2進数で1が2個以上含まれている数を見つける。
この問題を解決する唯一の方法は、全ての可能性（000、001、010、....、111）をチェックすることになります。

可能性は8つあり、これらは問題の探索空間と呼ばれ、以下のようなツリー構造に編成することができます。

             _ _ _  
        /              \
     0 _ _           1 _ _
   /       \       /       \
  00_     01_     10_     11_
 /   \   /   \   /   \   /   \
000 001 010 011 100 101 110 111

8クイーン問題

バックトラック法の適用例として、8クイーン問題があります。
Python3でnクイーン問題を解く