[数据结构与算法]算法竞赛入门到进阶 读书笔记（2）

一、递归
递归是将大问题逐步缩小为最小的同类问题的过程，即n->n-1…->1,一个递归函数直接调用自己就实现了程序的复用。
全排列：
1.用stl输出全排列
next_peimutation()可以不断生成下一个排列，通常由sort排序得到最小序列后不断用next_permutation()生成下一个字典序更大的排列

sort(a,a+4);
do{  for(i=0;i<4;i++)
{ cout<<a[i]<<" ";
cout<<endl;
} while(next_permutation(a,a+4));

2.递归求全排列
全排列个数就是n！，通过1,2,3…n数字之间的不断交换生成不同排列

int digui(int begin,int end){
if(begin==end)
m++;
else { for(i=begin;i<=end;i++)
{ swap(d[begin],d[i]);
 digui(begin+1,end);
 swap(d[begin],d[i]);}
 }
 }

通过递归依次交换数字产生的每一种分选择都会走向begin==end，记录下总的选择数，即n！。当总数和排列数不同时，其实不难发现，在else中每交换一次，下一次递归begin就加一。所以if中的条件其实就是求排列的数字数，比如说打印10个数中任意三个数的排列，只要让begin ==3就可以计算出一种三个数排列的情况，因此只要修改end即可。
二、子集生成
子集内部的元素是没有顺序的，因此不能当成全排列来做，但是通过书上的讲解，使用二进制进行对照十分方便理解。
将每个子集对应一个二进制数，1对应子集中的某个元素，例如{0，1，2}中的{2}对应的二进制码是100，{1，2}是110，存在一个元素即对应一个1。
组合：
打印所有子集，通过二进制可知子集的数量是2的n次方，用i的循环依次检索0-1<<n范围的二进制码和0-n的j的循环，通过位与判断，存在1则说明有元素重合，将j打印出来即是所有子集。

void zuhe(int n){
for(int i=0;i<(1<<n);i++)
{ for(j=0;j<n;j++)
{ if(i&(1<<j)) cout<<j<<" ";
cout<<endl;}
}
}

当n总数和需要组合的数m不同时，可以使用

k=k&(k-1);

它能够依次消除二进制中的1，通过这个操作即可判断二进制循环i中满足组合数m的情况，然后判断输出子集。

三、广度优先搜索
搜索分为广度优先搜索和深度优先搜索。广度优先搜索即将每层完全探索完后开始探索下一层，但是编译器是单机顺序运行，因此每一层并行计算其实也有顺序。广度优先搜索大多和队列挂钩。
1.hdu 1312 红黑砖块问题
计算能走过的所有砖块数即可用广度优先搜索，将左上右下作为行走方向依次进队和出队，计算所有可走砖块数量。

while(!q.empty())  //经过队列的循环可以检索所有搜索情况
{ start=q.front();
q.pop();
for(i=0;i<4;i++)
{ next.x=start.x+dir[i][0];
  next.y=start.y+dir[i][1];
  //判断next是否在所给范围和可走范围中
  //进队后表示已经走过，不能再走
  num++;
  q.push(next);
  }

2、八数码问题(状态图搜索)
搜索的情况不仅可以看成是数，也可以整体看作一个状态。给出一个三乘三的棋盘，要求求出将初始棋局移动到目标棋局的最小移动数。
广度优先搜索很适合处理最短路程问题，但是搜索状态需要进行对相同状态的去重，即用到康托函数。
康托函数可以计算出一组数所有排列方式的康托值，康托值即给定排列方式在全排列中是第几大排列，计算方法为从首位开始依次计算所有首位小于给定排列方式的排列数。
计算公式为X=a[n]*(n-1)!+a[n-1] *(n-2)!+…+a[2]*1!+a[1]*0！。
a[i]表示原数的第i位在当前未出现的元素中排在第几个

bool Cantor(int str[],int n) //康托函数，str【】为给定的状态
{ long result=0;
 for(int i=0;i<n;i++)
 { int counted=0;
  for(int j=i+1;j<n;j++){
  if(str[i]>str[j])   //判断当前未出现的元素排在第几个，即公式中的a[i]
   ++counted;}
   result+=counted*factory[n-i-1];
   }
   if(!visited[result]){
    visited[result]=1; //如果未重复则记下其使用过，然后使函数返回值为1，即可继续搜索。
    result 1;
    }
    else 
    return 0;
    }

有了判断是否重合的康托函数后即可大大减少复杂度，然后按照红黑砖块的方法依次往下进行广度优先搜索即可。
3 .A * 算法
在求解最短路径问题时往往并不需要像红黑砖块一样进行全面的广度优先搜索，A*算法即BFS+贪心算法。根据曼哈顿距离两点之间最短距离即其实际距离（横坐标距离和纵坐标距离之和），因此这样就不用搜索全部的点。
4.双向广搜
双向广搜即从初始位置和结束位置同时出发进行广度优先搜索，在需要满足知道起点和终点的情况下，使用双向广搜效率会高很多。
双向广搜同样可以解决八数码问题。