窮挙再帰と遡及アルゴリズムの終結編
45653 ワード
窮挙再帰と遡及アルゴリズム
一般的な再帰関数では、二分検索、ファイルの反転など、決定点ごとに再帰を呼び出す必要があります(例えば、二分検索では、ノードごとに再帰左サブツリーまたは右サブツリーを選択する必要があります).このような再帰呼び出しでは、再帰呼び出しは線形構造に形成され、アルゴリズムの性能は呼び出し関数のスタック深さに依存します.たとえば、反転ファイルの場合、呼び出しスタックの深さはファイルのサイズに等しい.例えば、二分検索、再帰深さO(nlogn)の2種類の再帰呼び出しは非常に効率的である.
サブセット問題またはフル配列問題を考慮すると、各決定ポイントでは、再帰呼び出しのためにブランチを選択するだけでなく、すべてのブランチを再帰呼び出しに試行します.各決定ポイントには複数の選択があり、この複数の選択の各選択はbase caseに遭遇するまで、より多くの選択をもたらします.これにより,再帰呼び出しが進むにつれて,窮屈再帰アルゴリズムは時間的複雑度が高くなる.たとえば、各決定ポイントで、どのアルファベットを選択するか、現在の位置で次の都市(TSP)を選択するかを決定する必要があります.では、私たちは代価の高い貧乏な再帰を避ける方法がありますか?答えは状況によって決まる.場合によっては、グローバルな最適解を見つける必要があるなど、方法がありません.しかし、より多くの場合、私たちは満足のいく解を見つけることを望んでいます.各決定点では、再帰的な呼び出し経路だけを選択して、それが成功することを望んでいます.もし私たちが最終的に発見したら、満足のいく解を得ることができて、OK私たちは他の状況を遍歴しません.そうでなければ、今回の試みが成功しなかったら、決定点を返し、選択の試みを変えます.これが遡及アルゴリズムです.説明に値するのは、遡及の深さについて、私たちは最近の決定点に遡るだけで、この決定点が他の選択を満たして試していないことを満たす必要があります.遡及的に上昇するにつれて、最終的には初期状態に戻る可能性があります.この時、私たちはすでにすべての状況を窮挙して再帰しました.では、この問題は解けません.
典型的な問題の回顧
抽象的なのではないでしょうか.私もそう思いますが、仕方がないと思います.厳格さはやはりあります.もっと多くの例を見てみましょう.結局、私たちは実際の問題を解決するために勉強しています.
【経典貧挙問題】貧挙のすべての配列
質問の説明:文字列を指定し、再配置後に可能なすべての配置を出力します.
各決定ポイントでは、残りの処理対象文字列の中で、残りの文字列の長さがkであると仮定するアルファベットを選択する必要があります.各決定ポイントにはk種類の選択があり、各選択に対して1回試して、1つを選択するたびに、現在の文字列と残りの文字列を更新します.残りの文字列が空の場合、base caseに到達し、現在選択されている文字列を出力すればよい.疑似コード及びC++コードは以下の通りである.
この問題の中で、私たちはすべての可能な選択を試みて、貧乏な再帰に属して、全部でnがあります!に表示されます.これは非常に古典的なモードであり,クイズ問題,数独問題,最適化整合問題,スケジューリング問題など,多くの再帰アルゴリズムの核心であり,このモードによって解決できる.
【古典的窮挙問題】サブセット問題
質問の説明:集合を指定し、その集合のすべてのサブセットをリストします.
各決定点について、残りのセットから1つの要素を選択すると、2つの選択があります.サブセットには要素が含まれているか、含まれていないかがあります.これにより、ステップを返すたびに、残りのセットの要素が1つ減少し、残りのセットが空になるまでbase caseに着きます.疑似コード及びC++コードは以下の通りである.
これはもう一つの貧挙再帰の典型的な例である.再帰呼び出し問題の規模は毎回1つ減少するが,2つの新しい再帰呼び出しが生成され,時間的複雑度はO(2^n)である.これも古典的な問題であり,この種の問題を解決するpatternを銘記する必要があり,他にも最適充填問題,集合区分問題,最長共通サブ列問題(longest shared subsequence)などがある.
この2つの問題は似ているように見えますが、実際には大きな違いがあり、異なる2つの問題に属しています.permutation問題では,決定点ごとに現在のサブストリングに1つのアルファベットを含むように選択し,(残りのサブストリング長をnと仮定する)nがあり,選択ごとに再帰的に呼び出されるため,n規模のn−1のサブ問題,すなわちT(n)=nT(n−1)がある.subset問題では、各決定点でアルファベットの選択は残りのサブ列の頭文字にすぎませんが、私たちの決定の過程は選択or not選択(これは問題です.ハハ)で、私たちは1つのアルファベットを持って行った後、2回の再帰呼び出しをしました(permutation問題と比較して、私たちは次のアルファベットを持ってから1回の再帰呼び出ししかしません).従ってT(n)＝2＊T(n−1)である.
まとめて言えば、permutation問題は1つのアルファベットを持って行った後、再帰的に1回呼び出して、私たちの決定点はnつのアルファベットが持つことができます;subsetの問題は1つのアルファベットを持って行った後、2回の再帰呼び出しを行い、私たちの決定点は取るべきアルファベットを含むか含まないか、両者の違いをよく理解してください.
再帰的遡及
permutation問題とsubset問題において,それぞれの可能性を探索した.すべての決定点で、私たちはすべての可能な選択を試み、私たちがすべての可能な選択を挙げたことを知っています.これにより、時間の複雑さが高くなります.特に、多くの意思決定点があり、各意思決定点に多くの選択肢がある場合です.遡及アルゴリズムでは,条件を満たすと他の選択を行わない選択を試みた.このアルゴリズムの一般的な擬似コードパターンは以下の通りである.
遡及関数を書く忠告は、構造configurationに関する詳細を関数から取り出し(これらの詳細には、各決定点でどのような選択があり、選択が行われ、成功したかどうかを判断するなど)helper関数に入れ、主体関数をできるだけ簡潔に明確にすることで、遡及アルゴリズムの正確性を確保することができます.開発とデバッグにも役立ちます.
まず最初の例を見て,permutation問題から変異した.問題は文字列を指定して、合法的な単語を並べ直すことができますか?この問題はすべての状況を窮める必要はなく、合法的な単語を見つけるだけでよいので、遡及アルゴリズムで効率を速めることができます.合法的な単語を構成できれば、私たちはその単語をreturnします.そうでなければ空欄を返します.問題のbase caseは、辞書に単語が含まれているかどうかをチェックします.私たちが選択をするたびに再帰的に呼び出し、現在の選択をした後に成功するかどうかを判断し、できれば、他の可能性を試しません.もしできないなら、私たちは個別の選択を変えます.コードは次のとおりです.
このアルゴリズムをさらに剪定して,「袋小路」に入るのを早く避けることができる.たとえば、文字列を「zicquzcal」と入力すると、接頭辞「zc」を見つけたら、辞書に「zc」で始まる単語がないため、これ以上選択する必要はありません.具体的にはbase caseに別の終了条件を追加する必要があります.sofarが有効な接頭辞でない場合は、直接「」を返します.
【経典遡及問題1】八皇后問題
問題は8 x 8のチェス盤に8つのqueueを載せ、衝突しないことを要求することだ.(すなわち、任意の2つのqueueは同行せず、異なる列、異なる対角線)である.前述の基本パターンに従って、以下の擬似コードとC++コードを与えることができます.
【経典遡及問題2】数独問題
数独の問題は、スペースに1〜9の数字を記入することとして記述することができ、各行の各列の3＊3のサブ数独の数字1〜9が1回しか現れず、1回しか現れないことを要求する.一般的な数独問題は、解の一意性を保証するためにいくつかの数字を記入することを実現し、暴力的な解読を必要とせず、論理的な推理だけで完成することができる.今回はコンピューター暴力で遡って解を得てみましょう.数独問題を解決する疑似コードとC++コードは以下の通りである.
【経典遡及問題3】迷宮探索問題
この問題は、ブラックブロックがブロックを通過できないことを示し、ホワイトブロックがブロックを通過できることを示し、迷路の入口と所望の出口が与えられ、入口と出口を接続する経路を見つけることを要求するいくつかの白黒ブロックからなる迷路を実現する.前のテーマのマットがあって、コースは実は同じです.現在の位置では、周囲のすべてのブロックに対して、実行可能性を判断し、すべての実行可能なブロックに対して、私たちの現在のすべての可能なchoicesです.choiceを試して、再帰的な判断がsolutionを引き起こすことができるかどうか、できればreturn true;そうでなければ、別のchoiceを試してみます.すべてのchoiceが成功した解をもたらすことができない場合、return false.残りは再帰終了の条件であり,現在位置が目標位置に等しい場合,再帰終了,return trueである.C++コードは以下の通りです.
本文のまとめ
再帰遡及アルゴリズムは、ほとんどの作業の再帰過程が私たちを助けてくれたので、実は簡単だと理解しました.もう一度繰り返して、再帰遡及アルゴリズムの基本モード:現在の構造を識別して、現在の構造のすべての可能なchoiceを識別して、1つのchoiceを試して、再帰的な検査は1つのsolutionを招いたかどうか、もしそうならば、直接return true;そうでなければ別のchoiceを試してみます.すべてのchoiceを試みた場合、1つの解をもたらすことができず、return falseは遡及プロセスをトリガーします.残りは関数の最初に再帰的終了条件を定義することであり、これは具体的な問題の具体的な分析が必要であり、一般的には、現在の構造は目標構造、再帰的終了、return falseに等しい.
再帰遡及アルゴリズムの思想を理解した後、経典のpermutation問題とサブセット問題を覚えて、残りはもっと練習と思考を加えて、基本的にあまり難しい問題はありません.geekforgeeksのウェブサイトには遡及アルゴリズムの集合Backtrackingがあり、テーマは古典的で基本的に問題はありません.
参考文献
[1] Exhaustive recursion and backtracking
[2] www.geeksforgeeks.org-Backtracking
[3] Backtracking algorithms "CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms"
[4] Wikipedia: backtracking
一般的な再帰関数では、二分検索、ファイルの反転など、決定点ごとに再帰を呼び出す必要があります(例えば、二分検索では、ノードごとに再帰左サブツリーまたは右サブツリーを選択する必要があります).このような再帰呼び出しでは、再帰呼び出しは線形構造に形成され、アルゴリズムの性能は呼び出し関数のスタック深さに依存します.たとえば、反転ファイルの場合、呼び出しスタックの深さはファイルのサイズに等しい.例えば、二分検索、再帰深さO(nlogn)の2種類の再帰呼び出しは非常に効率的である.
サブセット問題またはフル配列問題を考慮すると、各決定ポイントでは、再帰呼び出しのためにブランチを選択するだけでなく、すべてのブランチを再帰呼び出しに試行します.各決定ポイントには複数の選択があり、この複数の選択の各選択はbase caseに遭遇するまで、より多くの選択をもたらします.これにより,再帰呼び出しが進むにつれて,窮屈再帰アルゴリズムは時間的複雑度が高くなる.たとえば、各決定ポイントで、どのアルファベットを選択するか、現在の位置で次の都市(TSP)を選択するかを決定する必要があります.では、私たちは代価の高い貧乏な再帰を避ける方法がありますか?答えは状況によって決まる.場合によっては、グローバルな最適解を見つける必要があるなど、方法がありません.しかし、より多くの場合、私たちは満足のいく解を見つけることを望んでいます.各決定点では、再帰的な呼び出し経路だけを選択して、それが成功することを望んでいます.もし私たちが最終的に発見したら、満足のいく解を得ることができて、OK私たちは他の状況を遍歴しません.そうでなければ、今回の試みが成功しなかったら、決定点を返し、選択の試みを変えます.これが遡及アルゴリズムです.説明に値するのは、遡及の深さについて、私たちは最近の決定点に遡るだけで、この決定点が他の選択を満たして試していないことを満たす必要があります.遡及的に上昇するにつれて、最終的には初期状態に戻る可能性があります.この時、私たちはすでにすべての状況を窮挙して再帰しました.では、この問題は解けません.
典型的な問題の回顧
抽象的なのではないでしょうか.私もそう思いますが、仕方がないと思います.厳格さはやはりあります.もっと多くの例を見てみましょう.結局、私たちは実際の問題を解決するために勉強しています.
【経典貧挙問題】貧挙のすべての配列
質問の説明:文字列を指定し、再配置後に可能なすべての配置を出力します.
各決定ポイントでは、残りの処理対象文字列の中で、残りの文字列の長さがkであると仮定するアルファベットを選択する必要があります.各決定ポイントにはk種類の選択があり、各選択に対して1回試して、1つを選択するたびに、現在の文字列と残りの文字列を更新します.残りの文字列が空の場合、base caseに到達し、現在選択されている文字列を出力すればよい.疑似コード及びC++コードは以下の通りである.
1 // Permutation Problem
2 // If you have no more characters left to rearrage, print the current permutation
3 // for (every possible choice among the characters left to rearrage)
4 // {
5 // Make a choice and add that character to the permutation so far
6 // Use recursion to rearrage the remaing letters
7 // }
8 //
9 void RecursivePermutation(string sofar, string remain)
10 {
11 if (remain == "") {cout << sofar << endl; reutrn;}
12
13 for (size_t i = 0; i < remain.size(); ++i)
14 {
15 string sofar2 = sofar + remain[i];
16 string remain2 = remain.substr(0, i) + remain.substr(i+1);
17 RecursivePermutation(sofar2, remain2);
18 }
19 }この問題の中で、私たちはすべての可能な選択を試みて、貧乏な再帰に属して、全部でnがあります!に表示されます.これは非常に古典的なモードであり,クイズ問題,数独問題,最適化整合問題,スケジューリング問題など,多くの再帰アルゴリズムの核心であり,このモードによって解決できる.
【古典的窮挙問題】サブセット問題
質問の説明:集合を指定し、その集合のすべてのサブセットをリストします.
各決定点について、残りのセットから1つの要素を選択すると、2つの選択があります.サブセットには要素が含まれているか、含まれていないかがあります.これにより、ステップを返すたびに、残りのセットの要素が1つ減少し、残りのセットが空になるまでbase caseに着きます.疑似コード及びC++コードは以下の通りである.
1 // Subset Problem
2 //
3 // If there are no more elements remaining, print current subset
4 // Consider the next element of those remaining
5 // Try adding it to current subset and use recursion to build subsets from here
6 // Try not adding it to current subset and use recursion to build subsets from here
7 void RecursiveSubset(string sofar, string remain)
8 {
9 // base case
10 if (remain == "") { cout << sofar << endl; return; }
11
12 char ch = remain[0];
13 string remain2 = remain.substr(1);
14 RecursiveSubset(sofar, remain2); // choose first element
15 RecursiveSubset(sofar + ch, remain2); // not choose first element
16 }これはもう一つの貧挙再帰の典型的な例である.再帰呼び出し問題の規模は毎回1つ減少するが,2つの新しい再帰呼び出しが生成され,時間的複雑度はO(2^n)である.これも古典的な問題であり,この種の問題を解決するpatternを銘記する必要があり,他にも最適充填問題,集合区分問題,最長共通サブ列問題(longest shared subsequence)などがある.
この2つの問題は似ているように見えますが、実際には大きな違いがあり、異なる2つの問題に属しています.permutation問題では,決定点ごとに現在のサブストリングに1つのアルファベットを含むように選択し,(残りのサブストリング長をnと仮定する)nがあり,選択ごとに再帰的に呼び出されるため,n規模のn−1のサブ問題,すなわちT(n)=nT(n−1)がある.subset問題では、各決定点でアルファベットの選択は残りのサブ列の頭文字にすぎませんが、私たちの決定の過程は選択or not選択(これは問題です.ハハ)で、私たちは1つのアルファベットを持って行った後、2回の再帰呼び出しをしました(permutation問題と比較して、私たちは次のアルファベットを持ってから1回の再帰呼び出ししかしません).従ってT(n)＝2＊T(n−1)である.
まとめて言えば、permutation問題は1つのアルファベットを持って行った後、再帰的に1回呼び出して、私たちの決定点はnつのアルファベットが持つことができます;subsetの問題は1つのアルファベットを持って行った後、2回の再帰呼び出しを行い、私たちの決定点は取るべきアルファベットを含むか含まないか、両者の違いをよく理解してください.
再帰的遡及
permutation問題とsubset問題において,それぞれの可能性を探索した.すべての決定点で、私たちはすべての可能な選択を試み、私たちがすべての可能な選択を挙げたことを知っています.これにより、時間の複雑さが高くなります.特に、多くの意思決定点があり、各意思決定点に多くの選択肢がある場合です.遡及アルゴリズムでは,条件を満たすと他の選択を行わない選択を試みた.このアルゴリズムの一般的な擬似コードパターンは以下の通りである.
1 bool Solve(configuration conf)
2 {
3 if (no more choice)
4 return (conf is goal state);
5
6 for (all available choices)
7 {
8 try choice c;
9
10 ok = solve(conf with choice c made);
11 if (ok)
12 return true;
13 else
14 unmake c;
15 }
16
17 retun false;
18 }遡及関数を書く忠告は、構造configurationに関する詳細を関数から取り出し(これらの詳細には、各決定点でどのような選択があり、選択が行われ、成功したかどうかを判断するなど)helper関数に入れ、主体関数をできるだけ簡潔に明確にすることで、遡及アルゴリズムの正確性を確保することができます.開発とデバッグにも役立ちます.
まず最初の例を見て,permutation問題から変異した.問題は文字列を指定して、合法的な単語を並べ直すことができますか?この問題はすべての状況を窮める必要はなく、合法的な単語を見つけるだけでよいので、遡及アルゴリズムで効率を速めることができます.合法的な単語を構成できれば、私たちはその単語をreturnします.そうでなければ空欄を返します.問題のbase caseは、辞書に単語が含まれているかどうかをチェックします.私たちが選択をするたびに再帰的に呼び出し、現在の選択をした後に成功するかどうかを判断し、できれば、他の可能性を試しません.もしできないなら、私たちは個別の選択を変えます.コードは次のとおりです.
1 string FindWord(string sofar, string rest, Dict& dict)
2 {
3 // Base Case
4 if (sofar.empty())
5 {
6 return (dict.containWords(sofar)? sofar : "");
7 }
8
9 for (int i = 0; i < rest.size(); ++i)
10 {
11 // make a choice
12 string sofar2 = sofar + rest[i];
13 string rest2 = rest.substr(0, i) + rest.substr(i+1);
14 String found = FindWord(sofar2, rest2, dict);
15
16 // if find answer
17 if (!found.empty()) return found;
18 // else continue next loop, make an alternative choice
19 }
20
21 return "";このアルゴリズムをさらに剪定して,「袋小路」に入るのを早く避けることができる.たとえば、文字列を「zicquzcal」と入力すると、接頭辞「zc」を見つけたら、辞書に「zc」で始まる単語がないため、これ以上選択する必要はありません.具体的にはbase caseに別の終了条件を追加する必要があります.sofarが有効な接頭辞でない場合は、直接「」を返します.
【経典遡及問題1】八皇后問題
問題は8 x 8のチェス盤に8つのqueueを載せ、衝突しないことを要求することだ.(すなわち、任意の2つのqueueは同行せず、異なる列、異なる対角線)である.前述の基本パターンに従って、以下の擬似コードとC++コードを与えることができます.
#include <iostream>
#include <vector>
using namespace std;
// Start in the leftmose column
//
// If all queens are placed, return true
// else for (every possible choice among the rows in this column)
// if the queue can be placed safely there,
// make that choice and then recursively check if this choice lead a solution
// if successful, return true
// else, remove queue and try another choice in this colunm
// if all rows have been tried and nothing worked, return false to trigger backtracking
const int NUM_QUEUE = 4;
const int BOARD_SIZE = 4;
typedef vector<vector<int> > Grid;
void PlaceQueue(Grid& grid, int row, int col);
void RemoveQueue(Grid& grid, int row, int col);
bool IsSafe(Grid& grid, int row, int col);
bool NQueue(Grid& grid, int curcol);
void PrintSolution(const Grid& grid);
int main()
{
vector<vector<int> > grid(BOARD_SIZE, vector<int>(BOARD_SIZE, 0));
if (NQueue(grid, 0))
{
cout << "Find Solution" << endl;
PrintSolution(grid);
}
else
{
cout << "Cannot Find Solution" << endl;
}
return 0;
}
void PlaceQueue(Grid& grid, int row, int col)
{
grid[row][col] = 1;
}
void RemoveQueue(Grid& grid, int row, int col)
{
grid[row][col] = 0;
}
bool IsSafe(Grid& grid, int row, int col)
{
int i = 0;
int j = 0;
// check row
for (j = 0; j < BOARD_SIZE; ++j)
{
if (j != col && grid[row][j] == 1) return false;
}
// check col
for (i = 0; i < BOARD_SIZE; ++i)
{
if (i != row && grid[i][col] == 1) return false;
}
// check left upper diag
for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
{
if (grid[i][j] == 1) return false;
}
// check left lower diag
for (i = row + 1, j = col - 1; i < BOARD_SIZE && j >= 0; i++, j--)
{
if (grid[i][j] == 1) return false;
}
return true;
}
bool NQueue(Grid& grid, int curcol)
{
// Base case
if (curcol == BOARD_SIZE)
{
return true;
}
for (int i = 0; i < BOARD_SIZE;++i)
{
if (IsSafe(grid, i, curcol))
{
// try a choice
PlaceQueue(grid, i, curcol);
// if this choice lead a solution, return
bool success = NQueue(grid, curcol + 1);
if (success) return true;
// else unmake this choice, try an alternative choice
else RemoveQueue(grid, i, curcol);
}
}
return false;
}
void PrintSolution(const Grid& grid)
{
for (int i = 0; i < BOARD_SIZE; ++i)
{
for (int j = 0; j < BOARD_SIZE; ++j)
{
cout << grid[i][j] << " ";
}
cout << endl;
}
cout << endl;
}【経典遡及問題2】数独問題
数独の問題は、スペースに1〜9の数字を記入することとして記述することができ、各行の各列の3＊3のサブ数独の数字1〜9が1回しか現れず、1回しか現れないことを要求する.一般的な数独問題は、解の一意性を保証するためにいくつかの数字を記入することを実現し、暴力的な解読を必要とせず、論理的な推理だけで完成することができる.今回はコンピューター暴力で遡って解を得てみましょう.数独問題を解決する疑似コードとC++コードは以下の通りである.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdio>
using namespace std;
// Base Case: if cannot find any empty cell, return true
// Find an unsigned cell (x, y)
// for digit from 1 to 9
// if there is not conflict for digit at (x, y)
// assign (x, y) as digit and Recursively check if this lead to a solution
// if success, return true
// else remove the digit at (x, y) and try another digit
// if all digits have been tried and still have not worked out, return false to trigger backtracking
const int GRID_SIZE = 9;
const int SUB_GRID_SIZE = 3;
typedef vector<vector<int> > Grid;
bool IsSafe(const Grid& grid, int x, int y, int num);
bool FindEmptyCell(const Grid& grid, int& x, int& y);
bool Sudoku(Grid& grid);
void PrintSolution(const Grid& grid);
int main()
{
freopen("sudoku.in", "r", stdin);
vector<vector<int> > grid(GRID_SIZE, vector<int>(GRID_SIZE, 0));
for (int i = 0; i < GRID_SIZE; ++i)
{
for (int j = 0; j < GRID_SIZE; ++j)
{
cin >> grid[i][j];
}
}
if (Sudoku(grid))
{
cout << "Find Solution " << endl;
PrintSolution(grid);
cout << endl;
}
else
{
cout << "Solution does not exist" << endl;
}
return 0;
}
bool Sudoku(Grid& grid)
{
// base case
int x = 0; int y = 0;
if (!FindEmptyCell(grid, x, y)) return true;
// for all the number
for (int num = 1; num <= 9; ++num)
{
if (IsSafe(grid, x, y, num))
{
// try one choice
grid[x][y] = num;
// if this choice lead to a solution
if (Sudoku(grid)) return true;
// otherwise, try an alternative choice
else grid[x][y] = 0;
}
}
return false;
}
bool IsSafe(const Grid& grid, int x, int y, int num)
{
// check the current row
for (int j = 0; j < grid[x].size(); ++j)
{
if (j != y && grid[x][j] == num) return false;
}
// check current col
for (int i = 0; i < grid.size(); ++i)
{
if (i != x && grid[i][y] == num) return false;
}
// check the subgrid
int ii = x / 3;
int jj = y / 3;
for (int i = ii * SUB_GRID_SIZE; i < (ii+1) * SUB_GRID_SIZE; ++i)
{
for (int j = jj * SUB_GRID_SIZE; j < (jj+1) * SUB_GRID_SIZE; ++j)
{
if (i != x || j != y)
{
if (grid[i][j] == num) return false;
}
}
}
return true;
}
// Find next Empty Cell
bool FindEmptyCell(const Grid& grid, int& x, int& y)
{
for (int i = 0; i < GRID_SIZE; ++i)
{
for (int j = 0; j < GRID_SIZE; ++j)
{
if (grid[i][j] == 0)
{
x = i;
y = j;
return true;
}
}
}
return false;
}
void PrintSolution(const Grid& grid)
{
for (int i = 0; i < GRID_SIZE; ++i)
{
for (int j = 0; j < GRID_SIZE; ++j)
{
cout << grid[i][j] << " ";
}
cout << "
";
}
cout << endl;
}【経典遡及問題3】迷宮探索問題
この問題は、ブラックブロックがブロックを通過できないことを示し、ホワイトブロックがブロックを通過できることを示し、迷路の入口と所望の出口が与えられ、入口と出口を接続する経路を見つけることを要求するいくつかの白黒ブロックからなる迷路を実現する.前のテーマのマットがあって、コースは実は同じです.現在の位置では、周囲のすべてのブロックに対して、実行可能性を判断し、すべての実行可能なブロックに対して、私たちの現在のすべての可能なchoicesです.choiceを試して、再帰的な判断がsolutionを引き起こすことができるかどうか、できればreturn true;そうでなければ、別のchoiceを試してみます.すべてのchoiceが成功した解をもたらすことができない場合、return false.残りは再帰終了の条件であり,現在位置が目標位置に等しい場合,再帰終了,return trueである.C++コードは以下の通りです.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int BOARD_SIZE = 4;
enum GridState {Gray, White, Green};
const int DIRECTION_NUM = 2;
const int dx[DIRECTION_NUM] = {0, 1};
const int dy[DIRECTION_NUM] = {1, 0};
typedef vector<vector<GridState> > Grid;
bool IsSafe(Grid& grid, int x, int y);
bool SolveRatMaze(Grid& grid, int curx, int cury);
void PrintSolution(const Grid& grid);
int main()
{
vector<vector<GridState> > grid(BOARD_SIZE, vector<GridState>(BOARD_SIZE, White));
for (int j = 1; j < BOARD_SIZE; ++j) grid[0][j] = Gray;
grid[1][2] = Gray;
grid[2][0] = Gray; grid[2][2] = Gray; grid[2][3] = Gray;
// Place the init position
grid[0][0] = Green;
bool ok = SolveRatMaze(grid, 0, 0);
if (ok)
{
cout << "Found Solution" << endl;
PrintSolution(grid);
}
else
{
cout << "Solution does not exist" << endl;
}
return 0;
}
bool SolveRatMaze(Grid& grid, int curx, int cury)
{
// base case
if (curx == BOARD_SIZE - 1 && cury == BOARD_SIZE - 1) return true;
// for every choice
for (int i = 0; i < DIRECTION_NUM; ++i)
{
int nextx = curx + dx[i];
int nexty = cury + dy[i];
if (IsSafe(grid, nextx, nexty))
{
// try a choice
grid[nextx][nexty] = Green;
// check whether lead to a solution
bool success = SolveRatMaze(grid, nextx, nexty);
// if yes, return true
if (success) return true;
// no, try an alternative choice, backtracking
else grid[nextx][nexty] = White;
}
}
// try every choice, still cannot find a solution
return false;
}
bool IsSafe(Grid& grid, int x, int y)
{
return grid[x][y] == White;
}
void PrintSolution(const Grid& grid)
{
for (int i = 0; i < BOARD_SIZE; ++i)
{
for (int j = 0; j < BOARD_SIZE; ++j)
{
cout << grid[i][j] << " ";
}
cout << "
";
}
cout << endl;
}本文のまとめ
再帰遡及アルゴリズムは、ほとんどの作業の再帰過程が私たちを助けてくれたので、実は簡単だと理解しました.もう一度繰り返して、再帰遡及アルゴリズムの基本モード:現在の構造を識別して、現在の構造のすべての可能なchoiceを識別して、1つのchoiceを試して、再帰的な検査は1つのsolutionを招いたかどうか、もしそうならば、直接return true;そうでなければ別のchoiceを試してみます.すべてのchoiceを試みた場合、1つの解をもたらすことができず、return falseは遡及プロセスをトリガーします.残りは関数の最初に再帰的終了条件を定義することであり、これは具体的な問題の具体的な分析が必要であり、一般的には、現在の構造は目標構造、再帰的終了、return falseに等しい.
再帰遡及アルゴリズムの思想を理解した後、経典のpermutation問題とサブセット問題を覚えて、残りはもっと練習と思考を加えて、基本的にあまり難しい問題はありません.geekforgeeksのウェブサイトには遡及アルゴリズムの集合Backtrackingがあり、テーマは古典的で基本的に問題はありません.
参考文献
[1] Exhaustive recursion and backtracking
[2] www.geeksforgeeks.org-Backtracking
[3] Backtracking algorithms "CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms"
[4] Wikipedia: backtracking