バックトラッキングアルゴリズムは、原則として、与えられた問題にすべての可能な解を与えるために様々な方法で完了することができる部分的な候補のセットを列挙する。 完了は、一連の候補拡張ステップによって段階的に行われます。
概念的には、部分的な候補は、ツリー構造のノード、潜在的な探索ツリーとして表されます。 各部分候補は、単一の拡張ステップによってそれとは異なる候補の親です; ツリーの葉は、それ以上拡張することができない部分的な候補です。
バックトラッキングアルゴリズムは、この検索ツリーをルートから深さ一次で再帰的にトラバースします。 各ノードcで、アルゴリズムは、cが有効な解に完了できるかどうかをチェックします。 それができない場合は、cをルートとするサブツリー全体がスキップされます（剪定されます）。 それ以外の場合、アルゴリズムは(1)c自体が有効な解であるかどうかをチェックし、そうであればそれをユーザーに報告し、(2)cのすべてのサブツリーを再帰的に列挙します。
したがって、アルゴリズムによってトラバースされる実際の探索木は潜在的な木の一部にすぎません。 アルゴリズムの総コストは、実際のツリーのノード数に各ノードの取得と処理のコストを掛けたものです。 この事実は、潜在的な検索ツリーを選択し、剪定テストを実装するときに考慮する必要があります。
PseudocodeEdit
特定のクラスの問題にバックトラッキングを適用するためには、解決すべき問題の特定のインスタンスのデータPと、root、reject、accept、first、next、outputの六つのプロシージャーパラメータを提供する必要があります。 これらの手順では、インスタンスデータPをパラメーターとして受け取り、次の操作を実行する必要があります:
- root(P):検索ツリーのルートにある部分候補を返します。
- reject(P,c):部分候補cが完了する価値がない場合にのみtrueを返します。
- : cがPの解である場合はtrueを返し、それ以外の場合はfalseを返します。
- first(P,c):候補cの最初の拡張子を生成します。
- next(P,s):拡張子sの後に候補の次の代替拡張子を生成します。
- output(P,c):アプリケーションに応じて、Pの解cを使用します。
バックトラッキングアルゴリズムは、コールbacktrack(root(P))に問題を軽減します。backtrackは次の再帰的な手順です:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
使用上の考慮事項edit
rejectプロシージャは、cの可能な拡張がPの有効な解ではないことが確実な場合にのみtrueを返すブール値関数でなければなりません。 誤った真の結果は、bt手順がいくつかの有効な解決策を逃す可能性があります。 プロシージャは、reject(P,t)が検索ツリー内のcのすべての祖先tに対してfalseを返したと仮定することができます。
一方、バックトラッキングアルゴリズムの効率は、可能な限りルートに近い候補に対してtrueを返すrejectに依存します。 Rejectが常にfalseを返した場合でも、アルゴリズムはすべての解を検索しますが、ブルートフォース検索と同等になります。
acceptプロシージャは、cが問題のインスタンスPの完全かつ有効な解決策である場合はtrueを返し、それ以外の場合はfalseを返します。 部分候補ｃおよびツリー内のそのすべての祖先が拒絶検定に合格したと仮定することができる。
上記の一般的な擬似コードは、有効な解が常に潜在的な探索木の葉であるとは想定していません。 言い換えれば、Pに対する有効な解をさらに拡張して他の有効な解を得ることができる可能性を認めている。
最初と次の手順は、バックトラッキングアルゴリズムによって使用され、ツリーのノードcの子、つまりcとは異なる候補を単一の拡張ステップで列挙 呼び出しfirst(P,c)は、cの最初の子を何らかの順序で生成する必要があります; そして、next（P、s）の呼び出しは、ノードsの次の兄弟をその順序で返す必要があります。 要求された子が存在しない場合、両方の関数は特徴的な”NULL”候補を返す必要があります。
関数root、first、およびnextは、部分候補の集合と潜在的な探索木を定義します。 それらは、Pのすべての解が木のどこかに発生し、部分的な候補が複数回発生しないように選択する必要があります。 さらに、彼らは効率的で効果的な拒否述語を認めるべきです。
早期停止variantsEdit
上記の擬似コードは、指定されたインスタンスPの解であるすべての候補の出力を呼び出します。