見出し画像

📏バックトラッキング(逆引き)のテクニック解説

あたり総研

バックトラック」という言葉は、1950年代にアメリカの数学者D.H.レーマーによって作られた


〔意見・約束などを〕撤回する
〔来た時と〕同じ道を引き返す

９０％以上のプログラミング用語は定義があいまいだ。アパッチヘリから窓、最終的にはおしゃぶり（pacifier）まで登場するこの渡世で、バックトラッキングとは何を提示することばなのか。

バックトラックとは，制約充足問題をはじめとする計算問題のすべて（または一部）の解を求めるための一般的なアルゴリズムで，解の候補を段階的に構築し，その候補が有効な解に完成できないと判断した時点で候補を放棄する（「バックトラック」）ものである

とにかくなにかをやめるんだな、おまえは

バックトラックが適用できる場合は、1回のテストで多くの候補を排除できるため、すべての完全な候補を総当りで列挙するよりもはるかに高速であることが多い。

順番が決まってれば、効率がいい時があるんだな

他の多くのメタヒューリスティックな手法とは異なり、有限の問題に対するすべての解を一定の時間内に見つけることが保証されてる。

バックトラック」という言葉は、1950年代にアメリカの数学者D.H.レーマーによって作られた

バックトラックは、クロスワード、暗算、数独などの制約充足問題を解くための重要なツールとなる

なんか、穴埋め問題的なやつを総当たりでやらなくてすむという

ナップザック問題をはじめとする組み合わせ最適化問題の解析[3]においても，最も便利な手法であることが多い．

試してみてうまくいかなかったならば、別のものを試す

深いところまで一旦降りると、

画像3


時を戻そう（バックトラッキング）

めちゃめちゃ簡単なバックトラッキングの例をみつけた。

ブリリアントさん、ありがとう。

長さNの配列Aには，N! の並び順があるはずです。

画像6


3x2x1で6ね。

def permutation(list, start, end):

   if (start == end):
       print list
   else:
       for i in range(start, end + 1):
           list[start], list[i] = list[i], list[start]  # The swapping
           permutation(list, start + 1, end)
           list[start], list[i] = list[i], list[start]  # Backtracking

permutation([1, 2, 3], 0, 2)  # The first index of a list is zero

これなら読める（泣　いや、ほんとは読めないけど、中身見たら多分分かる。。

と思ったが、こんなに短いが、やってることが意味不明。とりあえず、２箱しかない配列にして、スワップとバックトラッキングの詳細を表示するようにする。

画像7

再帰の仕組みも最小で終わるので、所定の数をスワップしたあともとに戻しているのがわかる。

これがバックトラッキングだー、理由はまだよくわからんが。。。

動きを確認するために、_で内部変数を作って、動きの確認ができるコードを作ってみた。

import copy
_stack=[]
def permutation(list, start, end,count):
   if (start == end):
       print(list)
   else:
       for i in range(start, end + 1):
           _backup=copy.copy(list);
           list[start], list[i] = list[i], list[start]  # The swapping
           _stack.append(_backup[i])
           print("swapped",_backup[start],"->",_backup[i],"then",list,_stack)
           permutation(list, start + 1, end,count)
           _backup=copy.copy(list);
           list[start], list[i] = list[i], list[start]  # Backtracking
           _stack.pop()
           print(" backte",_backup[i],"<-",_backup[start],"then",list,_stack)

permutation(['a', 'b','c'], 0, 2,0)  # The first index of a list is zero

結果はこんな感じで推移する

swapped a -> a then ['a', 'b', 'c'] ['a']
swapped b -> b then ['a', 'b', 'c'] ['a', 'b']
['a', 'b', 'c']
backte b <- b then ['a', 'b', 'c'] ['a']
swapped b -> c then ['a', 'c', 'b'] ['a', 'c']
['a', 'c', 'b']
backte b <- c then ['a', 'b', 'c'] ['a']
backte a <- a then ['a', 'b', 'c'] []
swapped a -> b then ['b', 'a', 'c'] ['b']
swapped a -> a then ['b', 'a', 'c'] ['b', 'a']
['b', 'a', 'c']
backte a <- a then ['b', 'a', 'c'] ['b']
swapped a -> c then ['b', 'c', 'a'] ['b', 'c']
['b', 'c', 'a']
backte a <- c then ['b', 'a', 'c'] ['b']
backte a <- b then ['a', 'b', 'c'] []
swapped a -> c then ['c', 'b', 'a'] ['c']
swapped b -> b then ['c', 'b', 'a'] ['c', 'b']
['c', 'b', 'a']
backte b <- b then ['c', 'b', 'a'] ['c']
swapped b -> a then ['c', 'a', 'b'] ['c', 'a']
['c', 'a', 'b']
backte b <- a then ['c', 'b', 'a'] ['c']
backte a <- c then ['a', 'b', 'c'] []

お分かりいただけただろうか？スワップをバックトラッキングでもどしてるんだが、再帰で戻ったときにやるから慣れてあらめちゃめちゃ処理が追いづらい。いくつか見やすい方法を考えて、スワップごとにスタックに積んで、バックトラッキングでスタックから出すコードを入れて、積んである文字の動きがなんとなくわかるようになった。

さらば、Nクイーン

なんとか分かりやすい例を見つけて、バックトラッキングのなんとなくを理解できるようになった。

非線形パターン（1つのパターン内で同じ変数が複数現れるパターン）に対するパターンマッチをサポートしている。 また、パターンマッチのよるデータの分解方法が複数ある場合でも、パターンマッチのための探索空間を効率よくバックトラッキングする。

https://ja.wikipedia.org/wiki/Egison


この記事が参加している募集

#この街がすき

43,693件

お願い致します