1. 概要

このチュートリアルでは、バックトラッキングアルゴリズムの背後にある理論的アイデアについて説明します。また、バックトラッキングアプローチを使用して解決策を見つける古典的な問題についても説明します。

2. バックトラッキングの概要

バックトラッキングは、ブルートフォースアプローチを使用して問題のすべての解決策を取得することを目的としたアルゴリズム手法です。 これは、すべてのソリューションのセットを段階的に構築することで構成されます。 問題には制約があるため、それらを満たさないソリューションは削除されます。

再帰呼び出しを使用して、ソリューションを段階的に構築し、時間とともにレベルを上げて、ソリューションセットを見つけます。これらのソリューションを見つけるために、状態空間ツリーという名前の検索ツリーは使用済み。 状態空間ツリーでは、各ブランチは変数であり、各レベルはソリューションを表します。

バックトラッキングアルゴリズムは、深さ優先探索法を使用します。 ソリューションの探索を開始すると、境界関数が適用され、アルゴリズムはこれまでに構築されたソリューションが制約を満たしているかどうかを確認できます。 含まれている場合は、検索を続行します。 そうでない場合、ブランチは削除され、アルゴリズムは前のレベルに戻ります。

3. 例

ここでは、バックトラックプロセスの背後にある理論を説明するために、非常に簡単な例を取り上げています。 3文字を横に並べられないように配置したいと思います。

バックトラックによると、最初に、状態空間ツリーを構築します。 考えられるすべての解決策を見つけて、与えられた制約でそれらをチェックします。 与えられた制約を満たすソリューションのみを保持します。

問題の可能な解決策は次のようになります：、、、、、、。

それにもかかわらず、この問題の有効な解決策は、制約を満たすものであり、最終的な解決策セットのみを保持します。

4. バックトラッキングアルゴリズムを使用する場合

バックトラッキングアルゴリズムは、特定の種類の問題に適用されます。 たとえば、これを使用して決定問題の実行可能な解決策を見つけることができます。最適化問題にも非常に効果的であることがわかりました。

場合によっては、問題のすべての実行可能な解決策のセットを見つけるために、列挙問題にバックトラッキングアルゴリズムが使用されます。

一方、バックトラッキングは、問題を解決するための最適化された手法とは見なされません。 問題に必要な解決策に期限がない場合に、そのアプリケーションを見つけます。

5. バックトラッキングアルゴリズム

5.1. 問題文

バックトラックの典型的な例は、1848年にドイツのチェス愛好家MaxBezzelによって最初に提案された-Queens問題です。 サイズのチェス盤を考えると、問題はチェス盤に女王を配置することです。そのため、2人の女王が互いに攻撃することはありません。

この問題については、チェス盤上の クイーンの位置のすべての配置を見つける必要があることは明らかですが、制約があります。クイーンが別のクイーンを攻撃できないようにする必要があります。

5.2. 擬似コード

バックトラッキング手法を使用して-Queens問題を解決する擬似コードを見てみましょう。

このアルゴリズムは、最初の空の行のインデックスを表す配列とパラメーターから開始します。 チェス盤上の女王の位置は、配列を使用して格納されます。ここで、行のどの正方形に女王が含まれているかを示します。

まず、変数のサイズがのサイズより大きいかどうかを確認します。 この条件が満たされる場合、配列を返します。 が未満の場合、女王の現在の位置をインデックス値で確認します。 チェス盤にクイーンを配置するための非攻撃位置である場合は、インデックスを配列に保存します。 このように、関数を再帰的に呼び出すことにより、チェス盤のすべての位置を探索します。

5.3. ソリューションの例

例としてチェス盤を取り上げると、問題を解決すると10の解決策が得られます。これにより、これらすべての解決策を取得するためにバックトラッキングアルゴリズムを使用することになります。

この問題の場合、見つかった解決策は有効ですが、それでも-Queens問題のバックトラッキングアルゴリズムはに等しい時間計算量を示します。

6. 結論

このチュートリアルでは、バックトラッキング手法の一般的な考え方について説明しました。 また、バックトラッキングを使用するアルゴリズムも紹介しました。

バックトラッキングは、このアルゴリズムの時間計算量が高くても、既存のすべてのソリューションを調査する必要がある場合があるため、さまざまな種類の問題を解決するための有効で重要なツールです。