算法分析结课总结回溯算法

以下是回溯算法的经典框架结构：
 1 //t：递归的深度，也就是对象的层数。因此每次的回溯遍历都以深度为参数。
 2 void backtrack (int t)        
 3 {
 4     if(t>n)                    //n：对象的总深度，或对象的总层数。
 5         output(x);            //x：解的容器，一般是个数组。
 6     else
 7     {
 8         /*f(t)和g(t)确定t层解的个数，或说第t个位置上解的可选个数。
 9         （1）0-1问题每层都有0和1两个解。（2）n皇后问题每层都有n个解。（3）排列
10         问题第t层有t到n个解。所以排列问题每层解的个数跟t有关。*/
11         for(int i=f(t);i<=g(t);i++)        
12         {
13             x[t]=h(i);            //h(i)：第t层的第i中解，x[t]:记录第t层的解。            
14             
15             /*constrain（t,i）：判断当x[t]取h(i)时，是否有必要继续递归，
16             如：当前x记录的解,继续递归是否有可能比当前最优解更好，如0-1问题；
17             或h(i)是否是一个合法的，即符合规则的解，如n皇后问题；
18             bound(t,i)：判断当x[t]取h(i)时，当前x记录的解是否已超过界限。如0-1问题。*/            
19             if(constrain(t,i) && bound(t,i))                
20                 backtrack(t+1);
21         }
22     }
23 }