1. 序章

このチュートリアルでは、バックトラッキングと深さ優先探索の違いについて説明します。 また、バックトラッキング手法を使用したアルゴリズムの例についても説明します。

2. 深さ優先探索

深さ優先探索（DFS）は、グラフをトラバースするために使用されるアルゴリズムです。 ルートノードから始まり、各ブランチに沿って可能な限り深く移動します。

以下のツリーは、深さ優先探索を適用するときにノードが訪問される順序を示しています。

深さ優先探索を使用して、1つのソリューションのみでパズルを解いたり、連結成分を見つけたりすることができます。 これは、グラフ内のサイクルを見つけるためのデフォルトのアルゴリズムでもあります。 さらに、スペース効率が高いため、幅優先探索よりも一般的なグラフ検索の方が便利です。

3. バックトラック

Backtracking は、検索空間で可能なすべてのソリューションを反復処理するために使用されるアルゴリズムです。 したがって、制約の問題を解決するために一般的に使用されます。 この意味で、バックトラックは検索スペースを制限し、計算時間を節約します。

基本ケースから部分解を構築するプロセスは、ツリーの深さ検索トラバーサルを実行することに対応します。

3.1. 例

与えられた配列の要素からすべてのサブセットを生成する簡単なアルゴリズムを書いてみましょう。 入力要素ごとに、それを候補リストに追加し、 Subscriptions（）関数を再帰的に呼び出します。 このステップの後、候補リストからこの要素を削除してバックトラックします。 最後に、 Subscriptions（）関数を再度呼び出します。 最終的な結果は、両方の再帰呼び出しの合計です。

上記のアルゴリズムの再帰実行ツリーは次のようになります。

最終的な解決策は、実行ツリーの一番下にあります。 これは8つの要素のセットです。

サブセットの順序は、サブセットを構築するために、左側のツリーブランチに続いて深さ優先探索を使用したことを示しています。

3.2. バックトラッキングのアプリケーション

バックトラッキングは、クロスワード、数独、チェス、三目並べ、その他のパズルを解くために広く使用されています。 また、特定のセットから要素のすべての組み合わせを生成する場合にも役立ちます。 さらに、これはIcon、Planner、Prologなどのプログラミング言語の基礎です。

4. 比較

興味深いことに、バックトラッキングアルゴリズムが繰り返される解空間は、通常、グラフの形式を持っていることがわかります。 そのため、両方のアルゴリズムの実装は非常に似ています。

5. 結論

この記事では、バックトラッキングとDFSの類似点と相違点について説明しました。 また、バックトラッキングを使用して簡単なアルゴリズムを作成しました。

最後に、バックトラッキングはDFSを使用してソリューション空間をトラバースするため、どちらも再帰的アルゴリズムとして表すことができることを学びました。