復帰モードの本質は次のとおりです。 プログラムには、「フォーク」ポイントがあります。これは、動作（「代替」）の1つを選択する必要があるポイントです。 将来的には、選択したオプションが「失敗」となり、道路の分岐点に戻って他の選択肢を選択する必要があることが判明する可能性があります。
Becktrackingの特徴は、管理だけでなくデータにもロールバックがあることです。 ロールバック中、プログラムは失敗した代替を選択した結果として行ったすべてのことを「忘れ」ます。データは以前の値を復元し、代替を選択した結果はすべて取り消されます。 ロールバック後、次の代替策を取り、すべてのアクションを再実行します。 どの選択肢が受け入れられるかを確認します。 このフォークですべての選択肢が失敗した場合、失敗は上にあるフォークに伝播します。
Becktrackingは以下を提供します。
-ロールバック管理。
-データに応じたロールバック。
-選択肢のリストの列挙。
ロールバックアクションはありません。 例：スクリーン、プリンターなどへの印刷
フォークは、ローカルのもの（サブルーチンでのみ表示可能）とグローバル（サブルーチンが終了してもフォークが表示される）に分割できます。
したがって、プロシージャへのロールバックエントリが可能です。 手順が完全に復元され、すべてのローカル変数、値、および値の履歴が復元されます。
組織のオプション：
-代替としてデータとアクションを選択できます。 （手続きラベルの配列）
-代替のリスト：固定され、動的に計算され、まったく保存されない場合があります。
-一連の選択肢の自動並べ替え。
どの選択肢が成功をもたらすかを予測します。 （予測にはリソースが必要です。）。 しかし、代替案を整理し、最終的に結果に到達します。
-「故障」設計がない場合があります。 （分岐点を確立するための設計があるか、存在しません）
-ロールバックが可能です。最も近いフォーク、指定された静的/動的に、目的のフォークを自動的に決定します。
すべての選択肢を試した場合は、障害を上階に広げてください。
段階的にロールバックしないために、必要なものにロールバックする必要があります。
1.すべてのフォークをマークし、そこにロールバックします
2.フォークへのロールバックは動的に決定されます。
-自動フォーク検出。
プログラム内でのロールバック
呼び出されたルーチンへのロールバック
完了したルーチンへのロールバック。
手順の完了後にフォークにロールバックできる場合、フォークは外部にあります。
取り消せないアクション-ロールバック中にキャンセルされないアクションが存在する場合と存在しない場合があります。
-リターンモードを、動的/静的に、完全に/部分的に無効にすることができます。
-メッセージの失敗のシグナル、およびプログラム分析の可能性に関連付けることができます。
実装でバックトラッキングをサポートする言語があります（Prolog、Plener）。 この記事の一部として、明示的にサポートしていない言語でのリターンモードのエミュレーションを検討します。 この記事では、構文に邪魔されないようにリストを作成するために、パスカルのような疑似コードを使用します。
手続き指向言語でのバックトラッキングのスキーム実装。
このアプローチでは、再帰を使用してフォークをエミュレートし、ループを使用して代替を列挙します。
procedure TryAlt(N:trazvilka; var uspeh:boolean);
begin
{ }
uspeh:=false;
repeat { }
if { } then begin { }
if { ( )} then
uspeh:=true
else begin
try(N+1;uspeh);{ }
if uspeh then
{ }
{ }
end;
end;
until uspeh or
end.
安定した結婚の課題
2つの互いに素なセットAとBが同じサイズnで与えられていると仮定します。 nペアのセット<a、b>を見つける必要があります-AからのaとBからのbがいくつかの制限を満たすように。 配布基準は多数あります。 そのうちの1つを検討します。これは、安定結婚のルールと呼ばれます。
Aを多数の男性とし、Bを多数の女性とします。 各男性とすべての女性は、優先パートナーを示しました。 夫婦であるが、実際の配偶者よりも互いを好む男女が存在するような方法でカップルが形成される場合、この分布は不安定になります。 そのようなペアがない場合、分布は安定しています。 ペアの配布が行われた後でも、配布リストは変更されないことに注意してください。
解決策を見つけるための可能な方向は、両方のセットが使い果たされるまで、2つのセットのメンバーのペアを1つずつ配布しようとすることです。 この問題を解決するために、バックトラッキングスキームを使用して、単純化の方向に少し変更します。
Procedure tryMan (m : man);
Var
R : rang;
Begin
If m < n then
For r := 1 to n do begin
r- m
If then begin
;
Try ( m);
;
End;
end;
else
end;
男性と女性の好みを示す2つのマトリックスで初期データを表します。
Var
womanForMan : array [1..n,1..n] of woman
manForWoman : array [1..n,1..n] of man
したがって、womanForMan [m、r]は、男性のリストmのr番目の女性です。 同様に、manForWoman [w、r]は、女性wのリストでr番目にいる男性です。
結果は女性配列で表されるため、女性[m]は男性mの配偶者を表します。 対称性のために、man [w]が男性wの配偶者を示すように、manを導入します。 実際、man配列には、すでに女性に含まれている情報が含まれているため、冗長です。 提案された結婚のセットの安定性を判断するには、男女の配列の情報が必要です。 このセットは、提案された結婚ごとに個人をペアリングして安定性をチェックすることにより段階的に構築されるため、すべてのコンポーネントが定義される前に男女の配列が必要です。 どのコンポーネントが既に定義されているかを追跡するために、ブール配列を導入します：
singleMan、SingleWoman：ブールの配列[1..n]
コンポーネントの真実は、対応する男性（女性）が自由であることを意味します。
彼らの助けを借りて、述語はsingleWoman [w]結合として明確になり、結婚は安定します。
現在の重要なタスクは、安定性決定アルゴリズムを改良することです。 覚えておくべき最初の特徴は、定義により、安定性はランク（つまり、優先リスト内の位置）の比較から得られることです。 ただし、これまでに特定されたデータのコレクションのどこにも、男性と女性の直接アクセス可能なランクはありません。 もちろん、それらはwomanForManとmanForWomanの値によって計算できますが、安定性の計算は非常に一般的な操作であるため、この情報へのより直接的なアクセスを提供することをお勧めします。 これを行うために、2つの行列を導入します。
Rmw：鳴った配列[男性、女性]。
Rwm：鳴った配列[女性、男性]。
さらに、rmw [m、w]は男性mのリストの女性wのランクを表し、rwm [w、m]は女性wのリストの男性mのランクを表します。 これらの補助行列の値は変化せず、womanForManとmanForWomanの値によって最初から決定できます。
述語Marriage is stableは、その定義に従って正確に計算できます。 結婚の可能性を確認する必要があることを思い出させてくださいmとw、ここでw = womanForMan [m、r]。 まず、そのような結婚が許容されると仮定してから、この結婚の安定性への干渉を検出しようとします。 次の2つの干渉が発生する可能性があります。
1）mによると、wより高いランクの女性pwがいて、彼女自身が夫よりmを好む場合があります。
2）wによると、mより高いランクの男性pmがいて、彼自身が妻よりもwを好む場合があります。
最初の種類の干渉を検出するために、mがwを好むすべての女性、つまり、すべてのpw = womanForMan [m、i]のランクrwm [pw、m]とrwm [pw、man [pw]]を比較します。 r。 実際、すべての女性pwはすでに結婚しています。女性のいずれかがまだ結婚していない場合、mは彼女を以前に選択していたからです。 第2種の干渉を検出するには、wが現在のペアmを好むすべての候補pm、つまり、すべての男性pm = manForWoman [w、i]、i <rwm [w、m]を最初のケースと同様にチェックする必要がありますが、 pmがまだ結婚していないトピック女性[pm]との比較をスキップすることを忘れないでください。 これは、mまでのすべての男性が結婚していることがわかっているため、pm <mを確認することで確認できます。
安定性チェック手順の全文は次のようになります
Function stable(m, w, r : integer) : Boolean;
Var
Pw, pm, I, lim : integer;
S : Boolean;
Begin
I := 0; s := true;
Repeat
Inc(i);
If i<r then begin
Pw := womanForMan[m,i];
If not(singleWoman[pw]) then
S := rwm[pw,m] >rwmn[pw,man[pw]];
End;
Until (i=r) or (not(s));
I := ;0 lim := rwm[w,m];
Repeat
Inc(i);
If I < lim then begin
Pm := manForWoman[w,i];
If pm<m then
S := rmw[pm,w]>rmw[pm,woman[pm]
End;
Until (i=lim) or (nor(s));
End;
おわりに
このアルゴリズムはすべての可能な解決策を生成し、男性、女性、または平均のいずれかの最適な解決策を見つけるように修正できます。 それはすべて、このアルゴリズムが使用される目的に依存します。