還暦AIスマートフォン用の表示で見る還暦AI還暦になってからAIを勉強する過程を記録するブログ2019-12-29バックトラックついでにバックトラックについても調べてみた。私は自分の理解で「バックトラック」という言葉を使っている。3の動作例)」のところで、下の図を使って動作を説明した。「1で数字1を選択したら2になった。2で数字2を選択したら3になった。3で失敗したので2に戻り、今度は数字3を選択した。」という中の「3で失敗したので2に戻り」というところがバックトラックだ。失敗した時に前の状態に戻り、そこから別の選択をすることがバックトラックだと認識している。ウィキペディアの「バックトラッキング」の項を調べてみたら、以下のように書かれていた。(backtracking)は、制約充足問題の解を探索する戦略の一種で、力まかせ探索を改良したもの。Lehmer)が1950年代に作った造語である。「制約充足問題」というのがよく分からないが、今回の魔法陣作成もこの中に入るのだろう。search)は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。力まかせ探索とは「全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法」と考えればよいのだろう。3×3魔法陣を例にとると、1から9までの数字を9つのマスに配置する全ての組合せ、すなわち9×8×7×6×5×4×3×2×1=362,880通りの配置、を全て作って、そのひとつひとつが、縦・横・斜めの数字の合計が15かどうかチェックするやり方が、力まかせ探索というのだろう。searchというのだそうだ。「単純だが非常に汎用的」というのは、きっとそうだろう。バックトラッキングの説明に戻る。バックトラッキングのアルゴリズムは、単に正しい解を得るまで可能な組み合わせを試していくだけであり、一種の深さ優先探索である。探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。その組み合わせを試しても解でなかった場合、さらに探索木を戻り、新たな組み合わせを試す。探索木を全部サーチしたとき、探索は失敗して終了する。「探索の際、ある組み合わせが解でなかったなら、探索木をたどって戻り別の組み合わせを試す。」という考えがキーだろう。私が上で魔法陣の例で説明したことであっていそうだ。DFS、バックトラック法ともいう)は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。同上とあって、バックトラッキングとの違いがよく分からない。バックトラックとバックトラッキングという言葉の使い分けは、バックトラックとは状態を戻ることであり、バックトラッキングはバックトラックを用いた探索方法、ということのようだ。それならバックトラッキングは深さ優先探索と同じ意味に思えてくる。月別アーカイブはてなブログをはじめよう!CUSCUSさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。