全面解析回溯法:算法框架与问题求解.doc_第1页
全面解析回溯法:算法框架与问题求解.doc_第2页
全面解析回溯法:算法框架与问题求解.doc_第3页
全面解析回溯法:算法框架与问题求解.doc_第4页
全面解析回溯法:算法框架与问题求解.doc_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

全面解析回溯法:算法框架与问题求解目录什么是回溯法?回溯法的通用框架利用回溯法解决问题问题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+;

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论