インタビュー必須：バックトラッキングアルゴリズムの詳細な説明

序文

みなさんこんにちは。私はカタツムリを採っている小さな男の子です。

LeetCode を練習していると、バックトラッキング アルゴリズム タイプの問題によく遭遇します。バックトラッキング アルゴリズムは 5 つの基本アルゴリズムの 1 つであり、大企業では一般的にこのアルゴリズムについて質問します。今日は、バックトラッキングアルゴリズムのルーチンを学びましょう。記事に不正確な点があれば、指摘してください。ありがとうございます〜

• バックトラッキングアルゴリズムとは何ですか?
• アルゴリズムの問​​題はバックトラッキングアルゴリズムにつながる
• バックトラッキングアルゴリズムフレームワークルーチン
• Leetcode ケース分析

1. バックトラッキングアルゴリズムとは何ですか?

バックトラッキング アルゴリズム。すべての可能な候補ソリューションを探索してすべてのソリューションを見つけるアルゴリズム。

試行錯誤の考え方を採用し、問題を段階的に解決しようとします。問題を段階的に解決するプロセスで、既存の段階的な回答が試行によって有効かつ正しい解決策を提供できないことが判明した場合、前のステップまたはそれ以前のステップの計算をキャンセルし、他の可能な段階的な解決策を通じて問題の答えを再度見つけようとします。バックトラッキング法は通常、最も単純な再帰法を使用して実装されます。上記の手順を繰り返すと、次の 2 つの状況が発生する可能性があります。

• 可能性のある正しい答えを見つけます。
• あらゆる可能な段階的なアプローチを試した後、問題には答えがないことを宣言します。

人生で似たような例を挙げると、例えば羊飼いの少年の羊が道の分かれ道で迷子になります。少年は羊を探すために道のさまざまな分かれ道に沿って歩き、次から次へと分かれ道で羊を見つけようとします。羊が見つからない場合は、羊が見つかるまで、道の分岐点で別の道を探しながら戻り続けます。

次の図は、羊を見つけるための意思決定ロードマップです。

羊飼いの少年は A の方向を見てから C の方向に歩きました。羊が見つからなかったので、道の分岐点に戻り、D の方向に歩き続けました... 羊が見つかるまで。これがバックトラッキングです。

2. アルゴリズムの問​​題はバックトラッキングアルゴリズムにつながる

重複する数字のない配列 nums が与えられた場合、すべての可能な順列を返します。回答は任意の順序で返すことができます。

例1:

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

例2:

入力: nums = [ 0 , 1 ]
出力: [ [ 0 , 1 ] , [ 1 , 0 ] ]

2.1 実装のアイデア

この質問を読んだ後、最初に思い浮かぶのはすべての順列を列挙することですが、パターンなしでそれらを列挙することはできませんよね?たとえば、3 つの数字 [1,2,3] を並べ替える場合、最初の数字を 1 として並べ替えると、2 番目の数字は 2 または 3 のみになります。2 番目の数字が 2 の場合、3 番目の数字は 3 のみになります...

羊を探す羊飼いのルートマップを参考にして、全体の配置のツリー図を描くと、次のようになります。

実際、ルート ノードからツリーをトラバースし、パスに沿って番号を記録し、リーフ ノードに移動すると、順列を取得できます。すべてのリーフ ノードをたどると、完全な配置が得られます。

この木をもっと明確に理解するにはどうすればいいでしょうか?

理解を容易にするために、nums の数字 k を k 個の選択肢と見なすことができます。たとえば、[1,2,3] の場合、各数字には 1、2、3 の 3 つの選択肢があります。

選択するたびに、空間ツリーが展開されます。

選択が完了したら、選択したパスが重複している場合は、それを切り詰めます。

上の図のツリーは、すべての要素をトラバースし、空間ツリーを拡張してから、剪定を行うものとして見ることができます。下記の通り

さて、ツリーの成り立ちがわかったので、ツリーをトラバースして完全な順列を見つける方法を見てみましょう。ツリーの枝をたどるたびに、決断を下すようなものです。実行されたパスと選択肢をツリー ノードの 2 つの属性として利用できるようになります。

ルートノードにいる場合、利用可能な選択肢は1、2、3で、以下に示すように、歩いたパスは空です。

リーフノードに到達すると、辿ってきたパス配列の長さは要素群の数と等しくなります。このとき、辿ってきたパスは条件を満たす解となります。

2.2 コードの実装

コードはどのように記述しますか? 以前ツリートラバーサルを学習したとき、通常は再帰を使用しましたが、この質問でも再帰を使用します。

• 再帰エントリとは何ですか? オプションのパスと、実行されたパスだけです。
• 再帰関数の本体はどうでしょうか? 現在の配列の要素を列挙し、プルーニングをスキップするために if ステートメントを必要とする for ループです。
• 再帰終了はどうでしょうか? つまり、リーフ ノードに到達することです。リーフ ノードとは、構築されたパスの配列の長さが nums の長さと等しいときです。

実装コードは次のとおりです。

クラスソリューション{
 //完全な配置、つまりすべてのパスセット
 リスト<リスト< 整数>> allPath =新しい LinkedList <> ( ) ;

 パブリック リスト<リスト< 整数>> permute ( int [ ] nums ) {
 //現在のパス、エントリ パス、パスは空です
 リスト< 整数>パス=新しい LinkedList <> ( ) ;
 //再帰関数のエントリ、オプションは nums 配列
 backTrace (数値、パス) ;
 allPath を返します。
 }

 パブリック void backTrace ( int [ ] nums , List < Integer > path ) {
 //歩いたパスの配列の長さは nums の長さに等しく、リーフノードに到達したことを示しているため、完全な順列セットに追加されます。
 if ( nums .length == path .size ( ) ) {
 allPath .add (新しい LinkedList (パス) ) ;
 戻る;
 }

 ( int i = 0 ; i < nums .length ; i ++ ) {
 //実行されたパスを整理してチェックする
 if (パス.contains (数値[ i ] ) ) {
 続く;
 }
 //選択して現在のパスに追加します
 パス.add ( nums [ i ] ) ;
 //再帰、次のレベルの決定に入る
 backTrace (数値、パス) ;
 //選択を解除する
 パス.remove (パス.size ( ) - 1 ) ;
 }
 }
 }

なぜバックトラックが必要なのでしょうか? あるいは、なぜバックトラック アルゴリズムを使用するのでしょうか?

1 つの順列を見つけるだけでなく、条件を満たすすべての順列を見つける必要があるからです。

再帰呼び出しが終了すると、現在の再帰分岐は終了し、他の分岐に移動して検索を続ける必要があります。

そのため、現在の選択を解除し、選択前の状態に戻ってから次のオプションを選択して次の分岐に入る必要があります。

3. バックトラッキングアルゴリズムフレームワークルーチン

徹底的にパターンを見つけ、バックトラッキングの決定木を要約する

バックトラッキングアルゴリズムフレームワークコードを適用する

3.1. 徹底的にパターンを見つけ、バックトラッキング決定木を要約する

バックトラック型の質問の場合も、網羅的な列挙が基本となります。通常、徹底的な列挙を通じてパターンを見つけ、その後バックトラッキングの決定ツリーを描きます。たとえば、上記の完全な順列の例。

決定木のノードには通常、実行されるパスと実行可能な選択肢という 2 つの属性があります。決定バックトラッキングツリーを要約するときには、この点に注意する必要があります。

3.2. バックトラッキングアルゴリズムフレームワークの適用

バックトラッキング問題を解決することは、実際には決定木のトラバーサル プロセスを解決することです。検討すべき質問は 3 つあります。

• 選んだ道: あなたが選び、選んだ道
• オプションリスト: 現在選択できる選択肢
• 終了条件: 一般的に、決定木のリーフ ノードに到達すると、他の条件付き選択を行うことができなくなります。

バックトラッキング アルゴリズムの疑似コード フレームワークは次のとおりです。

 //すべてのパスコレクション
リスト<> allPath = [ ]
 void backTrace (オプションのリスト、既に実行されたパス) :
 if (終了条件が満たされた場合) {
 allPath .add (すでに通過したパス) ;
 戻る;
 }
 for (選択: オプションのリスト) {
 選択する
 backTrace (現在のオプション リスト、パスはすでに実行されています) ;
 選択を元に戻す
}

4. Leetcode ケース分析の質問:

重複要素のない整数配列候補とターゲット整数 target が与えられた場合、数値の合計がターゲット数値 target と等しくなる候補のさまざまな組み合わせをすべて見つけ、リストの形式で返します。これらの組み合わせは任意の順序で返すことができます。

候補内の同じ番号は、制限なく繰り返し選択できます。少なくとも 1 つの数字に異なる数の選択された数字がある場合、2 つの組み合わせは異なります。

例1:

入力: 候補= [ 2 , 3 , 6 , 7 ] 、ターゲット= 7
出力: [ [ 2 , 2 , 3 ] , [ 7 ] ]
説明する：
 2と3 は候補セットを形成できます。2 + 2 + 3 = 7 。注2:複数回使用できます。
 7も候補です、 7 = 7 。
組み合わせはこの2つだけです。

例2:

入力:候補= [ 2 , 3 , 5 ] 、ターゲット= 8
出力: [ [ 2 , 2 , 2 , 2 ] , [ 2 , 3 , 3 ] , [ 3 , 5 ] ]

4.1 アイデア

まず、パターンを徹底的に探してみましょう。例 1 のデータ、候補 = [2,3,6,7]、ターゲット = 7 を取ります。

 7 = 2 + 2 + 3
 7 = 7

例 2 のデータをもう一度取り上げてみましょう。

 8 = 2 + 2 + 2 + 2
 8 = 2 + 3 + 3
 8 = 3 + 5

実際、パターンは非常に明確です。候補配列の要素をターゲットから 1 つずつ減算するだけです。0 に減算できれば、それが解決策です。

次に、ツリーを描画します。ターゲットはツリーのルート ノードと考えることができ、ブランチは次のように候補配列の要素と子ノードの差を表します。

次に、バックトラッキング アルゴリズム フレームワークを適用します。 歩んできたパス、オプション リスト、終了条件をどのように表現するのでしょうか。次の図を参照してください。

オレンジ色のノード 4 に移動すると、リスト内のオプションはマイナス 2 またはマイナス 3 になります。これは、マイナス 6 が負の数であるためです。オプション リストであるかどうかをどのように判断しますか? 現在のターゲットの値から選択するブランチを引いた値が 0 より大きい限り、オプション リストとして使用できます。

選択されるパスは -3 ブランチです。

終了条件はどうでしょうか? 負の数または 0 ノードに到達すると、終了する時間であり、それ以上の決定は行えません。

4.2 コードの実装

最後に、トレースバック アルゴリズム フレームワークの疑似コードを次のように使用します。

クラスソリューション{

 リスト<リスト< 整数>> allPath =新しい LinkedList <> ( ) ;

 パブリックリスト<リスト< 整数>> combinationSum ( int [ ]候補、 intターゲット) {
 リスト< 整数>パス=新しい LinkedList <> ( ) ;
 backTrace (候補、ターゲット、パス、 0 ) ;
 allPath を返します。
 }

 パブリック void backTrace ( int [ ]候補、 intターゲット、 List < Integer >パス、 int開始) {

 （ターゲット< 0 ）の場合{
 戻る;
 }
 //終了条件を満たし、それを合計パスに追加します
 （ターゲット== 0 ）の場合
 allPath .add (新しい ArrayList (パス) ) ;
 戻る;
 }

 for ( int i = start ; i < candidates .length ; i ++ ) {
 //オプションリスト: 現在のノードは、取得するパス値より大きい
 if (ターゲット>=候補[ i ] ) {
 //選択する
 パス.add (候補[ i ] ) ;
 //再帰
 backTrace (候補, ターゲット候補[ i ] ,パス, i ) ;
 //選択を元に戻す
 パス.remove (パス.size ( ) - 1 ) ;
 }

 }
 }
 }

参考文献と謝辞

「Labuladong のアルゴリズム チートシート」

leetcode 公式サイト