はじめに
以前、数独のウェブアプリを作った際にアルゴリズムの「バックトラッキング」というものをchatGPTから提案されました
一旦その場は理解しきれなかったので、今回で概念だけでも理解できればと思い記事にしようと思います
バックトラッキングとは
組み合わせ探索問題や最適化問題を解くための汎用的なアルゴリズムです。簡単に言うと、「試行錯誤をしながら、間違えたら引き返して別の道を試す」というアプローチを取ります。
ということらしいです
具体的なイメージ
正直なところ説明の文章を読んでもなんじゃやそれ状態なので、もう少し深掘りをしてみます
簡単な例で行くと、迷路や2分木で表現すると分かりやすそうです
迷路であればスタートからゴールに向かうまでに幾つか分岐点がありますが、各分岐点で選択肢をひとつ残らず系統的に試していくというイメージです
2分技も親ノードから一番深い子ノードに辿り着くにはどのノードを辿っていけば良いのかを、間違えては分岐点まで戻り、間違えた選択肢とは別のものを選ぶということを繰り返します
段々と理解できてきた気がします
こんな2分技があったとすると
回答の探し方としては以下が考えられます
まずはAからBに進んでそのあとEに進みますが、正解ではないので次の答えの候補を探さないといけません
そこで次はAからBに行ってFまで進みますが、これも正解ではありませんね
じゃあ次はAからCに行ってG、、、、
明らかに重複している処理があるかと思います
最下層のノードを見る際にAまで戻る必要があるかという点ですね
例えばEやFが正解かを調べる場合にはBまで見ていたらそこまでは正解であると仮定して、
B、C、DからBを選んでという選択の回数が減りますね
これがバックトラッキングということになります
今回はまだ2分木の例が少ないので、あんまり関係ないのではと思われるかもしれませんが階層が深くなるごとに計算量が増えていくので、やはり余計な選択・処理はしない方が良いですよね(ゲームでもチェックポイントは欲しいですよね、初めからやり直すのは面倒ということです)
数独に当てはめて考えてみ
ことの発端は、数独の問題を作ってみたところから始まりますので、同じように考えてみます
9 x 9の盤面があり、そこに数字の1を全て入れるところから考えてみます
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| A | |||||||||
| B | |||||||||
| C | |||||||||
| D | |||||||||
| E | |||||||||
| F | |||||||||
| G | |||||||||
| H | |||||||||
| I |
数独は同じ数字が縦横で重ならないというルールがあるので、それに違反した場合は手順戻ってやり直すという感じですね
判定として同じ行に同じ数字はあるか、同じ列に同じ数字があるかを確認して存在していれば間違っている、存在していなければ正解になります
A1に1を入れた場合、A2以降には数字が入らないので処理がスキップできます
次にB行についてですがここで、初めて同じ列に同じ数字が発生するのでB1に1は置くことができないという判定になります
その後の処理としてはもしもバックトラッキングを使っていなければ再びA1から考え直すことになりますがバックトラッキングを活用すると間違ったところ、つまりB列の2からやり直すという処理に変わりるので、かなり計算量を削減できていることがわかるかと思います
なんでもfor文で回しちゃいけないですね、本当に
実際のコードについては以下記事でも紹介しているので興味があれば覗いてみてください
↓
https://qiita.com/ryo0819/items/c70e7950ece35e1ca60c
おわりに
ということで久方ぶりのアルゴリズムについて考えてみるという記事でした
深さ優先探索や幅優先探索など遠い昔にやったことがありますが、いざ活用しようと思うと適切に活用できていないので、日頃かそのような思考ができるように努力したいです