バックトラッキングアルゴリズムの理論的基礎を一緒に復習しましょう。覚えていますか?

[[423516]]

バックトラッキングアルゴリズムは、実は非常にわかりにくく、理解するのが困難です。バックトラッキングアルゴリズムを学ぶには、私の B ステーションビデオを見ることをお勧めします。このビデオを見ると、バックトラッキングアルゴリズムに関する疑問がすべて解消されると思います。

バックトラッキングとは何か

バックトラッキングは、検索方法の 1 つであるバックトラッキング検索とも呼ばれます。

バイナリツリーシリーズでは、バックトラッキングについて何度も説明しました。たとえば、バイナリツリーでは再帰が使用されていると考えていましたが、実際にはバックトラッキングも含まれていました。

バックトラックは再帰の副産物であり、再帰がある限りバックトラックは発生します。

したがって、以下の説明では、バックトラック関数、つまり再帰関数とは関数のことを指します。

バックトラッキングの効率

バックトラッキング法のパフォーマンスはどうでしょうか? ここで明確にしておきましょう。バックトラッキング法は難しくて理解しにくいですが、効率的なアルゴリズムではありません。

バックトラッキングの本質は、網羅的な列挙、つまりすべての可能性を列挙し、必要な答えを選択することです。バックトラッキングをより効率的にしたい場合は、いくつかのプルーニング操作を追加できますが、網羅的な列挙というバックトラッキングの本質は変わりません。

では、効率的でないのになぜバックトラッキングを使用するのでしょうか?

選択の余地がないので、いくつかの問題を力ずくで探し出し、せいぜいそれらを刈り込むだけでも十分ですが、これ以上に効率的な解決策はありません。

この時点で、誰もが興味を持っているはずです。これらはどのような質問なのでしょうか。あまりにもすごいので、力ずくで検索するしかありません。

バックトラックで解決した問題

バックトラッキングは一般に次の問題を解決できます。

組み合わせ問題: 特定の規則に従って N 個の数値から k 個の数値の集合を見つける
切断問題: 特定の規則に従って弦を切断する方法はいくつかあります
サブセット問題: N 個の数値の集合のうち、要件を満たすサブセットはいくつありますか?
配置問題: N 個の数字を特定の規則に従って配置します。配置方法は何通りありますか?
チェス盤の問題: N クイーン、数独の解き方など

これらをご覧になれば、すべての問題が単純ではないことがお分かりいただけると思います。

さらに、組み合わせと順列を区別できない生徒もいるかもしれません。

組み合わせでは要素の順序は強調されませんが、配置では要素の順序は強調されます。

たとえば、{1, 2} と {2, 1} は順序が重視されていないため、組み合わせると 1 つのセットになります。ただし、並べると、{1, 2} と {2, 1} は 2 つのセットになります。

組み合わせは無秩序であり、配置は順序があるということを覚えておけば、それで十分です。

バックトラッキングを理解する方法

バックトラッキングによって解決される問題は、ツリー構造に抽象化できます。そうです、バックトラッキングによって解決されるすべての問題は、ツリー構造に抽象化できるのです。

バックトラッキング法は、セット内のサブセットを再帰的に検索する問題を解決するため、セットのサイズがツリーの幅を構成し、再帰の深さがツリーの深さを構成します。

再帰には終了条件が必要なので、高さが制限されたツリー (N 項ツリー) にする必要があります。

初心者はこの部分をあまり理解できないかもしれません。後ほどバックトラッキングアルゴリズムで解決するすべての問題で、この点を強調し、図を描いて対応する例を示します。今は印象を持っていただければ十分です。

バックトラッキングテンプレート

以下は、Carl がまとめたバックトラッキングアルゴリズムのテンプレートです。

二分木の再帰について説明した際に、再帰三部作について説明しました。ここでは、バックトラッキング三部作について説明します。

バックトラッキング関数テンプレートの戻り値とパラメータ

バックトラッキングアルゴリズムでは、関数に backtracking という名前を付けるのが私の習慣ですが、好きな名前を付けることができます。

バックトラッキングアルゴリズムの関数の戻り値は通常 void です。

パラメータを見てみましょう。バックトラッキングアルゴリズムに必要なパラメータは、バイナリツリー再帰を使用する場合ほど一度に簡単に決定できないため、通常は最初にロジックを記述し、必要に応じてパラメータを入力します。

しかし、後ほどバックトラッキングの質問の説明をするときに、誰もが理解しやすいように、最初にパラメータを決定するお手伝いをします。

バックトラッキング関数の疑似コードは次のとおりです。

 void バックトラック(パラメータ)

バックトラック関数の終了条件

二分木の再帰を説明すると、木構造であるため、木構造を走査するための終了条件が存在する必要があることがわかります。

したがって、バックトラックにも終了条件があります。

終了条件に達すると、ツリーで確認できます。一般的に、リーフノードが見つかると、条件を満たす答えが見つかります。この答えが保存され、このレベルの再帰が終了します。

したがって、バックトラック関数の終了条件の疑似コードは次のようになります。

 if (終了条件) {
    結果を保存します。
戻る;
 }

バックトラック検索のトラバーサルプロセス

上で述べたように、バックトラック法は一般的にセット内の再帰検索です。セットのサイズがツリーの幅を構成し、再帰の深さがツリーの深さを構成します。

図に示すように:

バックトラッキングアルゴリズムの理論的基礎

図では、セットのサイズを意図的に子供の数と同じにしていることに注意してください。

バックトラッキング関数のトラバーサルプロセスの疑似コードは次のとおりです。

 for (select: 現在のレイヤーセット内の要素 (ツリー内のノードの子の数はセットのサイズです)) {
    処理ノード。
    backtracking(パス, 選択リスト); // 再帰
    バックトラック、処理結果の取り消し
}

for ループはコレクション間隔をトラバースします。for ループはノードが持つ子の数と同じ回数だけ実行されることがわかります。

バックトラックはここで自分自身を呼び出して再帰を実現します。

図からわかるように、for ループは水平方向のトラバーサルとして理解でき、バックトラック (再帰) は垂直方向のトラバーサルであり、ツリーのトラバーサルを完了します。一般的に言えば、リーフノードの検索は、見つけられる結果の 1 つです。

プロセスを分析した後、バックトラッキングアルゴリズムテンプレートフレームワークは次のようになります。

 void バックトラッキング(パラメータ) {
    if (終了条件) {
        結果を保存します。
戻る;
    } 
 
 for (select: 現在のレイヤーセット内の要素 (ツリー内のノードの子の数はセットのサイズです)) {
        処理ノード。
        backtracking(パス, 選択リスト); // 再帰
        バックトラック、処理結果の取り消し
    }
 }