450、バックトラッキング アルゴリズムとは何ですか? 一度見れば理解できますが、実際に書いてみると失敗します。

450、バックトラッキング アルゴリズムとは何ですか? 一度見れば理解できますが、実際に書いてみると失敗します。

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

Baidu 百科事典では、バックトラッキング アルゴリズムの定義を次のように説明しています。バックトラッキング アルゴリズムは、実際には列挙に似た検索と試行のプロセスです。主に、検索と試行のプロセス中に問題の解決策を探します。解決条件が満たされなくなったことが判明すると、「バックトラック」して戻り、他のパスを試します。バックトラッキングは、最適化条件に従って前方に検索し、目標を達成する最適化検索方法です。しかし、あるステップまで探索を進めた際に、当初の選択が最適ではなかったり、目的を達成できないことが判明した場合、1ステップ戻って新たな選択を行います。この失敗したらやり直すという手法をバックトラッキングと呼び、ある状態においてバックトラッキングの条件を満たすポイントを「バックトラッキングポイント」と呼びます。多くの複雑で大規模な問題は、「普遍的な問題解決法」として知られるバックトラッキング法を使用して解決できます。

わかりましたか？バックトラッキングアルゴリズムは、実際には継続的な探索と試行のプロセスです。探索が成功すれば成功です。探索が失敗した場合は、一歩下がって試行を続けます...、

合計

結合和は古典的なバックトラッキングアルゴリズムの問​​題であり、問​​題の 1 つは次のようになります。

合計が n になる k 個の数字の組み合わせをすべて見つけます。組み合わせには 1 から 9 までの正の整数のみが許可され、各組み合わせには重複した数字はありません。

例:

  • すべての数値は正の整数です。
  • ソリューション セットには繰り返しの組み合わせを含めることはできません。

例1:

  • 入力: k = 3、n = 7
  • 出力: [[1,2,4]]

例2:

  • 入力: k = 3、n = 9
  • 出力: [[1,2,6], [1,3,5], [2,3,4]]

この問題は非常に明確です。1 から 9 までの k 個の数字を選択し、その合計が n に等しく、これらの k 個の数字が重複しないという問題です。したがって、最初の選択を行うときは、これらの 9 つの数字から 1 つを選んで、この分岐に沿って進むことができます。2 番目の選択を行うときは、これらの 9 つの数字から 1 つを選ぶことができますが、重複する数字は選べないため、最初に選んだ数字は除外する必要があります。2 番目の選択を行うときは、残りの 8 つの数字から 1 つしか選ぶことができません...選択プロセスは比較的明確です。9方向ツリーとして考えることができます。葉ノードを除いて、各ノードには9つの子ノードがあり、次のようになります。

9 つの数字のうちの 1 つを選択するには、そのいずれかの枝に沿って進むことになります。これは実際には DFS です (DFS がわからない場合は、373、データ構造 6、ツリーを参照してください)。バイナリ ツリーの DFS コードは次のとおりです。

  1. 公共 静的void treeDFS(TreeNodeルート) {
  2.     ルート == nullの場合
  3. 戻る;
  4.     System.out.println(root.val ) ;
  5.     treeDFS(ルート.左); treeDFS(ルート.右) ;}

ここでは、バイナリツリーのDFSを模倣して9方向ツリーを書くことができます。9方向ツリーのDFSは、9つの子ノードを再帰的にトラバースすることです。コードは次のとおりです。

  1. 公共 静的void treeDFS(TreeNodeルート) {
  2.     // 再帰には終了条件が必要です
  3.     ルート == nullの場合
  4. 戻る;
  5.     System.out.println (root.val); //ループを通して9つのサブツリーをそれぞれ走査する
  6. ( int i = 1; i <= 9; i++)の場合{
  7.         //2、状況に応じてオプションとなるいくつかの操作
  8.         treeDFS( "i番目の子ノード" );
  9.         //3、状況に応じてオプションとなるいくつかの操作
  10.     }}

DFS は、実際にはすべてのブランチをトラバースすること、つまり、すべての可能な結果を​​リストすることと同じです。結果が n に等しい限り、それが私たちが探しているものです。では、この 9 進ツリーには最大で何層のレイヤーがあるでしょうか? k 個の数値があるため、最大で k 層のレイヤーしか存在できません。コードを見てみましょう

  1. パブリックリスト<リスト<整数>>combinationSum3( int k, int n) {
  2.     List<List< Integer >> res = new ArrayList<>();
  3.     dfs(res, 新しいArrayList<>(), k, 1, n);
  4.  resを返します。
  5.  }private void dfs(List<List< Integer >> res, List< Integer > list, int k, int start, int n) {
  6.     //終了条件。この条件が満たされた場合、それ以上検索する意味はありません。
  7.     if ( list.size () == k || n <= 0) {
  8.         //適切なセットが見つかったら、コレクションリストに追加します
  9.         (リストサイズ() == k && n == 0)の場合
  10.             res.add (新しいArrayList<>(リスト));
  11. 戻る;
  12.     }
  13.     //ループを通して、9つのサブツリーを個別に走査します
  14. ( int i = 開始; i <= 9; i++) {
  15.         //現在の値を選択
  16.         リストに追加します(i);
  17.         //再帰
  18.         dfs(res, リスト, k, i + 1, n - i);
  19.         // 選択を元に戻す
  20.         リストを削除します(リストのサイズ() - 1);
  21.     }
  22.  }

コードは比較的単純なので、分析してみましょう（理解している場合はスキップできます）。

  1. コード dfs の最初の部分は終了条件の判断です。 前回の 426 では、再帰とは何ですか? この記事を通じて、再帰を徹底的に理解できます。 再帰には終了条件が必要であると言われています。
  2. 次の for ループは、それぞれ 9 つの子ノードをトラバースします。ここで i は start から始まるため、サブツリーがまだ 9 つ存在しない可能性があることに注意してください。前述のように、9 つの数字から 1 つを選択した場合、2 回目は残りの 8 つからのみ選択でき、3 回目は残りの 7 つからのみ選択できます...
  3. 20 行目では、dsf の開始は i+1 です。ここで、なぜ i+1 なのかを説明する必要があります。たとえば、3 を選択した場合、次回は 4 から始める必要があります。1 を追加しないと、次回は 3 から始めることになり、数字が繰り返されることになり、明らかに問題の要件と矛盾します。
  4. なぜ for ループ内で毎回 1 から開始できないのでしょうか? 毎回 1 から開始すると、結果が繰り返されます。たとえば、[1, 2] が選択された場合、次回は [2, 1] が選択される場合があります。
  5. バックトラック アルゴリズムを理解していない場合、最後の行で選択が取り消される理由を理解するのが最も難しいかもしれません。私の公式アカウントをよく読んでいる方は、これが私がよく言及しているブランチ汚染問題であることをご存知かもしれません。リストは参照渡しされるため、あるブランチから別のブランチにジャンプするときに、前のブランチのデータを削除しないと、リストは前のブランチのデータを次のブランチに持ち込み、間違った結果になります（後述）。前のブランチのデータを削除することに加えて、別の方法としては、下の図に示すように、各ブランチが新しいリストとなり、互いに干渉しないように、各ブランチごとにリストを作成します。

コードは次のとおりです

  1. パブリックリスト<リスト<整数>>combinationSum3( int k, int n) {
  2.     List<List< Integer >> res = new ArrayList<>();
  3.     dfs(res, 新しいArrayList<>(), k, 1, n);
  4.  resを返します。
  5.  }private void dfs(List<List< Integer >> res, List< Integer > list, int k, int start, int n) {
  6.     //終了条件。この条件が満たされた場合、それ以上検索する意味はありません。
  7.     if ( list.size () == k || n <= 0) {
  8.         //適切なセットが見つかったら、コレクションリストに追加します
  9.         (リストサイズ() == k && n == 0)の場合
  10.             res.add (新しいArrayList<>(リスト));
  11. 戻る;
  12.     }
  13.     //ループを通して、9つのサブツリーを個別に走査します
  14. ( int i = 開始; i <= 9; i++) {
  15.         //新しいリストを作成し、元のリストから分離し、以前のリストに影響を与えずに現在のリストを変更します
  16.         List< Integer > subList = new LinkedList<>(list);
  17.         サブリストに追加(i);
  18.         //再帰
  19.         dfs(res, サブリスト, k, i + 1, n - i);
  20.         // 変更は新しいリストで行われ、元のリストは変更されないため、ここでは元に戻す操作がないことに注意してください。
  21.         // 元に戻す操作は必要ありません
  22.     }
  23.  }

最後に元に戻す操作がないことがわかります。これは、各ブランチが新しいリストであり、現在のブランチへの変更が他のブランチに影響しないため、操作を元に戻す必要がないためです。

注意: このようなコードは書かないようにしてください。この方法では問題は解決できますが、各ブランチでリストが再作成されるため、非常に非効率的です。

最後のコード行を理解するには、まず再帰とは何かを理解する必要があります。再帰は、再帰と戻りの 2 つの部分に分かれています。再帰は下方向に渡すことであり、戻りは戻ることです。再帰を呼び出すと最終的にどうなるかを確認するために、簡単な図を描いてみましょう。

これは非常に単純な三分木です。これに対して DFS トラバーサルを実行すると、パス 1→2 に沿って進むと、リストは [1, 2] になります。再帰呼び出しなので、最終的にはノード 1 に戻ります。2 が削除されない場合、1→4 の分岐に沿って進むと、[1, 2, 4] になります。しかし、実際には、1→4 の分岐の結果は [1, 4] になるはずです。前の分岐の値を持ってきたからです。ノード 1 と 2 を通過した後、最終的にノード 1 に戻ります。ノード 1 に戻るときは、ノード 2 の値を削除してリスト [1] を作成し、ブランチ 1→4 に沿って進むと、結果は [1, 4] になります。

バックトラッキング アルゴリズムのコード テンプレートをまとめてみましょう。

  1.  private void backtrack( "元のパラメータ" ) {
  2.     //終了条件（再帰には終了条件が必要です）
  3.     if ( "終了条件" ) {
  4.         //いくつかの論理演算（状況に応じてオプション）
  5. 戻る;
  6.     } for ( int i = "forループの開始時のパラメータ" ; i < "forループの終了時のパラメータ" ; i++) {
  7.         //いくつかの論理演算（状況に応じてオプション）
  8.         // 選択する
  9.         //再帰
  10.         backtrack( "新しいパラメータ" );
  11.         //いくつかの論理演算（状況に応じてオプション）
  12.         // 選択を元に戻す
  13.     }
  14.  }

テンプレートを使用すると、バックトラッキング アルゴリズムのコードを書くのは非常に簡単です。それでは、テンプレートに基づいて、いくつかの典型的なバックトラッキング ケースに対する答えを書いてみましょう。

8つのクイーンの問題

8 クイーン問題も、非常に古典的なバックトラッキング アルゴリズムの問​​題です。 以前、8 クイーン問題に関する特別な紹介がありました。 理解できない場合は、まず 394、古典的な 8 クイーン問題と N クイーン問題を参照してください。彼はただ挑戦し続けます。クイーンを現在の位置に配置できる場合は、そこに配置します。最後の列にも配置できれば成功です。特定の位置に配置できない場合は、前のステップに戻ってもう一度試します。例えば、次の図に示すように、まず最初の行の最初の列にクイーンを配置します。

次に、1 列目から始めて 2 行目の競合しない位置に別のクイーンを配置し、次に 3 行目…と続けます。競合せずに 8 行目に置くことができれば成功です。8 行目より前に競合がある場合は、前の手順に戻って適切な位置を探し続けます…コードを見てみましょう。

  1.  //row は行番号を示します
  2. パブリックvoid 解決( char [][] チェス, int行) {
  3.     //終了条件、行は0から始まり、最後の行を配置でき、成功を示します。 if (row == chess.length) { //自分で書いたパブリックメソッド、2次元配列を印刷します。 //主にデータのテストに使用されます。 Util.printTwoCharArrays(chess); System.out .println(); return ; } for ( int col = 0; col < chess.length; col++) {
  4.         //クイーンを現在の位置に配置できるかどうかを確認します
  5.         if (valid(チェス、行、列)) {
  6.             //現在の位置にクイーンを配置しても競合しない場合は、
  7.             //現在の位置にクイーンを置く
  8.             チェス[行][列] = 'Q' ;
  9.             // 再帰、次の行に続きます...
  10.             チェスを解く(チェス、行 + 1);
  11.             //現在の位置にあるクイーンを削除します
  12.             chess[行][列] = '.' ;
  13.         }
  14.     }
  15.  }

完全順列問題

繰り返しのない数字のシーケンスが与えられた場合、そのシーケンスのすべての可能な順列を返します。

  • 例：
  • 入力: [1,2,3]
  • 出力：

  1.  [  
  2.  [1,2,3],  
  3.  [1,3,2],  
  4.  [2,1,3],  
  5.  [2,3,1],  
  6.  [3,1,2],  
  7.  [3,2,1]  
  8.  ]

この問題は三分木として扱うことができるため、各ステップで 3 つの選択肢があります。具体的なプロセスは分析しません。上記のテンプレートに従ってコードを記述するだけです。

  1. パブリックリスト<リスト<整数>>並べ替え( int []数値){
  2.     List<List< Integer >> list = new ArrayList<>();
  3.     バックトラック(リスト、新しいArrayList<>()、数値);
  4. リストを返します。
  5.  }private void backtrack(List<List< Integer >> list, List< Integer > tempList, int [] nums) {
  6.     //終了条件
  7.     if ( tempList.size () == nums.length) {
  8.         // 説明: 組み合わせのグループを見つける
  9.         リストに新しいArrayList<>(tempList)を追加します。
  10. 戻る;
  11.     }
  12.  ( int i = 0; i < nums.length; i++) {
  13.         //重複はあり得ないので、重複がある場合は選択できません
  14.         tempList.contains (nums [ i])の場合
  15. 続く;
  16.         //現在の値を選択
  17.         tempList.add (nums[i]) ;
  18.         //再帰
  19.         バックトラック(リスト、tempList、数値);
  20.         // 選択を元に戻す
  21.         tempList.remove( tempList.size ()-1);
  22.     }
  23.  }

シンプルだと思いませんか？

部分集合問題

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

  • 注意: ソリューション セットには重複したサブセットを含めることはできません。
  • 例：
  • 入力:数字 = [1,2,3]
  • 出力：

  1. 入力: nums = [1,2,3]
  2. 出力：
  3.  [
  4.  [3]、
  5.  [1]、
  6.  [2]、
  7.  [1,2,3],
  8.  [1,3]、
  9.  [2,3]、
  10.  [1,2]、
  11.  []
  12.  ]

テンプレートに従って修正してみましょう。

  1. パブリックList<List< Integer >> サブセット( int [] nums) {
  2.     List<List< Integer >> list = new ArrayList<>();
  3.     // 最初にソートする
  4.     配列.sort(数値);
  5.     バックトラック(リスト、新しいArrayList<>()、数値、0);
  6. リストを返します。
  7.  }
  8. プライベート void backtrack(List<List< Integer >> list, List< Integer > tempList, int [] nums, int start) {
  9.     //ここで終了条件が書かれていないことに注意してください。再帰には終了条件が必要ではないでしょうか? なぜここに書かれていないのでしょうか? 実際、ここでの終了条件は
  10.     // forループで暗黙的に示されます。もちろん、if(start>nums.length) rerurn; と書くこともできますが、ここでは省略します。
  11.     リストに新しいArrayList<>(tempList)を追加します。
  12.  ( int i = start; i < nums.length; i++) {
  13.         // 選択する
  14.         tempList.add (nums[i]) ;
  15.         //再帰
  16.         バックトラック(リスト、tempList、nums、i + 1);
  17.         // 選択を元に戻す
  18.         tempList.remove( tempList.size ()-1);
  19.     }
  20.  }

したがって、このような質問に対する解決策は基本的にこのパターンに従います。つまり、最初に選択を行い、次に再帰し、最後に選択を元に戻すというものです。最初の例について説明したときに、元に戻す理由は、前のブランチの結果が次のブランチに引き継がれて誤った結果が発生するのを防ぐためであると述べました。ただし、両者の違いは、一方が終了条件の判断であり、もう一方が for ループの開始値であるという点です。これらには、特定の問題に対する特定の分析が必要です。それでは最後の数独パズルを見てみましょう。

数独を解く

皆さんは数独をやったことがあるでしょう？ルールは以下のとおりです。

数独の解答は次のルールに従います。

  • 1～9 の数字は各行に 1 回だけ表示できます。
  • 1 ～ 9 の数字は各列に 1 回だけ出現します。
  • 1 ～ 9 の数字は、太い実線で区切られた 3x3 の各マス目に 1 回だけ表示されます。

これ以上プロセスを分析しません。コードを直接見てください。コードには詳細なコメントもあります。この記事では、バックトラッキング アルゴリズムについて説明します。ここでは、主に backTrace メソッドを見ていきます。他のメソッドはまだ見る必要はありません。

  1.  //バックトラッキングアルゴリズム
  2. 公共 静的ブール値Sudokuを解く( char [][]ボード){
  3. トレースをボードに戻します(ボード、0、0)。
  4.  }//ここでのパラメータに注意してください。row は行番号を表し、col は列番号を表します。プライベート静的ブールバックトレース( char [][]ボード、 int行、 int列){
  5.     //行は0から始まることに注意してください。行がboard.lengthに等しい場合、数独は
  6.     //最後の行が読み込まれて走査され、数独の値が有効であることを示し、直接trueを返します 
  7.     行 == ボードの長さの場合
  8. 戻る 真実;
  9.     //現在の行の最後の列が走査された場合は、次の行の最初の列から開始します。ここでのトラバーサル // 順序は最初の行の最初の列から最後の列まで、次に 2 番目の行の最初の列から最後までです
  10.     // 1 列目、次に 3 行目... if (col == board.length)
  11.  return backTrace(board, row + 1, 0);
  12.     //現在の位置にすでに数字がある場合は、それ以上入力することはできません。この行の次の列に移動します。if (board[row][col] != '.' )
  13.  return backTrace(board, row, col + 1);
  14.     //上記の条件がいずれも満たされない場合は、1から9までの適切な数字を選択して数独を埋めます。
  15.  ( char i = '1' ; i <= '9' ; i++) {
  16.         // 数字 i が現在の位置 [行、列] に配置できるかどうかを判断します。配置できない場合は、適切な数字が見つかるまで次の数字を配置できるかどうかを判断します。1 から 9 までの数字のいずれも配置できない場合は、次の
  17.         // 直接戻る 間違い 
  18.         if (!isValid(ボード、行、列、i))
  19.  continue ; // 数値 i を入力できる場合は、数値 i を入力します board[row][col] = i; // 成功した場合は直接戻り、再試行する必要はありません if (backTrace(board, row, col))
  20. 戻る 真実;
  21.         //それ以外の場合はキャンセルして再選択します board[row][col] = '.' ;
  22.     } //現在の位置[行、列]に数字が入らなければ、直接falseを返す 
  23. 戻る 間違い;
  24.  }//現在の位置[row, col]に文字を格納できるかどうかを確認します cprivate static boolean isValid( char [][] board, int row, int col, char c) {
  25.  ( int i = 0; i < 9; i++)の場合{
  26.         ボード[i][col] != '.' && ボード[i][col] == c の場合
  27. 戻る 間違い;
  28.         ボード[行][i] != '.' && ボード[行][i] == c の場合
  29. 戻る 間違い;
  30.         if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&
  31.                 ボード[3 * (行 / 3) + i / 3][3 * (列 / 3) + i % 3] == c)
  32. 戻る 間違い;
  33.     }戻る 真実;
  34.  }

要約する

バックトラックアルゴリズムは、再帰と組み合わせると理解しやすくなります。再帰は2つの部分に分かれています。最初の部分は最初に渡され、2番目の部分は終了条件に達したときに戻ります。階乗の再帰を見てみましょう。

実際、バックトラッキング アルゴリズムは、値を下に渡すときに値を変更し、元に戻すときに元の値を復元します。たとえば、クイーンが 8 個ある場合、まず、クイーンを配置できる位置があると想定します。それが機能しない場合は、現在の位置をキャンセルし、クイーンを別の位置に配置します。組み合わせ問題の場合は、値を渡すときに現在の値をリストに追加し、戻すときにリストから削除します。

<<:  モノのインターネット向けのデータストリーミング、AI、機械学習プラットフォームを構築する方法

>>:  マスク氏：スマートウォッチや携帯電話は時代遅れの技術、脳コンピューターインターフェースこそが未来

推薦する

DAMOアカデミー物流ロボットQA

1. 物流ロボットとは？物流ロボット「Xiaomanlu」は、ターミナル物流シナリオ向けに設計され...

GoogleはOpenAIの競合企業Anthropicに最大20億ドルを投資することに同意したと報じられている

事情に詳しい関係者によると、10月28日、Googleはこれまでの投資に加え、OpenAIの競合企業...

Googleの人工知能部門DeepMindが想像力を駆使した新システムを開発

北京時間8月19日のreadwriteによると、2014年にGoogleに買収された英国の人工知能企...

自然言語処理がヒラリーとトランプの「話し方」を分析

[[173621]]編集者注：現地時間10月9日、米国大統領選挙の2人の候補者による第2回公開討論会...

テクノロジーフロンティア | 昆虫はIoT AIの未来となるか？

研究者たちは、特定の昆虫の神経系の機能が、決定論的、確率的、揮発性、不揮発性メモリの機能とどのように...

...

...

...

脳コンピューターインターフェースにおける重要な進歩！国内チームが「フルスペクトル中国語解読」に成功：トップ3の正解率は100％に迫る

今年8月、ネイチャー誌に立て続けに掲載された2つの論文は、脳コンピューターインターフェースが言語回復...

X-Dreamerは2Dと3D生成のギャップを埋め、高品質のテキストから3D生成を実現します。

近年、事前学習済みの拡散モデル[1, 2, 3]の開発により、テキストから3Dコンテンツへの自動作成...

AIは採用に何をもたらすのでしょうか?

人工知能は、次のような採用活動に大きく貢献しています。 [[433895]] 1. 候補者の自動ソー...

量子機械学習変分量子分類器 (VQC) の紹介

変分量子分類器 (VQC) は、量子コンピューティング技術を使用して分類タスクを実行する機械学習アル...

外国人の機械学習エンジニアは失業に直面しているのに、なぜ彼らはまだMLの学習にこだわるのでしょうか?

機械学習の分野では悲観的な見通しが広がっています。機械学習の人材の採用は減速しています。 [[334...

機械学習の経験を人生の指針に活用する: 学習効率を最大化する方法

[[185313]]原作者 | ライムンド・マンテローラ編集チーム | Aileen、Huang W...

ByteDanceは、従来の4倍の速度を誇る高性能トレーニングおよび推論エンジンLightSeqを発表した。

Transformer モデルは、Google チームが 2017 年に発表した論文「Attent...