递归回朔法简单总结

2017-9-10 释然 前端技术资源

如果您想订阅本博客内容,每天自动发到您的邮箱中, 请点这里

回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

在回溯法中,每次扩大当前部分解时,都面临一个可选的状态集合,新的部分解就通过在该集合中选择构造而成。这样的状态集合,其结构是一棵多叉树,每个树结点代表一个可能的部分解,它的儿子是在它的基础上生成的其他部分解。树根为初始状态,这样的状态集合称为状态空间树。

回溯法解题的关键要素:
确定了问题的解空间结构后,回溯法将从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。开始结点成为活结点,同时也成为扩展结点。在当前的扩展结点处,向纵深方向搜索并移至一个新结点,这个新结点就成为一个新的活结点,并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个活结点处,并使其成为当前的扩展结点。回溯法以上述工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。
运用回溯法解题的关键要素有以下三点:
(1) 针对给定的问题,定义问题的解空间;
(2) 确定易于搜索的解空间结构;
(3) 以深度优先方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。

我们来看一下递归实现回朔法的模板代码:

[java] view plain copy
  1. void BackTrace(int t) {  
  2.         if (t > n)  
  3.             Output(x);  
  4.         else  
  5.             for (int i = f(n, t); i <= g(n, t); i++) {  
  6.                 x[t] = h(i);  
  7.                 if (Constraint(t) && Bound(t))  
  8.                     BackTrace(t + 1);  
  9.             }  
  10.     }  


下边看几个LeetCode上几道典型的回朔法:

题目一:


题目的大意就是按照手机键盘上,每个数字可以表示的意义,给定一个字符串数字,列举出所有可能的字符组合~

结题思路:使用递归模板搞定

[java] view plain copy
  1. public class Solution {  
  2.     List<String> list = new ArrayList<String>();  
  3.     String[] letterMap = {  
  4.         " "// 0  
  5.         "",  // 1  
  6.         "abc",  
  7.         "def",  
  8.         "ghi",  
  9.         "jkl",  
  10.         "mno",  
  11.         "pqrs",  
  12.         "tuv",  
  13.         "wxyz"  
  14.     };  
  15.     public List<String> letterCombinations(String digits) {  
  16.         if(digits==null||digits.equals(""))  
  17.             return list;  
  18.           
  19.         generate(digits,0,"");  
  20.           
  21.         return list;  
  22.     }  
  23.     private void generate(String digits,int index,String s){  
  24.         // 此时s是其中的一个解  
  25.         if(index==digits.length()){  
  26.             list.add(s);  
  27.             return ;  
  28.         }  
  29.         char c = digits.charAt(index);  
  30.         if(c>='0'&&c<='9'&&c!='1'){  
  31.             String letters = letterMap[c-'0'];  
  32.             for(int i = 0;i<letters.length();i++){  
  33.                 generate(digits,index+1,s+letters.charAt(i));  
  34.             }  
  35.         }  
  36.           
  37.     }  
  38. }  


题目二:求全排列


题目大意就是给定一个数组,求其全排列组合

[java] view plain copy
  1. public class Solution {  
  2.     List<List<Integer>> res = new ArrayList<List<Integer>>();  
  3.     public List<List<Integer>> permute(int[] nums) {  
  4.         List<Integer> list = new ArrayList<Integer>();  
  5.         if(null==nums||nums.length==0)  
  6.             return res;  
  7.         get1Result(nums,0,list);  
  8.         return res;  
  9.     }  
  10.     // list中保存了一个有index个元素的排列  
  11.     // 向这个排列的末尾添加第index+1个元素,获得一个有index+1个元素的排列  
  12.     private void get1Result(int[] nums,int index,List<Integer> list){  
  13.         if(index==nums.length){  
  14.             res.add(new ArrayList<Integer>(list));  
  15.             return ;  
  16.         }  
  17.         for(int i = 0;i<nums.length;i++){  
  18.             if(!list.contains(nums[i])){  
  19.                 list.add(nums[i]);  
  20.                 get1Result(nums,index+1,list);  
  21.                 list.remove(list.size()-1);  
  22.             }  
  23.         }  
  24.               
  25.     }  
  26. }  


题目三:求所有组合


题目大意就是说从n个数中取出k个数,找出所有的组合,利用递归模板代码,我们可以得出以下的代码:

[java] view plain copy
  1. public class Solution {  
  2.     List<List<Integer>> res = new ArrayList<List<Integer>>();  
  3.     public List<List<Integer>> combine(int n, int k) {  
  4.         if(n<=0||k<=0||k>n)  
  5.             return res;  
  6.         List<Integer> list = new ArrayList<Integer>();  
  7.         generateCombine(n,k,1,list);  
  8.         return res;  
  9.     }  
  10.       
  11.     // 求解C(n,k),当前已经找到的组合存储在c中,需要从start开始搜索新的元素  
  12.     private void generateCombine(int n,int k,int start ,List<Integer> list){  
  13.         if(list.size()==k){  // 递归结束条件  
  14.             res.add(new ArrayList<Integer>(list));  
  15.             return ;  
  16.         }  
  17.         // 递归过程  
  18.          for(int i = start;i<=n;i++){  
  19.             list.add(i);  
  20.             generateCombine(n,k,i+1,list);  
  21.             list.remove(list.size()-1);  
  22.         }  
  23.     }  
  24. }  


运行结果如下:用了25ms。



这个时候就涉及到了一种回溯剪枝的问题,我们还是依照例子中的n = 4, k = 2来说明,有如下的树形图:


也就是说,我们可以在递归过程中,将不必要的枝条从树中减掉,比如说本例中的取4!!!

剪枝之后的代码如下:

[java] view plain copy
  1. public class Solution {  
  2.     List<List<Integer>> res = new ArrayList<List<Integer>>();  
  3.     public List<List<Integer>> combine(int n, int k) {  
  4.         if(n<=0||k<=0||k>n)  
  5.             return res;  
  6.         List<Integer> list = new ArrayList<Integer>();  
  7.         generateCombine(n,k,1,list);  
  8.         return res;  
  9.     }  
  10.       
  11.     // 求解C(n,k),当前已经找到的组合存储在c中,需要从start开始搜索新的元素  
  12.     private void generateCombine(int n,int k,int start ,List<Integer> list){  
  13.         if(list.size()==k){  
  14.             res.add(new ArrayList<Integer>(list));  
  15.             return ;  
  16.         }  
  17.         // 递归过程  
  18.         // 还有k-list.size()个空位,所以,[i...n]中至少要有k-list.size()个元素  
  19.         // i最多为n-(k-list.size())+1,否则没有那么多元素可以放入list中了。  
  20.         for(int i = start;i<=n-(k-list.size())+1;i++){  
  21.             list.add(i);  
  22.             generateCombine(n,k,i+1,list);  
  23.             list.remove(list.size()-1);  
  24.         }  
  25.     }  
  26. }  


运行结果如下:仅仅只用了4ms,也就是说少用了21ms,简直就是完美的提升~



总结:

针对递归实现的回溯法,我们的基本思路是,首先定义一个用于递归的函数,在主函数中调用该递归函数;然后在递归函数中先判断是否达到了递归结束条件,之后进行循环遍历,在循环过程中,依次进行递归操作,设计到list的操作,主要要remove进行回退;最后,如果可以的话,记得注意剪枝操作,可以大大提升运行效率哦~


蓝蓝设计www.lanlanwork.com )是一家专注而深入的界面设计公司,为期望卓越的国内外企业提供卓越的UI界面设计BS界面设计 、 cs界面设计 、 ipad界面设计 、 包装设计 、 图标定制 、 用户体验 、交互设计、 网站建设 平面设计服务


标签: 递归实现回朔法 回朔法简单总结 递归的函数


发表评论:

Powered by emlog 京ICP备12006971号-1 sitemap