バックトラッキングの概要

バックトラック 問題を解決するためのアルゴリズムに基づく手法です。再帰呼び出しを使用して、時間の経過とともに値を段階的に増やしながらソリューションを構築することにより、ソリューションを見つけます。問題を解決するために与えられた制約に基づいて、問題の解決をもたらさない解決策を削除します。

バックトラッキングアルゴリズムは、特定の種類の問題に適用されます。

• 問題の実行可能な解決策を見つけるために使用される決定問題。

• 適用できる最良の解決策を見つけるために使用される最適化問題。

• 問題のすべての実行可能な解決策のセットを見つけるために使用される列挙問題。

バックトラッキング問題では、アルゴリズムは、問題の実行可能なソリューションが見つからない場合に問題がバックトラックできる小さなチェックポイントを持つソリューションへのシーケンスパスを見つけようとします。

例、

ここで

緑は開始点、青は中間点、赤は実行可能な解決策のない点、濃い緑は終了点です。

ここで、アルゴリズムが最後まで伝播して解決策であるかどうかを確認する場合、解決策が返される場合は、解決策を見つけるために次のポイントへのトラックを見つけるために、その1ステップ後ろのポイントに戻ります。

アルゴリズム

Step 1 − if current_position is goal, return success
Step 2 − else,
Step 3 − if current_position is an end point, return failed.
Step 4 − else, if current_position is not end point, explore and repeat above steps.

このバックトラッキング問題を使用して、N-Queen問題の解決策を見つけましょう。 。

N-Queenの問題では、NxNチェス盤が与えられ、2人の女王が互いに攻撃しないようにn人の女王をボードに配置する必要があります。クイーンが水平、垂直、または斜めのポイントに配置されている場合、クイーンは別のクイーンを攻撃します。ここでは、4クイーン問題を行います。

ここで、解決策は-

ここでは、位置へのクイーンとして1を使用したnクイーン問題のバイナリ出力が配置されます。

{0 , 1 , 0 , 0}
{0 , 0 , 0 , 1}
{1 , 0 , 0 , 0}
{0 , 0 , 1 , 0}

n個のクイーンの問題を解決するために、クイーンを1行の異なる位置に配置してみます。そして、それが他の女王と衝突するかどうかをチェックします。 2人の女王が互いに攻撃している場合、女王の現在の位置。彼らが攻撃している場合、私たちは女王の以前の場所に戻ってその位置を変更します。そして、クラッシュオブクイーンズをもう一度チェックしてください。

アルゴリズム

Step 1 − Start from 1st position in the array.
Step 2 − Place queens in the board and check. Do,
   Step 2.1 − After placing the queen, mark the position as a part of the solution and then recursively check if this will lead to a solution.
   Step 2.2 − Now, if placing the queen doesn’t lead to a solution and trackback and go to step (a) and place queens to other rows.
   Step 2.3 − If placing queen returns a lead to solution return TRUE.
Step 3 − If all queens are placed return TRUE.
Step 4 − If all rows are tried and no solution is found, return FALSE.

それでは、バックトラッキングを使用して迷路のネズミを解決しましょう 問題-

迷路問題のラットでは、NxN迷路を使用して、迷路の最初の位置、つまり[0] [0]になり、アレイの位置[n-1][n-1]で終了します。この道には、解決策につながらない死んだ道がいくつかあります。

この問題でバックトラックを使用して、迷路の最終目標位置に到達するために段階的に下がっていきます。