アルゴリズム講座/実践編/バックトラック
ホームページへ戻る 目次へ戻る
パズル問題解法のアルゴリズム講座

実践編

バックトラック

 バックトラック(バックトラッキング)は思考アルゴリズムの王様と言っても過言ではありません。私の知る限り思考プログラムの約90%はバックトラックを使っていると思います。

1.バックトラックの考え

    人が行う「試行錯誤という行為」を忠実に実行するように考え出されたアルゴリズムで利用範囲は
   広範です。もちろん不得意分野もあります。
    複数の未知のものを上手く組み合わせて、ある条件を満たす全体を得るのに、その未知のものを
   ひとつずつ許される範囲内で「もし、こう仮定して」さらにこの状態から「次に、こう仮定して」
   というように仮定から仮定へと強引に突き進みます。
    そんなことをすれば大抵は途中で行き詰ってしまいます。その時は1歩戻って(バックトラッキング)
   仮定を立て直して
、また、突き進みます。総ての仮定に失敗したら、そこからまた1歩戻って新たな仮定
   を立て直して同様に進行すれば、やがては解に到達することになります。

2.バックトラック例題「2枚のカードの間には?」

   ここでは例題として「2枚のカードの間には?」(Cマガ電脳クラブ91年4月号より)に挑戦してみます。

    1から7の数字を書いたカードが2枚ずつ計14枚ある。
  そしてこれを1列に並べ,2枚の1の間にはカードが1枚,
  2枚の2の間にはカードが2枚はさまれていて,同様に,
  3の間には3枚,4の間には4枚,5の間には5枚,6の間には
  6枚,7の間には7枚のカードがはさまれるように14枚の
  カードを並べて下さい。

 

3.例題をバックトラックで解く。

 
   次の2つを基本方針として考えることにする。
  1.[1]のカードからペアで順番に配置していく。
  2.仮定は左側への可能な配置から順次試していく。

  この方針で強引に仮定から仮定へと突き進むと、右上図のようになる。
  ここで行き詰まったので、5を取り除き、1歩戻って4の配置を変更する。

  こんなことの繰り返しをプログラムに実行させようとすると次のようになります。


 
C言語ソースリスト

Java言語ソースリスト

Javaアプレットの実行

動きが判る様にウエイトをかけています。

   このプログラムは総ての配置法を求める場合のものです。
    尚、1のカードから順に配置するようにしていますが、本当は
   7のカードから順に配置した方が無駄な探索を少なく出来ます。

   backtrack()を最初に呼び出すのは、backtrack(1)です。

    int LETSU[];  /* カードを置いていく列テーブル */

    /* No.pのカードをいろいろ置いてみる(バックトラック) */
    void backtrack(int p) {
        int  i;   /* 左カードの位置 */
        int  j;   /* 右カードの位置 */

        if (p > 7) {   /* 総てのカードが置かれている */
            (配置を表示する等の処理:省略);
        } else {
            for (i=0, j=p+1; j < 14; i++, j++) {
                if (LETSU[i]==0 && LETSU[j]==0) { /* カードを置けるなら */
                    LETSU[i] = LETSU[j] = p;      /* カードを置く(仮定) */
                    backtrack(p+1);               /* 再帰で次のNo.カードへ */
                    LETSU[i] = LETSU[j] = 0;      /* 状態を元に戻す */
                }
            }
        }
    }


目次へ戻る   前の頁へ戻る  次の頁へ進む