全面解析回溯法：算法框架与问题求解.doc

全面解析回溯法：算法框架与问题求解目录什么是回溯法？回溯法的通用框架利用回溯法解决问题问题1：求一个集合的所有子集问题2：输出不重复数字的全排列问题3：求解数独剪枝的示范问题4：给定字符串，生成其字母的全排列问题5：求一个n元集合的k元子集问题6：电话号码生成字符串问题7：一摞烙饼的排序问题8：8皇后问题总结与探讨附：算法设计手册第7章其余面试题解答 摘了一段来自百度百科对回溯法思想的描述：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。 可以把回溯法看成是递归调用的一种特殊形式。其实对于一个并非编程新手的人来说，从来没使用过回溯法来解决问题的情况是很少见的，不过往往是“对症下药”，针对特定的问题进行解答。这些天看了算法设计手册回溯法相关内容，觉得对回溯法抽象的很好。如果说算法是解决问题步骤的抽象，那么这个回溯法的框架就是对大量回溯法算法的抽象。本文将对这个回溯法框架进行分析，并且用它解决一系列的回溯法问题。文中的回溯法采用递归形式。在进一步的抽象之前，先来回顾一下DFS算法。对于一个无向图如下图左，它的从点1开始的DFS过程可能是下图右的情况，其中实线表示搜索时的路径，虚线表示返回时的路径： 可以看出，在回溯法执行时，应当：保存当前步骤，如果是一个解就输出；维护状态，使搜索路径（含子路径）尽量不重复。必要时，应该对不可能为解的部分进行剪枝(pruning)。下面介绍回溯法的一般实现框架： bool finished = FALSE; /* 是否获得全部解? */backtrack(int a, int k, data input) int cMAXCANDIDATES; /*这次搜索的候选 */ int ncandidates; /* 候选数目 */ int i; /* counter */ if (is_a_solution(a,k,input) process_solution(a,k,input); else k = k+1; construct_candidates(a,k,input,c,&ncandidates); for (i=0; incandidates; i+) ak = ci; make_move(a,k,input); backtrack(a,k,input); unmake_move(a,k,input); if (finished) return; /* 如果符合终止条件就提前退出 */ 对于其中的函数和变量，解释如下：a表示当前获得的部分解；k表示搜索深度；input表示用于传递的更多的参数；is_a_solution(a,k,input)判断当前的部分解向量a1.k是否是一个符合条件的解construct_candidates(a,k,input,c,ncandidates)根据目前状态，构造这一步可能的选择，存入c数组，其长度存入ncandidatesprocess_solution(a,k,input)对于符合条件的解进行处理，通常是输出、计数等make_move(a,k,input)和unmake_move(a,k,input)前者将采取的选择更新到原始数据结构上，后者把这一行为撤销。 其实回溯法框架就是这么简单，通过这个框架，足以解决很多回溯法问题了。不信？下面展示一下：（由于后文所有代码均为在C中编写，因此bool类型用int类型代替，其中0为FALSE，非0为TRUE。） 问题1：求一个集合的所有子集解答：将3个主要的函数实现，这个问题就解决了。由于每次for循环中ak=ci，这是唯一的改动，并且在下次循环时会被覆盖，不需要专门编写make_move()和make_unmove()。 int is_a_solution(int a,int k, data input) return k=input;void construct_candidates(int a,int k, data input, int c,int *ncandidates) c0 = 1; c1 = 0; *ncandidates = 2;void process_solution(int a,int k,data input) int i; printf(); for(i=1;i=k;i+) if(ai) printf( %d,i); printf( n); 候选构造函数construct_candidates()相对简单，因为对每个集合中的元素和一个特定子集，只有出现和不出现这两种可能。调用这个函数只需：generate_subsets(int n)int aNMAX;backtrack(a,0,n);扩展：Skiena在算法设计手册第14章组合算法部分介绍了生成子集的三种方式：按排序生成、二进制位变换、格雷码。上面这个算法是二进制变换的一种，格雷码生成可以参考后面习题解答的7-18；而按排序生成则比较复杂，它按特定顺序生成，如1,2,3生成顺序为 , 1, 1, 2, 1, 2, 3, 1, 3, 2, 2, 3，并且建议除非有这种要求，否则不要使用这个方式。 问题2：输出不重复数字的全排列解答：与上1题不同的是，由于不能重复出现，每次选择的元素都将影响之后的候选元素集合。构造候选时应从之前获得的部分解中获取信息，哪些元素是可以后续使用的，哪些是不可以的： void construct_candidates(int a,int k, data input, int c,int *ncandidates) int i; int in_permNMAX+1; for(i=1;i=NMAX;i+) in_permi = 0; for(i=1;ik;i+) in_permai = 1; *ncandidates = 0; for(i=1;i=input;i+) if(!in_permi) c*ncandidates = i; *ncandidates += 1; 不过这里可以看出一个问题，如果每次都是需要选择分支时构造候选元素，势必会造成浪费。这里仅仅是一个展示，如果提高效率，可以把解空间和原空间优化到一起，这样不必每次都生成解空间。下面的代码是对这个问题更好的也是更常见的解法，我相信不少人都写过，并对上一种看似复杂的解法表示不屑一顾： void permutaion(int *array,int k,int length) int i; if (length=k) for(i=0;ilength;i+) printf(%d ,arrayi); printf(n); return; for(i=k;imovek.x = x; board-movek.y = y; /printf(k:%d left:%dn,k,board-freecount); *ncandidates = 0; if(x0 & y0) return; possible_values(x,y,board,possible); for(i=1;i=DIMENSION;i+) if(possiblei) c*ncandidates = i; *ncandidates += 1; /most constrained square selectionvoid next_square(int *x,int *y, boardtype *board) int m_x,m_y,i,j; int score,max_score; m_x = -1,m_y = -1, max_score = 0; for(i=1;i=DIMENSION;i+) for(j=1;jmij) /not blank continue; score = evaluate(i,j,board); if(score max_score) m_x = i; m_y = j; max_score = score; *x = m_x; *y = m_y;int evaluate(int x,int y,boardtype* board) int i,j,i_start,j_start; int score = 0; /row i = x; for(j=1;jmij 0); /column j=y; for(i=1;imij0); /3*3 square i_start = (i-1)/3 *3 +1; j_start = (j-1)/3 *3 +1; /the most left and up point in the 3*3 square for(i=i_start;i=i_start+2;i+) for(j=j_start;jmij0); return score;int possible_values(int x,int y,boardtype* board, int possible) int i,j; volatile int i_start,j_start; for(i=1;i=DIMENSION;i+) possiblei = 1; /row i = x; for(j=1;jmij = 0; /column j = y; for(i=1;imij = 0; /3*3 square i_start = (x-1)/3; i_start = i_start * 3 + 1; j_start = (y-1)/3; j_start = j_start * 3 + 1; /printf(i_start:%d j_start:%dn,i_start,j_start); /the most left and up point in the 3*3 square for(i=i_start;i=i_start+2;i+) for(j=j_start;jmij = 0; /printf(%d,%d):,x,y); /for(i=1;imovek.x,board-movek.y,ak,board);void unmake_move(int a, int k, boardtype *board) free_square(board-movek.x,board-movek.y,board);void fill_square(int x,int y,int key,boardtype* board) board-mxy = key; board-freecount-;void free_square(int x,int y,boardtype* board) board-mxy = 0; board-freecount+;make_move()和unmake_move()is_a_solution()是对freecount是否为0的判断，process_solution()可以用作输出填好的数独，这两个函数的解法略过。而backtrack()函数和基本框架相比，看上去没多大的区别。void backtrack(int a,int k, boardtype* input) int cDIMENSION; int ncandidates; int i; if(is_a_solution(a,k,input) process_solution(a,k,input); else k = k+1; construct_candidates(a,k,input,c,&ncandidates); for(i=0;incandidates;i+) ak = ci; make_move(a,k,input); backtrack(a,k,input); unmake_move(a,k,input); if (finished) return; backtrack of sudoku经测试，算法设计手册上的Hard级别的数独，我的这个程序可以获得和原书同样的解。 附注：这里是以数独为例展示回溯法。而如果需要专门进行数独求解，可以试试DancingLinks，有一篇文章对其进行介绍，感兴趣的读者可以自行查阅。另外有关DancingLinks的性能，可以参阅：算法实践舞蹈链（Dancing Links）算法求解数独。 问题4：给定一个字符串，生成组成这个字符串的字母的全排列（算法设计手册面试题7-14）解答：如果字符串内字母不重复，显然和问题2一样。如果字符串中有重复的字母，就比较麻烦了。不过套用回溯法框架仍然可以解决，为了简化候选元素的生成，将所有候选元素排列成数组，形成“元素-值”对，其中值代表这个元素还能出现几次，把ASCII码的AZ、az映射为数组下标051。实现如下： int is_a_solution(char a,int k, int len) return (k=len);void process_solution(char a,int k, int len) int i; for(i=1;i=k;i+) printf(%c,ai); printf(n);void backtrack(char a,int k, int len,int candidate) int i; if(is_a_solution(a,k,len) process_solution(a,k,len); else k = k+1; for(i=0;iMAXCANDIDATES;i+) if(candidatei) ak = i+ A ; candidatei -;/make_move backtrack(a,k,len,candidate); candidatei+;/unmake_move if (finished) return; void generate_permutations_of_string(char *p) /sort char aNMAX; int candidateMAXCANDIDATES; int i,len=strlen(p); for(i=0;iMAXCANDIDATES;i+) candidatei = 0; for(i=0;i=k0）。（算法设计手册面试题7-15）解答：如果想采用问题1的解法，需要稍作修改，使得遍历至叶结点（也即所有元素都进行标记是否在集合中）时，判断是不是一个解，即元素数目是否为k。满足才能输出。 #include #define MAXCANDIDATES 2#define NMAX 3typedef int data;int is_a_solution(int a,int k, data input);void construct_candidates(int a,int k,data input, int c,int *ncandidates);void process_solution(int a,int k, data input);static int finished = 0;void construct_candidates(int a,int k, data input, int c,int *ncandidates) c0 = 1; c1 = 0; *ncandidates = 2;void process_solution(int a,int k,data input) int i; printf(); for(i=1;in)|(k=input)/not a solution return; else k=k+1; construct_candidates(a,k,input,c,&ncandidates); for(i=0;incandidates;i+) ak = ci; if(ci) num+; backtrack(a,k,input,n,num); num-; else backtrack(a,k,input,n,num); if (finished) return; generate_subsets(int n) int aNMAX+1; backtrack(a,0,n,2,0);int main() generate_subsets(NMAX); 问题6：电话号码对应字符串电话键盘上有9个数字，其中29分别代表了几个字母，如2:ABC，3:DEF.等等。给定一个数字序列，输出它所对应的所有字母序列。（算法设计手册面试题7-17，以及编程之美3.2“电话号码对应英语单词”）解答：这个问题在回溯法里已经很简单了，因为每一步的选择都不影响下一步的选择。稍微要注意的一点是如何把数字与多个字母的对应关系告诉程序。这个存储结构和相应的construct_candidates()可能是这样的： static char ch104 = , , ABC, DEF, GHI, JKL, MNO, PQRS, TUV, WXYZ,;static int total10 =0,0,3,3,3,3,3,4,3,4; void construct_candidates(int a,int k,data input, int *c,int *ncandidates) *c = inputk-1 - 0; *ncandidates = total*c; return; 而backtrack()中填充解空间a则是这样的：ak = chci;你会发现，backtrack()和编程之美3.2节解法二的RecurisiveSearch()实质是一样的：都是回溯法嘛。当然，能简化还是应该尽量简化的。 /cij 数字i对应的第j个字母/totali 数字i一共对应几个字母/number 待转换的数字序列/answer 解空间/index 当前处理的数字的位置/n 电话号码总长度void recursive(int * number, int * answer, int index, int n) if(index = n) for(int i=0;in;i+) printf(%c, cnumberiansweri); printf(n); return; for(answerindex=0;answerindextotalnumberindex;answerindex+) recursive(number, answer, index+1, n); 问题7：一摞烙饼的排序（编程之美1.3）假设有一堆烙饼，大小不一，需要把它们摆成从下到上由大到小的顺序。每次翻转只能一次翻转最上面的几个烙饼，把它们上下颠倒。反复多次可以使烙饼有序。那么，最少应该翻转几次呢？解答：根据编程之美的分析可知，对于n个烙饼，如果每次都把最大的先翻到最上面，然后再把它翻到最下面，这样就只用处理最上面的(n-1)个。而翻完n-1个时，最小的必然已经在上面，因此，翻转的上界是2(n-1)。为了在搜索解的时候剪枝，如果当前翻转次数多于上界2(n-1)，则必然不是最少的，应该直接返回。同时，当烙饼内部几个部分分别有序时（比如3、4、5已经连在一起、9、10已经连在一起），不应该拆散它们，而是应该视为一个整体进行翻转。这样，每次把最大的和次大的翻在一起，肯定要优于上界。把这个不怎么紧密的下界记为LowerBound，值为顺序相邻两个烙饼大小不相邻顺序的对数(pairs，不是log)。这样，有了粗略的上界和下界，就可以进行剪枝了。为了更有效的剪枝，可以把当前翻转步数大于已记录解的翻转步数的所有解也给剪掉。套用回溯法的框架，以下是求解代码。虽然和编程之美上的C+的面向对象版本看上去不太一样，但实质是一样的： #include #include #include typedef int* data;int is_a_solution(int a,int k, int step);/void construct_candidates(int a,int k,data input, int c,int *ncandidates);void process_solution(int a,int n,int step, data input,data output);/void make_move(int a,int k, data input);/void unmake_move(int a,int k,data inupt);int LowerBound(int *CakeArray,int n);int UpperBound(int n);void Reverse(int CakeArray,int begin,int end);void generate_sort(int a,int n);void show(data output);static int maxStep;/is_sorted()int is_a_solution(int *CakeArray,int n,int step) int i; for(i=1;iCakeArrayi) return 0; if(stepmaxStep) return 1; return 0;void process_solution(int a,int n,int step,data input,data output) int i; maxStep = step; printf(new maxStep:%dn,maxStep); for(i=0;istep;i+) outputi = inputi; return;int UpperBound(int n) return 2*(n-1);int LowerBound(int *CakeArray,int n) int i,t,ret = 0; for(i=1;ibegin); int i,j,t; for(i=begin,j=end;imaxStep) return; if(is_a_solution(a,n,step) process_solution(a,n,step,input,output); else /construct_candidates(a,k,input,c,&ncandidates); for(i=1;in;i+) Reverse(a,0,i);/make_move(a,k,input); inputstep = i; backtrack(a,n,step+1,input,output); Reverse(a,0,i);/unmake_move(a,k,input); void generate_sort(int a,int n) maxStep = UpperBound(n); int *SwapArray = malloc(UpperBound(n)+1)*sizeof(int); int *minSwapArray = malloc(UpperBound(n)+1)*sizeof(int); backtrack(a,n,0,SwapArray,minSwapArray); show(minSwapArray);void show(data output) int i; for(i=0;imaxStep;i+) printf(%d,outputi); printf(n); return ;int main() int i,n; printf(number of pancake:); scanf(%d,&n); int *CakeArray = malloc(n*sizeof(int); printf(pancakes order(continuously):n); for(i=0;in;i+) scanf(%d,&CakeArrayi); printf(searching.n); generate_sort(CakeArray,n); return 0; 其实理解这个算法的关键是如何把“翻转烙饼”的过程抽象成数据结构的改变，回溯法倒不是那么重要。 问题8：8皇后问题国际象棋棋盘上有8*8个格子。现在有8枚皇后棋子，一个格子只能放一个棋子，求解所有放法，使得这些棋子不同行、不同列、且不在对角线上（(4,5)和(5,6)就是在对角线上的情况，不合法）。解答：上面练习了那么多回溯法的问题，我相信能看到这里的人水平已经足以解决这个问题了。按行放置可以保证棋子不同行，对于每种放置可能，检查是否与上面各行的棋子是否同列、同对角线。都不满足的才能选作此次的决策即可。 #include #define DIM 8int is_a_solution(int aDIMDIM,int row);/void construct_candidates(int a,int k,data input, int c,int *ncandidates);void process_solution(int aDIMDIM);/void make_move(int a,int k, data input);/void unmake_move(int a,int k,data inupt);static int finished = 0;static count = 0;int is_a_solution(int chessDIMDIM,int row) return (row = DIM);void process_solution(int chessDIMDIM) int i,j; count+;