「アルゴリズムとデータ構造」では、バックトラッキングアルゴリズムの美しさを紹介します。

[[345679]]

序文
今回は、バックトラッキング アルゴリズムについて確認します。この問題解決の考え方を習得すると、今後の学習や、多くの検索および試行の問題に取り組む際に役立ちます。

バックトラッキング アルゴリズムについては、ある程度理解しています。バックトラッキング アルゴリズムは DFS に基づいていますが、違いは、検索プロセス中に、終了条件に到達した後、状態が復元され、前のレイヤーにバックトラッキングされて、再度検索されることです。したがって、バックトラッキング アルゴリズムと DFS の違いは、状態のリセットがあるかどうかであると理解できます。

バックトラッキング アルゴリズムが何であるか分からない場合、または少しは知っているが具体的な実装方法が分からない場合は、この記事を読むとよいでしょう。

次に、以下の点を中心にバックトラッキングアルゴリズムを紹介します👇

• ソース
• 基本的な考え方
• アルゴリズムフレームワーク
• 典型的な例

バックトラッキングアルゴリズムの起源
まず、バックトラッキング アルゴリズムとは何か、そしてそれがどこから来たのかを理解する必要があります。

Wikipediaの定義によると👇

バックトラッキング アルゴリズムは、ヒューリスティック メソッドとも呼ばれ、問題の解決策を体系的に検索する方法です。

バックトラッキング アルゴリズムを使用して問題を解決するための一般的な手順:

1. 与えられた問題に対して、その問題に対する少なくとも 1 つの (最適な) 解決策を含むソリューション空間を定義します。

2. バックトラッキングを使用してソリューション空間全体を簡単に検索できるように、検索しやすいソリューション空間構造を決定します。

3. 深さ優先方式でソリューション空間を検索し、検索プロセス中に無効な検索を回避するためにプルーニング関数を使用します。

もっと簡単に説明すると👇

バックトラッキング法は、道のさまざまな分岐点を選択し、一度に 1 つの分岐点から目的地を見つけようとすることで目的地を見つける方法と理解できます。間違った道を進んでしまった場合は、目的地が見つかるまで、前の分岐点にある別の道に戻り続けます。

基本的な考え方
まず、このバックトラッキング アルゴリズムの考え方を明確にする必要があります。その考え方に基づいて、疑似コードを作成できます。疑似コードを作成したら、実際の問題に応じて対応するソリューションを作成できます。

このタイプのバックトラッキング問題は、決定木を解決するためのトラバーサル プロセスとして考えることができ、これにより、後続の説明が容易になります。

基本的な考え方:

• 意思決定ツリーの 1 つのパスに沿って歩き始め、前進できる場合は前進し、前進できない場合は戻って別のパスを試します。

たとえば、8 人のクイーン問題を例に挙げて説明しましょう。

• 最初のステップはスムーズに進み、つまり、最初の行に最初のクイーンを配置します。
• 2 番目のステップでは、2 行目にクイーンを配置する必要があります。 クイーンをトラバースして、要件を満たす位置に配置する必要があります。
• 3 番目のステップ、つまり 3 行目では、トラバースして一致する位置を見つける必要があります。要件を満たすものがない場合は、「2 番目のステップを元に戻す」必要があります。次に、2 番目のクイーンの位置を変更し、3 番目のクイーンの位置が満たされるまで 2 番目のクイーンを再配置する必要があります。
• 2 番目のクイーンの位置を変更しても、3 番目のクイーンの位置が収まらない場合は、「最初のステップを元に戻し」、最初のクイーンの位置を再配置してから、後続の操作を順番に完了する必要があります。

これを別の例で見てみましょう。バックトラッキングは迷路探索でも非常に一般的です。簡単に言うと、このパスがブロックされている場合は、「最後の操作を元に戻し」、前の交差点に戻り、次のパスに進む必要があります。

バックトラッキングは究極的には「徹底的な方法」であることがわかったようですが、プルーニングを行わずに単に徹底的な方法を実行すると、時間の計算量が非常に大きくなります。では、どのようにプルーニングするのでしょうか?

バックトラッキング最適化手法をプルーニング、またはプルーニング関数と呼びます。この機能により、いくつかの状態を減算し、到達不可能な状態 (「最終状態」) をプルーニングできます。ここでの最終状態は、回答状態と見なすことができます。このようにして、一部の空間ツリー ノードの生成が削減されます。具体的なプルーニング方法については、問題解決の経験に基づいてさらに練習することができますので、ここでは詳細には触れません。

アルゴリズムフレームワーク
実際、ある程度の質問を練習すると、この種のバックトラッキング思考には一定のルーチンがあることが分かるので、擬似コードを以下に示します👇

以下は私自身の理解です。次の手順で理解していただければ分かりやすいと思います👇

この種の質問については、次の 3 つのステップで考えることができます。

1. 「パス」: 選択した内容を記録します。
2. 「選択リスト」: 一般的に、選択可能な操作を格納するために配列が使用されます。
3. 終了条件: 一般的に言えば、再帰の終了点、つまり検索の終了点です。

結果 = [] 
 
関数バックトラック(パス、選択リスト) {
    if( '終了条件が満たされている' ) {
        // 実際の質問に基づいて回答を更新します
        結果.push(パス)
戻る 
    }それ以外{
 ( i = 0 とします; i < selectlist.length; i++) {
            // 選択リストに対応する選択を行う
             
            選択する
             
            backtrack(パス、オプションリスト) 
             
            // これはバックトラッキングアルゴリズムなので、分岐で選択を行った後
            // 前に実行した操作をロールバックする必要があります
             
            選択を元に戻す
        }
    }
 }

同様の問題を解いたことがある人なら誰でも、コア処理は for ループ内の再帰操作であることを知っています。各再帰の前に、「選択を行います」。このソリューションが完了したら、「選択を元に戻す」必要があります。そうすることで、決定木の同じレベルの他の選択に影響を与えなくなります。

たとえば、迷路のような問題では、答えを探し続けて試行錯誤を続ける必要があります。このプロセスはバックトラッキング アルゴリズムです。次のグリッドに移動するたびに、まずグリッドを「マーク」して、そこを通過したことを示す必要があります。その後、検索を続けます...

この解決策が合理的でない場合は、以前にマークしたグリッドをクリアする必要がありますか?よく考えてみると、これは非常に合理的です。現在の解決策が機能しない場合は、「このステップを元に戻す」必要があります。

上記の基礎知識についてある程度理解できたので、この基礎知​​識を使って問題を解決することができます。

バックトレースの書き方
いくつかの質問をしてバックトラッキングアルゴリズムを予備的に理解した後、次の手順を参照して意図的に練習できると思います👇

• まず再帰ツリーを描画し、状態変数 (バックトラッキング関数のパラメータとして理解できます) を見つけます。
• 一般的には、質問の特定の条件に基づいて再帰終了を決定します。
• 選択リストを識別します (通常は関数パラメータに関連します)。
• 剪定。場合によっては、剪定が適切なこともあります。
• 選択して再帰的に呼び出し、次のレベルに進みます。
• 選択を元に戻します。

このバックトラッキング アルゴリズムの要約は非常に優れており、参考として使用できると思います。

2 例
次に、3つの質問を例にして、先ほど説明したアルゴリズムフレームワークに基づいて問題を解決する方法を確認します👇

すべての大文字と小文字⭐
リンク: 大文字と小文字すべて

文字列 S が与えられた場合、文字列 S 内の各文字の大文字と小文字を変更することで新しい文字列を取得できます。すべての可能な文字列のセットを返します。

例：

入力: S = "a1b2" 出力: ["a1b2", "a1B2", "A1b2", "A1B2"]

入力: S = "3z4" 出力: ["3z4", "3Z4"]

入力: S = "12345" 出力: ["12345"]

ヒント：

Sの長さは12を超えてはならない。 S は数字と文字のみで構成されます。

出典: LeetCode リンク: https://leetcode-cn.com/problems/letter-case-permutation 著作権は LeetCode Network に帰属します。商用目的での複製については、正式な許可を得るためにお問い合わせください。非商用目的での複製については、出典を明記してください。

さて、この質問については、絵を描いて例を挙げることができます。私はインターネットから写真を使います。

アルファベット順

数字の場合はそのままスキップします。文字の場合は大文字と小文字の2つの状態しかないので、次のアイデアがあります👇

• 数字に遭遇した場合、新しい分岐は発生せず、直接逆方向に検索します。このように、数字の検索は 1 回だけで済みます。
• 1 つの文字の場合、小文字を 1 回、大文字を 1 回と、合計 2 回検索する必要があります。
• インデックスを維持できます。数字に遭遇した場合、インデックスを 1 増やして再帰を続けます。文字に遭遇した場合、再帰を 2 回行う必要があります。文字が小文字であると仮定すると、1 回再帰 (インデックス + 1) し、バックトラック時に文字を大文字に変換して、再度再帰します。
• 再帰の終了: つまり、文字列全体が検索されるまで、先ほど維持したインデックスをこの時点での条件判断として使用できます。

この考え方に従えば、問題を解決する完全なコードを書くことができる。

コード👇

バックトラッキングアルゴリズムコード1

コードはこちらをクリック☑️

サブセット 🐍⭐⭐
リンク: サブセット

重複要素のない整数配列 nums が与えられた場合、配列のすべての可能なサブセット (べき乗集合) を返します。

注意: ソリューション セットには重複したサブセットを含めることはできません。

例：

入力: nums = [1,2,3] 出力: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

出典: LeetCode リンク: https://leetcode-cn.com/problems/subsets 著作権は LeetCode Network に帰属します。商用目的での複製については、正式な許可を得るためにお問い合わせください。非商用目的での複製については、出典を明記してください。

このタイプの質問をするとき、理解できない場合は、まず図を描くことができます。上記の質問から、ツリーのような構造を描き、決定木をどのようにトラバースするかを見て、剪定できるかどうかを確認します。インターネット上の図を参照してください👇

部分集合の再帰木

実際、この絵を描くことができれば、成功の半分は達成したことになります。この絵から、この木をもう一度横断できそうです。

まずは自分の考えを整理しなくてはいけません👇

• この質問は、ツリーのすべてのノードを見つけることに関するものである必要があります。
• このツリーでは、枝をトラバースして枝の 1 つを選択し、下方向に操作を続けることができます。この枝を選択しない場合は、別の枝を選択するという状況になります。したがって、次の数字を列挙するたびに、選択するか選択しないかの 2 つの選択肢があります。
• インデックスポインタを使用して「ノード」の状態、つまり現在再帰的に検査されている数値nums[index]を記録することを検討できます。
• 再帰を終了するための条件: index === nums.length。これは、すべての数値が検査され、現在のサブセットがソリューションに追加され、現在の再帰ブランチが終了することを意味します。
• 分岐が終了するたびに、つまり再帰が終了するたびに、現在の選択をキャンセル (リストから削除) し、選択前の状態に戻って別の選択を行う必要があります。つまり、現在の番号を選択せず​​、下方向に再帰し、サブセットの生成を続けます。

上記の疑似コードによれば、基本的にこの問題は解決できます👇

バックトラッキングアルゴリズム問題解決-2

コードはこちらをクリック☑️

答えるべき質問は無限にあります。これらの質問を終えた後、バックトラッキング アルゴリズムのルールを見つけ、より深く理解できるようになることを願っています。次に、いくつかの質問セットを用意しました。お役に立てば幸いです。

上級者向け質問のまとめ
以下は、インターネットで見つけたバックトラッキング アルゴリズムに関する優れた質問集です。まだ探している方は、こちらをご覧ください。