算法复习之回溯

递归，迭代，子集数，排列树

系统性（从根节点开始深度优先搜索）和跳跃性（遇到不满足条件则回溯）

回溯eg：

1、零一背包

2、TSP（travelling salesman problem 旅行商）问题

子集树：叶子节点2^n个 ——01背包

排列数： 叶子节点N!个 ——旅行商

装箱问题，类似01背包，先尽可能装满第一艘船，再把剩下的装进第二艘，属于NP难题

约束条件：∑wc <= C

界限条件：∑wci + c_left_all <= c_max

批处理作业调度：（排列树）

f1, f2

#include
using namespace std;

const int N = 9;
int x[N] =  {1,2,3,4,5,6,7,8,9};
int k[N];

void swap(int& a,int& b){
    int t = a;
    a = b;
    b = t;
}

void dfs(int i){
    if(i == 4){
        for(int a=0;a<4;++a){
            cout< 
将序列存在x[N]里面，用这种方法可以在不使用visit标记数组的情况下实现全排列
 
 
符号三角形问题：一共n(n+1)/2个符号 ，则+ - 都要有（n+1)*n/4个
 
每次都在第一行加一个，然后生成其他行的新增
 
eg： 生成一个（1，7）
 
则会生成（2，6） = （1，7）&（1，6）
 
通式为： 生成一个（1，t) , 则生成(j,t-j+1) = (j-1,t-j+1) & (j-1, t-j+2)
 
剪枝条件为：count > half || t(t-1)/2  - count > half
 
half = n*(n+1)/4
 
 
n皇后问题：第一行开始，每一格都放，放完一个后，进行判定，若是第一行，直接return true，其他行，place(int i){)  新放进来的是第i行，从第一行开始for(int j = 1; j 
判断条件，abs(p[i] - p[j]) == abs(i-j) || p[i] == [j]   return false
 
 
最大团问题：解空间——子集树，每个新加进来的点都与已经在的点直接相连
 
if(cn + n - i > bestn) x[i] = 0; dfs(i+1)  当当前已经有的加上剩余的也无法比当前最大还多时，直接回溯
 
 
图的m着色，有几种着色方案，还是把顶点存在一个依次数组中，若两个点之间直接相连，则a[i][j] = 1,
 
for(int i=0;i 
 
圆排列问题：全排列子集：计算圆心距离在x轴的投影，求哪一个排列最短
 
dist[t] = getDis(t)
 
剪枝：r[1] + dis[t] + r[t] < min 才能继续下一个
 
dist[t] 怎么求：  
 
dist[0] = 0;
r[0] = 0;
int getDis(int t){
    return dist[t-1] + 2*sqrt(r[t-1]*r[t]);
}   
 
上述算法尚有许多改进的余地。例如，象1,2,…,n-1,n和n,n-1, …,2,1这种互为镜像的排列具有相同的圆排列长度，只计算一个就够了，可减少约一半的计算量。另一方面，如果所给的n个圆中有k个圆有相同的半径，则这k个圆产生的k!个完全相同的圆排列，只计算一个就够了。
 
 
电路板排列问题：全排列子集：