還暦AI

還暦になってからAIを勉強する過程を記録するブログ

バックトラック

ついでにバックトラックについても調べてみた。私は自分の理解で「バックトラック」という言葉を使っている。「3×3魔法陣を書くプログラムを作る(step 3の動作例)」のところで、下の図を使って動作を説明した。

「①で数字1を選択したら②になった。さらに②で数字2を選択したら③になった。しかし③で失敗したので②に戻り、今度は数字3を選択した。」という中の「③で失敗したので②に戻り」というところがバックトラックだ。つまり、失敗した時に前の状態に戻り、そこから別の選択をすることがバックトラックだと認識している。この認識でよかっただろうか? ウィキペディアの「バックトラッキング」の項を調べてみたら、以下のように書かれていた。

バックトラッキング (backtracking)は、制約充足問題の解を探索する戦略の一種で、力まかせ探索を改良したもの。「バックトラック」という用語は、アメリカの数学者デリック・ヘンリー・リーマー (Derrick Henry Lehmer)が1950年代に作った造語である。


ウィキペディアの「バックトラッキング」の項 より

「制約充足問題」というのがよく分からないが、今回の魔法陣作成もこの中に入るのだろう。「力まかせ探索」についてはウィキペディアでは

力まかせ探索(ちからまかせたんさく、英: Brute-force search)またはしらみつぶし探索(英: Exhaustive search)は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。


ウィキペディアの「力まかせ探索」の項 より

とある。力まかせ探索とは「全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法」と考えればよいのだろう。3×3魔法陣を例にとると、1から9までの数字を9つのマスに配置する全ての組合せ、すなわち9×8×7×6×5×4×3×2×1=362,880通りの配置、を全て作って、そのひとつひとつが、縦・横・斜めの数字の合計が15かどうかチェックするやり方が、力まかせ探索というのだろう。英語ではBrute-force searchというのだそうだ。覚えておこう。「単純だが非常に汎用的」というのは、きっとそうだろう。


バックトラッキングの説明に戻る。

バックトラッキングアルゴリズムは、単に正しい解を得るまで可能な組み合わせを試していくだけであり、一種の深さ優先探索である。探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試す。探索木を全部サーチしたとき、探索は失敗して終了する。


ウィキペディアの「バックトラッキング」の項 より

「探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。」という考えがキーだろう。私が上で魔法陣の例で説明したことであっていそうだ。


深さ優先探索についてはウィキペディアでは

深さ優先探索(ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう)は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。


ウィキペディアの「深さ優先探索」の項 より

あるいは

形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。


同上

とあって、バックトラッキングとの違いがよく分からない。


バックトラックバックトラッキングという言葉の使い分けは、バックトラックとは状態を戻ることであり、バックトラッキングはバックトラックを用いた探索方法、ということのようだ。でも、それならバックトラッキング深さ優先探索と同じ意味に思えてくる。