Go语言视频零基础入门到精通

javalearner

一、  回溯的基本思想是：
     从一个给定的起始位置，我们希望到达一个目的位置。
我们重复地进行选择（可能是猜测）下一个位置应当是什么。如果一个给定的选择是有效的， 即新的位置可能位于通向目的位置的途径中，则前进到这个新的位置，然后继续。 如果一个给定的选择通向了死胡同 ，则回到前面的位置，进行其他的选择。
回溯就是通过一系列位置选择到达目的位置，并且在不能到达目的位置时反向退回的策略。

通俗的讲法：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

算法书上可能这样说：回溯法是在包含问题的所有解的解空间树(或森林)中，按照深度优先的策略，从根结点出发搜索解空间树。 算法搜索至解空间树的任一结点时，总是先判断该结点是否满足问题的约束条件。如果满足进入该子树，继续 按照深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。   
  
   
   
     
   

     
   
  
     回溯法在用来求解问题的所有解时，要回溯到根，且根结点的所有可行的子树都已被搜索遍才结束。而回溯法在用来求解问题的任一解时，只要搜索到问题的一个解就可以结束。适用于解决一些最优化问题。

二. 算法设计过程  (1) 确定问题的解空间   
应用回溯法解决问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个最优解。  (2) 确定结点的扩展规则
约束条件。  (3) 搜索解空间
    回溯算法从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应该往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中
搜索，直至找到所要求的解或解空间中已没有活结点时为止。  三. 算法框架
(1) 问题框架   设问题的解是一个n维向量(a1,a2,...,an),约束条件是ai(i=1,2,...,n)之间满足某种条件，记为f(ai)。  (2) 非递归回溯框架
int a[n], i;
i=1;
while(i>0(有路可走) and [未达到目标]){ //还未回溯到头
   if(i>n){ //搜索到叶结点
     搜索到一个解，输出；
   }else{
    a第一个可能的值；
    while(a不满足约束条件且在搜索空间内)
     a下一可能的值；
     if(a在搜索空间内){
      标识占用的资源；
       i = i+1; //扩展下一个结点
    }else{
      清理所占的状态空间；
      i = i-1; //回溯
    }
  }
}  (3)递归算法框架
int a[n];
try(int i){
    if(i>n){
       输出结果；
   }else{
      for(j=下界; j<=上界; j++){//枚举i所有可能的路径
        if(f(j)){ //满足限界函数和约束条件
           a = j;
           ... //其他操作
          try(i+1);
           a = 0; //回溯前的清理工作(如a置空)
        }
      }
    }
}

四、例
1. 问题描述： 输出自然数1到n的所有不重复的排列，即n的全排列。  2. 问题分析：
(1) 解空间： n的全排列是一组n元一维向量(x1, x2, x3, ... , xn),搜索空间是：1<=xi<=n i=1,2,3,...,n

(2) 约束条件： xi互不相同。技巧：采用"数组记录状态信息", 设置n个元素的一维数组d，其中的n个元素用来记录数据
1~n的使用情况，已使用置1，未使用置0  3. java代码：

1. 
   
2. /**  
   
3. * 回溯法  
   
4. *   
   
5. * @since jdk1.6  
   
6. * @author 毛正吉  
   
7. * @version 1.0  
   
8. * @date 2010.05.25  
   
9. *   
   
10. */  
    
11. public class NAllArrangement {   
    
12.     private int count = 0; // 解数量   
    
13.     private int n; // 输入数据n   
    
14.     private int[] a; // 解向量   
    
15.     private int[] d; // 解状态   
    
16.   
    
17.     /**  
    
18.      * @param args  
    
19.      */  
    
20.     public static void main(String[] args) {   
    
21.         //测试例子   
    
22.         NAllArrangement na = new NAllArrangement(5, 100);   
    
23.         na.tryArrangement(1);   
    
24.   
    
25.     }   
    
26.   
    
27.     public NAllArrangement(int _n, int maxNSize) {   
    
28.         n = _n;   
    
29.         a = new int[maxNSize];   
    
30.         d = new int[maxNSize];   
    
31.     }   
    
32.   
    
33.     /**  
    
34.      * 处理方法  
    
35.      *   
    
36.      * @param k  
    
37.      */  
    
38.     public void tryArrangement(int k) {   
    
39.         for (int j = 1; j <= n; j++) { // 搜索解空间   
    
40.             if (d[j] == 0) {   
    
41.                 a[k] = j;   
    
42.                 d[j] = 1;   
    
43.             } else { // 表明j已用过   
    
44.                 continue;   
    
45.             }   
    
46.   
    
47.             if (k < n) { // 没搜索到底   
    
48.                 tryArrangement(k + 1);   
    
49.             } else {   
    
50.                 count++;   
    
51.                 output(); // 输出解向量   
    
52.             }   
    
53.             d[a[k]] = 0; // 回溯   
    
54.         }   
    
55.     }   
    
56.   
    
57.     /**  
    
58.      * 输出解向量  
    
59.      */  
    
60.     private void output() {   
    
61.         System.out.println("count = " + count);   
    
62.         for (int j = 1; j <= n; j++) {   
    
63.             System.out.print(a[j] + " ");   
    
64.         }   
    
65.         System.out.println("");   
    
66.     }   
    
67.   
    
68. }  
    

复制代码

运行结果：
C:java>java NAllArrangement
count = 1
1 2 3 4 5
count = 2
1 2 3 5 4
count = 3
1 2 4 3 5
count = 4
1 2 4 5 3
count = 5
1 2 5 3 4
count = 6
1 2 5 4 3
count = 7
1 3 2 4 5
count = 8
1 3 2 5 4
count = 9
1 3 4 2 5
。。。。。。。。

未完，下一篇：【回溯法】 组合问题


  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/27/000517500.zip