[アルゴリズム]完全征服への遡及🤸‍♀️

特筆すべき問題集

・・【白準1488;】演算子𘚠・・

[白準9663]

【白準14501】

白駿[1799]:ビザンプ

ついせき

backtrackingは,再帰関数により種々の組合せの場合の数を探索するアルゴリズムである.
backtracking実装の核心は、クエリー範囲と内部関数の準備であるため、次の再帰からどこからどこへのナビゲーションを見つけることが重要です.現在のポイントが次の再帰をロードする場合、次の再帰の検索範囲をよく考慮すると、for文の範囲をコンテキストにうまく表現できます.

バックグラウンドトレースのデフォルトフォーマット

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
       //visited[i] = true; 혹은 뭔가 수행하고 싶은 조합 기준의 뽑기 기능
        combination(arr, visited, i + 1, n, r - 1);
        //visited[i] = false; 뽑은거 원상태로 돌리기 
    }
}

コンビネーションから必要な数の数字を抽出した場合、再帰関数の最上部でif(r=0)のようにカウント処理が行われる.
このときグループを選択して、処理すべきことを処理してから戻ればよい.
for文の基本形式はstartから総数を迂回し,startは再帰を呼び出すたびにi+1に増加する.

バックアップ・トラッキングの基本および複数のフォーマット

1.基本フォーマット

static void combination(int[] arr, int start, int n, int r) {
    if(r == 0) {
        // 조합을 다 뽑으면 수행할 내용 
        return;
    } 

    for(int i=start; i<n; i++) {
       //수행하고 싶은 조합 기준의 뽑기 기능
        combination(arr, i + 1, n, r - 1);
        //뽑은거 원상태로 돌리기 
    }
}

上記のように繰り返しますが、この形式は最も基本的な形式です.
始点からアレイの最後に移動します.
配列で出会った数字が組合せから抽出できる場合、2番目(または次のn個)の数字を抽出するために、現在位置の次の点を次の再帰の開始点に設定してから探索します.
このとき抽出する個数を1つ減らす必要があるので,r−1も再帰的な入力数として加える.



この場合,この方法を用いるとboolean visitのような数値が抽出されたか,数値にアクセスしたかを決定する必要はない.
図に示すように、現在位置の真下から再帰関数を検索するように再帰検索を設定するので、再帰は絶対に検索を繰り返すことはできません.

2.複数のオプションから1つを選択して、組合せのフォーマットを作成

この形式は[ホワイト148888]演算子問題で運用されている
複数のオプションの中から1つを選択して組合せを作成する形式で、その名の通り、数の限られた複数のグループのオプションの中から1つを選択して組合せを作成する方法です.
以下のコードは、4種類の演算子(加算、減算、乗算、除算)がそれぞれ抽出できる回数が与えられたときに使用できるコードです.
これにより、選択する集団が複数あり、数が限られている場合に使用することができる.

 public static void combination(int num, int index) {
        if (index == n) {
            max = Math.max(num, max);
            min = Math.min(num, min);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if(psmd[i]>0){
                psmd[i] --;
                switch (i){
                    case 0: combination(num+numbers[index],index+1); break;
                    case 1: combination(num-numbers[index],index+1); break;
                    case 2: combination(num*numbers[index],index+1); break;
                    case 3: combination(num/numbers[index],index+1); break;
                }
                psmd[i] ++;
            }
        }

このときのコアは、for文が毎回異なるstartを与えるのではなく、最初から最後のインデックスを参照し続けます.
これは、開始点のすべてのオプションを消費した場合、開始点のオプションではなく、次の再帰で前のオプションにナビゲートできる必要があるためです.

結果の組合せ構築プロセス

backtrackingの組合せ結果はbacktrackinput内で変数構築を行うことができる.
一方の値を単純にグローバル数値で教えるのではなく、if(r=0)関数部分でのみ処理されるbacktrackingの組合せ結果であれば、backtracking再帰関数の入力変数として定義します.
このような関数を使用して値構築結果の組合せを入力する場合は、再帰関数を呼び出すたびに、その入力値を構築値に入れればよい.

combination(result+numbers[index],index+1);
combination(resultString+string[index],index+1);

これにより再帰関数の入力値に直接構築できます!
もちろん、単純変数は再帰関数に直接+形式で貼り付けなければなりません.
値を返すと、手動で値を返す必要がなく、元の値に戻ります.

トレースバックの注意事項

indexブラウズを使用する場合はlistフォーマットを使用します

白準1759パスワードの作成問題のようにbacktrackingを使用したい場合は、探索中の配列要素が外部に挿入、挿入、終了すると流動性が変化します.
ArrayListやQueueのような形でdfs前後にremoveやaddを入れたい
でも!!!絶対にそうはいかない.
for文でナビゲートすると、インデックスは固定されているのではなく、流動的に挿入され、終了し、インデックスを1つずつ前に引くためです.
例:

for(int i = start; i<arrayList.size();i++){
	
    arrayList.remove(i);
    dfs(i+1,n);
    arrayList.add(i);
}

このようなコードはarrayListの最初のインデックスの要素を失い、再帰関数を呼び出して最後のインデックスの要素に追加すると、次の要素が最初のインデックスの要素になります.
次のナビゲーションでは、ナビゲーションが必要な次の要素が最初のindexの要素になるため、ナビゲーションはできませんが、次の要素からナビゲーションを開始します.
上のコードは簡単で、配列に列挙するだけでいいのですが、前述したようにbacktrackingで構造内の要素の再帰的な外部での流れの参加と終了を探索したい場合は、どうすればいいですか?

代替案

上記のコードは次のように変更できます.

static boolean[] visited = new boolean[arrayList.size()];

for(int i = start; i<arrayList.size();i++){
	
    visit[i] = true;
    dfs(i+1, n);
    visit[i] = false;
    
}

//외부에서 해당 ArrayList의 원소를 뺄 때
visit[i] = true;
//외부에서 해당 ArrayList의 원소를 넣을 때
visit[i] = false;

こんなに簡単に解決できます!
したがってbacktrackingで検索する配列の要素を外部で挿入および削除する必要がある場合、boolean形式の配列を使用してアクセスします.

最初から最後まで簡単なナビゲーションが必要な場合は、

白準1799毕紹普問題を参考にして理解することができます.
私たちがよく知っている裏通りを走るのは組み合わせを探すように、必ずいくつか数えて、目標値で引いたら、ドアを掛けて帰ります.
ただし,明確な目標値がなく,最初から最後まで探索する必要がある場合にはbacktrackingも用いられる.
逆追跡は単純な組合せで使用するだけでなく,種々の吸引の場合の数を計算する.
この場合、再帰関数をいつ返すべきかが気まずい.
backtrakingの基本フレームワークに夢中になりすぎたため、無視された事実がある.
これは非常に基本的ですが、すべての関数は関数の終了後に返されます(void関数などの戻り値がない場合)
そのため、簡単なエンドツーエンドのナビゲーションが必要です.
もう1つの戻る時間を探さなければ、forゲートで検索するだけでいいです.
この関数では、完全なナビゲーションが完了した時点がbacktrackingナビゲーション条件を満たすために返される時点です!
では、今の問題は、戻る前に条件が満たされたら、処理した機能はどうなるかということです.
これは、再帰関数が戻る(終了する)前に機能を更新し続け、必要な結果値を取得するだけです.

    static void dfs(int index, boolean black, int cnt) {

        for (int i = index; i < N * N; i++) {
            int x = i / N;
            int y = i % N;

            if (board[x][y] == 0 || isBlack[x][y] != black || !check(x, y))
                continue;

            visited[x][y] = true;
            dfs(i + 1, black, cnt + 1);
            visited[x][y] = false;
        }

        res[black ? 0 : 1] = Math.max(res[black ? 0 : 1], cnt);
    }

迅速な理解のために、トレースコードの例を示します.
この問題はチェス盤全体において,ビショップという言葉が上昇すれば最大数を求める問題である.
したがって,数の決まった組み合わせを選択するのではなく,最初から最後までチェス盤の探索によって馬が登れるか否かを判断し,最大数を繰り返し探索する場合である.
コードを見ると、単純にfor文ですべてのチェス盤の格を検索し、条件がチェス盤に馬を置くことを許可すれば、visitで馬を置くことや話題を移す形式を行うことができます.
文を返す条件が指定されていない場合、関数が返す各時点(関数の最後の部分)で文の個数を表すパラメータcountの最大値を更新し続けます.