《算法分析与设计》笔记整理_算法设计与分析听课笔记

一：分治法

（1）全排列问题

问题：打印出给定的n个字符的全排列。
思想：递归，将问题转化为前缀+n-1个字符的全排列
Notations:
list[]：一定顺序的n个字符字符串
k：当前前缀设置位置k号
m：字符总数量

void Perm(list[],int k,int m)
{
	if(k ==m)
	{
	  for(int i=0;i<m;i++)
	  cout<<list[i]<<' ';
	  cout<<endl;
	}
	for(int i=k;i<m;i++)
	{
	  swap(list[k],list[i]);  //设置k号确定字符
	  /*如何设置前缀？
	  从0号位置向后设置，可用字符为当前位置与后面位置字符
	  */
	  Perm(list,k+1,m);
	  swap(list[k],list[i]);  //还原k号字符与串初始顺序 循环设置新字符
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度 T(n)=n(c1+c2+T(n-1))=nT(n-1)+(c1+c2)n

（1.2）Hanoi塔问题

问题：a,b,c三个塔座，开始时，在塔座a上有一叠共N个的圆盘，自下而上从大到小叠放在一起，编号1，2，…，n。现要求将a上的一叠圆盘移到塔座b。
思想：将问题转化为将上面n-1个盘子移到c，把n号盘子移到b。再将c号的n-1个盘子按照相同的方法移到b。
Notations:
n:num.盘子
a,b,c：三个塔座

void Hanoi(int n,int a,int b,int c)
{
 	if(n >0){
 	Hanoi(n-1,a,c,b);  //将1-n-1号盘子从a-->c
 	Move(a,b); 
 	Hanoi(n-1,c,b,a);  //将1-n号盘子从c-->b
}
1
2
3
4
5
6
7

时间复杂度：T(n)=2T(n-1)+C=2(2T(n-2)+C)+C=O(2^n)

（2）整数划分问题

问题：将正整数n表示成一系列正整数之和，n=n1+n2+…+n_k(n1>=n2>=n3…>=nk)。这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记为p(n)。例如p(6)=11

6=5+1=4+2=4+1+1=3+3=3+2+1=3+1+1+1=2+2+2=2+2+1+1=2+1+1+1+1=1+1+1+1+1+1
思想：设q(n,m)为数字m对n的拆分数。当n=1,m=1时，q(1,1)=1。当n=m时，q(n,m)=q(n,m-1)+1。当n>m时，q(n,m)=q(n,m-1)+q(n-m,m)即下一拆分项与拆分后的新项。当n<m时，q(n,m)=q(n,n)。

代码

int q(int n,int m)
{
 	if((n==1)&&(m==1)) return 1;
 	else if(n >m) return q(n,m-1)+q(n-m,m);
 	else if(n ==m) return q(n,m-1)+1;
 	else return q(n,n);
}
1
2
3
4
5
6
7

（3）大整数乘法问题

问题描述：设X和Y都是n位二进整数，现在要计算它们的乘积，设计效率较高的方案。

（4）棋盘覆盖问题

问题描述：

输入：n*n棋盘大小，x,y特殊点大小
输出：棋盘覆盖格式
约束条件：只能使用4种L进行摆放填充
思路：将2^k * 2^k的棋盘分割为 4个2^k-1 * 2^k-1子棋盘，特殊方格必位于4个棋盘之一。用一个L型方格覆盖其他三个棋盘，从而将原问题转化为4个较小棋盘的棋盘覆盖问题

Notations:
tr:左上角方格行数
tc:左上角方格列数
dr:特殊点所在行
dc:特殊点所在列

/*
同思路中的L型填充不同，实际的代码过程是从左至右依次处理较小方格。
*/
void cheessBord(int tr,int tc,int dr,int dc,int size)
{
	if(size ==1) return;
	int t =title++;
	size /=2;
	if((dr<tr+s)&&(dc<tc+s)) //特殊点左上角
		chessBord(tr,tc,dr,dc,size);  //进入递归
	else  { //特殊点不在左上角 则L覆盖后再递归
		borad[tr+s-1][tc+s-1] =t;
		chessBord(tr,tc,tr+s-1,tc+s-1);
	}
	else if((dr<tr+s)&&(dc>=tc+s))  //特殊点在右上角
		chessBord(tr,tc+s,dr,dc,size); //进入递归
	else { //特殊点不在右上角 L覆盖后在递归
		board[tr+s-1][tc+s] =t;
		chessBord(tr,tc+s,tr+s-1,tr+s,size);
	}
	else if((dr>=tr+s)&&(dc<tc+s))  //特殊点在左下角
		chessBord(tr+s,tc,dr,dc,size); //进入递归
	else { //特殊点不在左下角 L覆盖后在递归
		board[tr+s][tc+s-1] =t;
		chessBord(tr+s,tc,tr+s,tr+s,size);
	}
	else if((dr>=tr+s)&&(dc>=tc+s))  //特殊点在右下角
		chessBord(tr+s,tc+s,dr,dc,size); //进入递归
	else { //特殊点不在右下角 L覆盖后在递归
		board[tr+s][tc+s] =t;
		chessBord(tr+s,tc+s,tr+s,tr+s,size);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

（5）合并排序

基本思想：将待排序的元素分成大小大致相同的两个子集合，分别对两个子集合进行排序。最终将排好序的子集合合并成要求的排序好的集合

void mergeSort(vector<int> &vec,int left,int right)
{
	int mid =(left+right)/2;
	mergeSort(vec,left,mid);      //左集合
	mergeSort(vec,mid+1,right);   //右集合
	merge(vec,left,mid,right);
}
void merge(vector<int>& vec,int left,int mid,int right)
{
	vector<int> temp;  //临时保存当前排好序的元素
	int i =left,j =mid+1;
	while((i<=mid)&&(j<=right)) {
		if(vec[i] <vec[j]) 
		temp.push_back(vec[i++]);
		else temp.push_back(vec[j++]);
	}  //按照升序将左右子集元素放在临时向量vec
	while(i<=mid) temp.push_back(vec[i++]);
	while(j<=right) temp.push_back(vec[j++]); //不等长元素加入temp
	for(int k=0;k<temp.size();k++)
		vec[k+left] =temp[k];   //temp[k]-->vec[left+k]实际位置修改
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：

（6）快速排序

基本思想：对于输入的子数组a[p:r]，按以下三个步骤进行排序
①分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q],a[q+1:r]，使a[p:q-1]中任意一个元素小于a[q]，而a[q+1:r]中任意一个元素大于a[q]
②递归求解：分别对a[p:q-1]和q[q+1:r]进行排序
③合并：a[p:q-1],a[q+1:r]排好序后,a[p:r]已经排好序

Model:

void quickSort(int a[],int p,int r)
{
	if(p <r) {
		int j =Partition(a,p,r);  //思想中的划分q
		quickSort(a,p,j-1);
		quickSort(a,j+1,r);
	}
}
int Partition(int a[].int p,int r)
{
	int x =a[p];   //a[p]作为基准值
	int i =p,j= r+1;
	while(1) {
		while((a[++i]<x)&&(i <r)); //左哨兵找大于x的点
		while(a[--j]>x);  //右哨兵找小于x的点
//找到各自点后 判断i<j? 若不成立则证明左右子数组已满足性质 退出循环
		swap(a[i],a[j]);		
	}
	a[p] =a[j];    //!!!
	a[j] =x;
	return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

上述代码是以左侧第一个元素作为基准值，而快速排序算法的性能取决于划分的对称性，因此可以使用随机选取基准点的方式，减少最坏情况的可能

int randomPartition(int a[],int p,int r)
{
	int i =rand()/(double)RAND_MAX *((right-left)+left);
	swap(a[i],a[p]);
	return Partition(a,p,r);
}
1
2
3
4
5
6

时间复杂度：
最好时间复杂度:O(nlogn)
最差时间复杂度:O(n^2)

（7）循环赛日程表

问题描述：
设计一个满足以下条件的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次
（2）每个选手一天只能赛一次
（3）循环赛一共进行n-1天
思路：将选手分为两半，n个选手的日程表可以通过过两组n/2个选手的日程表确定。递归使用这种一分为二的策略对选手分割。当仅剩下2个选手时，就容易安排比赛
步骤：
（1）初始化第一行
1 2 3 4 n=4
（2）使用第一行交叉填充第二行
1 2 3 4
2 1 4 3 {第一部分n=2}
（3）使用第一部分填充第二部分
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1 {第二部分n=1}

（8）最接近点对问题

一维情形：

（1）思路
①基于平衡子问题思想，选取中位数作为分割点，将S划分为S1,S2两个子集
②递归在S1,S2求解得到最接近点对(p1,q1),(p2,q2)，其中p3∈S1,q3∈S2的点对(p3,q3)也可能构成最接近点对
③p3,q3分别是S1,S2的最大和最小值，可以在线性时间内查找得到两值

二维情形：

输入：二维平面上n个点的集合
输出：距离最近的两个点
（1）思路：
①选取x=m,m为所有点x坐标的中位数把S分割为S1和S2
②递归的在S1,S2找到最接近点对(p1,q1),(p2,q2)，其中p3∈S1,q3∈S2的点对(p3,q3)也可能构成最接近点对，如何在线性时间查找p3,q3呢？

二：动态规划

（8）0-1背包问题

问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大。
输入：C>0 wi>0 vi>0 1<=i<=n
输出：(x1,x2,…,xn) (xi=0 or 1)
约束条件：ΣwixI <=C Max{ Σvixi }
①求什么设什么：从物品i到物品n选择装入容量为j的背包，背包内物品的总价值t(i,j)。
②分析证明重叠子问题：从物品i到物品n选择装入容量为j的背包。当wi>j时，总价值与t(i-1,j)相同。当wi<=j时，t(i,j)应该为选择i物品后选择(i+1)~ n物品装入容量为j-wi的包与选择i+1~n装入容量为j的包的最大值。从上到下分析，容易得出存在重叠子问题。
③证明最优子结构：假设t(i,j)是容量为j选择物品为i,i+1…n的最优解。其子问题①wi>j时 容量为j选择物品为i+1,i+2…n ②wi<=j时 容量为j-wi选择物品为i+1…n 与 容量为j选择物品为i+1,i+2…n。假设子问题非最优解，则①时最优解应该大于t(i+1,j) ②时最优解应该大于t(i+1,j-wi)。此时i~n个物品的最优解>t(i,j)，结果矛盾。
④递推公式：
t(i,j) =t(i+1,j) wi>j
=t(i+1,j-wi)+vi wi<=j

Note: 下面所述代码中,v[n+1],w[n+1] 第一位均存0.
m[n+1][c+1]的第一排(0)与第一列全0

void Knapsack(int v[],int w[],int c,int n,int **m)
{
//自底向上运算，【1】仅一个物品时：若j<wi时填充为0
   int jmax =min(c,w[n]-1);
   for(int i=0;i<=jmax;i++)
   m[n][i] =0;
//【1】若j>wi时 填充此物品价值
   for(int i=w[n];i<=c;i++)
   m[n][i] =v[n];
//【2】递推公式 自底向上运算
   for(int i=n-1;i>1;i--) { //第二排(1)仅考虑m(1,n)
   jmax =min(c,w[i]-1);
   //1.wi >j时
   for(int j=0;j<=jmax;j++)
   m[i][j] =m[i+1][j];
   //2.wi <j时
   for(int j=w[i];j<=c;j++)
   m[i][j] =max(m[i+1][j],m[i+1][j-w[i] ]+v[i]);
   }
//【3】单独算m(1,c)
   m[1][c] =m[2][c]; //初始化
   if(c >=w[1])
   m[1][c] =max(m[1][c],m[2][c-w[1] ]+v[1]);
}
//最优解回溯算法Traceback()
void Traceback(int **m,int w[],int c,int n,int x)
{
   for(int i=1;i<n;i++) {
   if(m[i][c] ==m[i+1][c]) 
   x[i] =0;
   else {
   x[i] =1;
   c -=w[i];
   }
   }
   if(m[n][c]) x[n] =1;
   else x[n] =0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间复杂度：
Knapsack()： T(n)=O(m*n) m为最大容量
Traceback(): T(n)=O(n)

（9）背包问题

问题描述：设有n个物体和一个背包，物体i的重量为wi，价值为vi，背包的容量为c。若将物体i的xi部分(1<=i<=n,0<=xi<=1)装入背包。则具有价值为vi,xi。目标是找到一个方案。使放入背包的物体总价值最高。
输入：c >0, n >0, wi >0, vi >0
输出：{x1,x2,…,xn} (0<=xi<=1)
约束条件：ΣwixI <=C Max{ Σvixi }
①分析最优策略：若把物品按照总价值从大到小装入背包，可能因为重量过高而出错。若把物品按重量从小到大装入背包，若价值较少也可能出错。若把物体按照单位体积从大到小装入背包，好像符合题意。
②证明最优子结构性质（反证法）：设A使容量为C的最大价值物品的集合。若j是集合A中的物品，从A中取出j，得到A’是容量为C的物品的集合。假设B’是去除j物品的最大价值物品集合，且|B’|>|A’|. B =B’+j |B|>|A|矛盾。
③证明最优策略（归纳法）：

Note:
vector< int >value,weight;
vector< float >x;
value:物品i的全职(n+1)
weight:物品i的重量(n+1)
x:物品i装入背包的比例(n+1)

bool cmp(int left,int right)
{//计算单位重量价值 并按照升序排列
   l =value[left]*1.0/weight[left];
   r =value[right]*1.0/weight[right];
   return l>r;
}
//value weight x为全局变量且在主函数中通过resize(n+1)进行了初始化
void Knapsack(int n,int c)
{
//[1]对物品按照单位重量价值排序
   sort(weight.begin()+1,weight.end(),cmp);
//weight[0]为无意义元素 不需要进行排序
//[2]贪心策略  循环装入背包
   int i =0;
   for(i=1;i<=n;i++)
   {
//weight按照单位重量价值按降序排序，最优解是将尽可能多的单位价值高的物品加入背包
       if(weight[i] >c)
       break;
//当较高单位重量价值的物品无法完全放入时 退出循环 并加入该物品的部分于背包
       x[i] =1;
       c -=weight[i];
   }
   if(i <=n)
   x[i] =c*1.0/weight[i];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

（10）最大子段和

问题描述：给定长度为n的整数序列a[1…n]，求[1,n]某个子区间[i,j]使得a[i]+…a[j]和最大。
输入：a[n]长度为n的序列
输出：最大子段和b[j]
约束条件：给定曲间某最大的字段和
思路：（1）枚举法 求给定序列的最大字段和可以枚举曲间内所有子区间和并取最大值即得解。但枚举法得时间复杂度为O(n^2) （2）分治法：将序列分为左右两个子段，最大子段和则存在三种情况 1：在左子序列 2：在右子序列 3：开始侧在左子序列，结束侧在右子序列。 1 2两种情况可以递归考虑。对于情况3：a[n/2]与a[n/2+1]一定在3序列中，只需求得[1,a[n/2]]得最大字段和s1和[a[n/2+1],n]得最大子段和s2。s=s1+s2即为第三种情况下的最大子段和。此时时间复杂度为O(nlogn) （3）动态规划算法：使用第二种算法考虑中间状态时，每层递归中都包含有重复计算的重叠子问题（重叠子问题性质），同时设b[j]是以j结尾得子段得最大字段和。则当b[j]>0时，b[j+1]=b[j]+a[j]。
（0）求什么，设什么： 设以第j个元素结尾得最大子段和为b[j]。分析可知b[j]与b[j-1]相关。
（1）重叠子问题性质：设b[j]=max{a[i]+a[i+1]+…a[j]} b[j-1]=max{a[i]+a[i+1]+…a[j-1]}。上述问题描述中存在重叠得计算过程。
（2）最优子结构性质：设b[j]是以j结尾得最大子段和，当b[j-1]>0时，b[j]=b[j-1]+a[j]。设B’是以j-1结尾得最大子段和(B’>b[j-1])，则B=B’+a[j]>b[j]矛盾。
（3）递推公式：
b[j] =b[j-1]+a[j] (b[j-1]>0)
b[j] =a[j] (b[j-1]<=0)

Notations:
sum:子段和
a[n+1]:n个元素构成的序列

int sumMax(int n,int a[])
{
	int sum =0;
	for(int i=1;i<=n;i++) {
	if(sum <0) 
		sum =a[i];   //不会更小  s[i]=a[i]
	else {
	sum =sum+a[i];  //正增长 s[i]=,s[i-1]+a[i]
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11

（11）最长公共子序列

问题描述：给定2个序列X={x1,x2…,xm},Y={y1,y2…,yn}。找出X和Y的最长公共子序列
输入：X={x1,x2…,xm},Y={y1,y2…,yn}
输出：Z =X和Y的最长公共子序列
约束：
思路：Xi={x1,x2…,xi}(i=1,2,…,m)，Yj={y1,y2,…,yj}(j=1,2,…,n) 分别是X,Y以xi和yj结尾的连续子段。分别求得Xi在j=(1,2,…,n)所有子段中的公共子序列长度。当xi=yj时，字段长度=1+Xi-1和Yj-1的公共子序列长度。当xi!=yj时，则需继承之前存在的公共子序列长度即Xi和Yj-1或Xi-1和Yj。
①求什么，设什么：求X=m和Y=n的序列的公共子序列长度，则设t[i][j]是长度为i,j的序列X’,Y’的公共子序列长度。
②重叠子问题性质：根据思路分析求解t[i][j]可能会用到t[i-1][j-1]、t[i][j-1]、t[i-1][j]，满足重叠子问题性质。
③最优子结构：将问题转换成如上子问题，即当x[i]=Y[j]时 t[i][j]=t[i-1][j-1]+1 否则t[i][j]=max(t[i][j-1],t[i-1][j])。设t[i][j]是X,Y的最优解，若Xi-1Yj-1的最优解为T’>t[i-1][j-1]则T=T’+1>t[i][j] 矛盾。
④递推公式：
t[i][j] =t[i-1][j-1]+1 X[i]=Y[i]
=max(t[i-1][j],t[i][j-1)

Notations:
X,Y:求解的两个序列
t[i][j]：以X[i]和Y[j]结尾的X’,Y’子序列的最长公共子序列长度

 void LCSlength(string x,string y,vector<vector<int> >&a,vector<vector<int> >&b)
{
	//初始化第一行和第一列为0
	int n =x.size(),m =y.size();
	for(int i=0;i<=n;i++) a[i][0] =0;
	for(int j=0;j<=m;j++) a[0][j] =0;
/*Note:递推公式 自底向上运算。 字符串的索引从0~size-1，因此数组索引时需要些许改动 不能直接1对1填写   x的第i个字符和y的第j对应a[i+1][j+1]
*/
	for(int i=1;i<n;i++) {
	for(int j=1;j<m;j++) {
	//x[i]=y[j]情况下 
	if(x[i] ==y[j]) {
		a[i+1][j+1] =a[i][j]+1;
		b[i+1][j+1] =1;    //斜上方
	}
	else {
		if(a[i][j+1] >a[i+1][j]) {
			a[i+1][j+1] =a[i][j+1];
			b[i+1][j+1] =2;  //上侧
		}
		else {
			a[i+1][j+1] =a[i+1][j];
			b[i+1][j+1] =3;  //左侧
		}
	}
}
void LCS(vector<vector<int> >&b,string x,int i,int j)
{
	if(b[i][j] ==1) {
	LCS(b,x,i-1,j-1);
	cout<<x[i];
	}
	else if(b[i][j] ==2)
	LCS(b,x,i-1,j);
	else if(b[i][j] ==3)
	LCS(b,x,i,j-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

（12）矩阵连乘问题

问题描述：给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序，使得次序计算的矩阵连乘需要的次数最少。
输入：p[n],(Ai=x*y,p[i-1]=x,p[i]=y)
输出：使得矩阵连乘次数最少的最优次序
约束条件：Ai与Ai+1可乘
递推公式：

步骤：初始化–>自底向上按照递推公式计算并记录最优截断位置

void matrixChanin(vector<int> p,vector<vector<int> >m,vector<vector<int> >s,int n)
{
	//初始化,m[i][i]=0
	for(int i=1;i<=n;i++)
	m[i][i] =0;
	//自底向上运算
	for(int r=2;r<=n;r++) //从第二列开始
	{
		for(int i=1;i<=n-r+1;i++)  //对角线排列的行数限制1-n 2-n-1 3-n-2
		{
			 int j =i+(r-1);       //当前行所对应列(i,j)
			 m[i][j] =m[i+1][j]+p[i-1]*p[i]*p[j];  //初始化m[i][j]
			 for(k=i+1;k<j;k++) {
			 	int tmp =m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
			 	if(tmp <m[i][j]) {
			 		m[i][j] =tmp;
			 		s[i][j] =k;   //截断位置更新
			 	}
			 }
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度：T(n)=O(n^3)

三：贪心算法

（13）最优编码树问题

问题描述：给定下列符号集以及它们在文档中出现的频率， 为这些符号设计二进制码，以便将文档的尺寸压缩至最小。
输入：字母表C={c1,c2,…,cn} 频率表F={f(c1),f(c2),…,f(c3)}
输出：具有最小B(T)的C前缀编码树
贪心思想：循环选择具有最低频率的两个结点生成一颗子树直至生成一棵树

template<class Type>
class Huffman
{
friend BinaryTree<int> HuffmanTree(Type [],int);
public:
	operator Type()const {return weight;} //排序需要
private:
	BinaryTree<int> tree;
	Type weight;
};

BinaryTree<int> HuffmanTree(Type f[],int n)
{
	//1.初始化节点向量  weight and tree
	Huffman<Type>* w =new Huffman<Type> [n+1];
	BinaryTree<int> z,zero;
	for(int i=1;i<=n;i++)
	{
		 w[i].weight =f[i];  //weight
		 z.MakeTree(i,zero,zero); //tree initialize
		 w[i].tree =z;
	}
	//2.生成优先队列（最小堆）
	MinHeap<Huffman> Q(1);  //按照()排序
	Q,Initialize(w,n,n);
	//3.删除最小的两个节点生成新的节点直至仅剩最后一个节点
	for(int i=1;i<n;i++) {
		Q.DeleteMin(x);
		Q.DeleteMin(y); //删除最小的两个节点
		z.MakeTree(0,x.tree,y.tree);
		x.weight +=y.weight;
		x.tree =z;
		Q.Insert(x);   //合并后插入
	}
	Q.DeleteMin(x);   //最小节点 根节点
	Q.Deactivate();
	delete []w;
	return x.tree;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

（14）最小生成树问题

问题描述：设G(V,E)是一个无向连通带权图，E中每条边(v,w)的权为c[v][w]，若G的一个子图G’是一颗包含G所有顶点且各边权和最小的生成树，则称G’是G的最小生成树。且G的最小生成树

输入：无向连通带权图邻接矩阵a[v+1][v+1]
输出：最小生成树（使各边权和最小的生成树）
MST性质：如果(u,v)∈E,且u∈U,v∈V-U,且a[u][v]的权最小，则一定存在G的一个最小生成树，它以(u,v)为其中一条边
贪心策略：（1）Prim算法：每次寻找下一个距MST任意顶点最近的顶点加入MST并对其展开松弛，直到所有顶点加入MST为止
（2）Kruskal算法：先按边权从小到大排序，然后递增顺序查看每一条边。若边的两个顶点不属于同一连通分支则合并

问题（1）Prim和Kruskal算法的异同
同：①都用于求解最小生成树问题。②都采取了贪心策略
异：①思路不同，prim每次寻找下一个距MST任意顶点最近的顶点，加入MST并对其展开松弛直到所有顶点加入MST。Kruskal先按边权从小到大排序，然后按递增顺序访问每一条边。若边的两个顶点不属于同一连通分支则合并。②时间复杂度不同：Prim算法时间复杂度为O(n^2)，Kruskal算法时间复杂度为O(eloge)

Notations:
lowcost[i]:i顶点距离最小生成树的最短距离
closeset[i]:i顶点与最小生成树连接的顶点
s[i]:i顶点是否加入MST

#define inf 999999
void Prim(int n,int **a)
{
//步骤：初始化-->最近邻点-->松弛
	int lowcost[n+1],closeset[n+1],s[n+1];
	//1.初始化
	s[1] =1;
	for(int i=2;i<=n;i++)
	{
		lowcost[i] =a[1][i];   //d[i]
		closeset[i] =1;
		s[i] =0; 
	}
	//2.找最近邻点+松弛循环(没有被访问且min distance)
	for(int i=1;i<=n;i++)  //循环执行N次  直到所有顶点加入MST
	{
		int Min =inf;
		int node =1;
		for(int j=2;j<=n;j++) {
			if((lowcost[j] <Min)&&(!s[i])) //未访问且较近 {
				Min =lowcost[j];  //更新
				node =j;  //更新
			}
		}
		s[node] =1;
		cout<<node<<' '<<lowcost[node]<<endl;  //index distance
		//3.松弛
		for(int j=2;j<=n;j++) {  //最紧邻点是与MST的任意节点
			if((a[node][j] <lowcost[j])&&(!s[j]))  //更新的原则：未加入且与node距离小于之前MST距离
			{
				lowcost[j] =a[node][j];
				closeset[j] =node; 
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度 T(n) =O(n^2)
Notations:
E[ ]:无向连接图的初始边关系
t[ ]:MST内存在的边

template<class Type>
class EdgeNode
{
	friend ostream& operator<<(ostream&,EdgeNode<Type>);
	friend bool Kruskal(int,int,EdgeNode<Type>*,EdgeNode<Type>*);
	friend void main(void);
public:
	operator Type()const {return weight;}
private:
	Type weight;
	int u,v;
};

template<class Type>
bool Kruskal(int n,int e,EdgeNode<Type> E[],EdgeNode<Type> t[])
{
//排序-->按升序访问节点 判断是否属于同一连通分支 合并
//采用最小堆和并查集实现 访问和合并查找功能
	MinHeap<EdgeNode<Type> >H(1);
	H.Initialize(E,e,e);
	UnionFind U(n);
	int k =0;  //MST内节点个数
//删去最短的边 判断两节点是否属于同一连通分支 若不属于则合并
	while(e&&k<n-1) //e>0 且剩下一个连通分支故执行n-1次
	{
		//1.删去最短边
		EdgeNode<Type> x;
		H.DeleteMin(x);
		//2.判断两节点是否属于同一连通分支
		int a =U.Find(x.u);
		int b =U.Find(x.v);
		if(a!=b)  { //不属于
			t[k++] =x;  //添加此边进入MST
			U.Union(a,b);  //合并-->属于相同连通分支
		} 
	}
	H.Deactivate();
	return (k==n-1);   //k=n-1时 表示MST构造完成(边数)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度：T(n) =O(eloge)

（15）最短路径问题

问题描述：给定带权有向图G=(V,E)，其中每条边的权是一个非负实数。要计算从V的一点v0到所有其他各顶点的最短路长度。
Modle:
从源到u的特殊路径：设u是G的某一个顶点，从源u且中间只经过S中顶点的路。
（1）贪心选择策略：从V-S中选择具有最短特殊路径的顶点u,从而确定从源到u的最短路径长度dist[u]。 问题：为什么不存在从源到u且长度比dist[u]更短的路？ 设x为初次走出S之外到达的顶点，并徘徊S内外多次，最后离开s到达u.
dist[x]<=d(s,x),d(s,x)+d(x,u)=d(s,u)<dist[u] --> dist[x]<dist[u]与u是具有最短特殊路径的条件相矛盾
（2）最优子结构性质
算法步骤：初始化–>找最近邻点(最短特殊路径)–>松弛(循环至所有顶点加入S)

void Dijkstra(vector<int> d,vector<int> prev,vector<vector<int> >c,int n,int v)
{
//初始化-->找最近邻点-->松弛
/*
d.resize(n+1)
c.resize(n+1);
for() {c[i].resize(n+1)}
*/
	bool s[n+1];
	//1.初始化
	for(int i=1;i<=n;i++) {
		s[i] =false; //未被访问
		d[i] =c[v][i];  //特殊路径距离
		if(d[i] ==inf) prev[i] =0;
		else prev[i] =v;  //前驱顶点
	}
	s[v] =true; d[v] =0;
	//2.寻找最近邻顶点并加入S
	for(int k=1;k<n;k++) {
		int u =0;
		int tmp =inf;
		for(int i=1;i<=n;i++) {
			if((!s[i])&&(d[i] <tmp)) {  //找到非inf点
				u =i; //记录顶点编号
				tmp =d[i];  //局部最小值
			}
		}
		s[u] =true;  //加入S
		d[u] =tmp;
		//3.松弛
		for(int i=1;i<=n;i++) {
			int tmp =d[u]+c[u][i];
			if((!s[i])&&(tmp <d[i])) {
				d[i] =tmp;
				prev[i] =u;  //修改最近特殊路径距离与前缀顶点
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度： T(n) =O(n^2)
（3）Bellman-Ford算法
dist^1[u] =Edge[v][u]
dist^k[u] =min{ dist^k-1[u],min{ dist^k-1[j]+Edge[j][u] } }

（16）活动安排问题

问题描述：设n个活动的集合E={1,2,…,n}，其中每个活动都要使用同一资源，而同一时间内只有一个活动能使用个这一资源。每个活动使用该资源有起始时间si和结束时间fi，若两区间不相交则称i,j两活动相容。选出最大相容的活动子集合
输入：s[n+1],f[n+1]
输出：S的最大相容集合xi=0,1
约束条件：相容、最大
（1）贪心策略：每次选择fi最小的活动（活动越早结束，就有更多空间选择其他活动）
（2）最优子结构性质：
①活动1包含在某个最优活动选择中
②A’=A-{1}，假设n-1的最优解为B’,B=B’+{1}>A矛盾

Notations:
A[n+1]:选择的活动
s[n+1],f[n+1]:活动i的开始和结束时间

vector<int> s,vector<int> f
bool cmp(int left,int right)
{
	return s[left] <=s[right];
}
void partySelect(vector<int> a,int n)
{
//按结束时间排序-->选择相容的活动
	//1.排序
	sort(s.begin()+1,s.end(),cmp);
	sort(f.begin()+1,f.end(),cmp);
	//2.选择相容的活动
	a[1] =1;
	int j =1;
	for(int i=2;i<=n;i++) {
		if(s[i] >=f[j]) {
			a[i] =1;
			j =i;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度： T(n) =O(nlogn)=O(n)+O(nlogn)

（17）最优装载问题

输入：wi(i=1,2,…,n)
输出：xi(xi=0 or 1)
约束条件：Σwi*xi<=c and max(Σxi)
（1）贪心策略：采用重量轻者先装的贪心选择策略
集装箱按照重量从小到大排序，(x1,x2,…,xn)是最优装载问题的一个最优解。设k=min{i|xi=1}(排序后装载的最小的集装箱的序号)
①k=1时 满足贪心选择性质
②k>1时，取y1=1,yk=0，则Σwiyi=wi-wk+Σwixi(i!=1 k)可知Σyi=Σxi，同样是最优解，因此满足从轻者先装的贪心选择性质
（2）最优子结构性质
设(x1,x2,…,xn)是最优装载问题的满足贪心选择性质的最优解，则x1=1,{x2,x3,…,xn}是重量为c-w1，待装集装箱为{2,3,…,n}时相应的最优解
注意：x1,x2,…,xn只能为0或1，要么不放要么全部放入

vector<int> w;
bool cmp(int left,int right)
{
	return w[left] <w[right];
}
void Load(int x[],int c,int n)
{
//序号按照重量从小到大排序-->增序判断
	vector<int> t(n+1);
	for(int i=1;i<=n;i++)
		t[i] =i;
	//1.序号按照重量从小到大排序
	sort(t.begin()+1,t.end(),cmp); 
	//2.装载判断 t[i]当前最小序号
	for(int i=1;i<=n&&w[[t[i]]]<=c;i++)
	{
	 	x[t[i]] =1;
	 	c -=w[t[i]];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：T(n) =O(nlogn)

四：回溯法

（1）问题的解空间

（2）两种避免无效搜索的策略
约束函数：在扩展节点处剪去不满足约束的子树
限界函数：剪去得不到最优解的子树
（3）回溯法的基本思路
①定义解空间
②确定解空间结构
③深度优先搜索+剪枝
（4）回溯法解题的四种算法框架
①递归法实现回溯法

void backtrace(int t)
{
	if(t >n) output(x); //最底层非扩展节点
	else { //当前扩展节点
		for(int i=f(n,t);i<=g(n,t);i++) {
		//起始到中止范围内，扩展结点所有的可选值h[i]
		x[i] =h[i];
		//深度优先+剪枝
		if(bound(t)&&constraint(t)) 
			backtrace(t+1);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

②采用树的非递归深度优先遍历，迭代法实现回溯

void ibacktrace()
{
	int t =1;  //第一层
	while(t >0) {
		//1.扩展结点判断
		if(f(n,t) <g(n,t)) { 
//扩展节点-->所有可能值-->DFS+剪枝
			for(int i=f(n,t);i<=g(n,t);i++) {
				x[i] =h[i];
				if(bound(t)&&constraint(t)) {
					if(solution(t)) output(x);
					else t++; //非结果 纵深t+1层
				}
			}
		}
		else //非扩展节点，返回t-1层
			t--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

③子集树：从n个元素的集合S中找出满足某种性质的子集时相应的解空间

void backtrace(int t)
{
	if(t >n) output(x);
	else { //扩展节点
	//可选值0 1-->DFS+剪枝
		for(int i=0;i<=1;i++) {
			x[t] =i;
			if(constraint(t)&&bound(t))
				backtrace(t+1);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

④排列树：确定n个元素满足某种性质的排列时相应的解空间树

void backtrace(int t)
{
	if(t >n) output(x);
	else {
		for(int i=t;i<=n;i++) {
			swap(x[t],x[i]); //修改排列 进入t+1层
			if(constraint(t)&&bound(t))
				backtrace(t+1);
			swap(x[t],x[i]);  //返回t-1层
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

（17）装载问题

问题描述：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且Σwi<=c1+c2。装载问题要求确定，是否有一个合理的装载方案可将这n个集装箱装上这2艘船。如果有，找出一种装载方案。
输入：c1,c2(>0), W[n]
输出：x[n] (对某一艘船的装载情况)
先将第一艘船尽可能的装满，然后将剩余的集装箱装上第2艘船。而将第一艘船尽可能装满等价于子集选取问题，使集装箱重量尽可能地接近c1。
（1）定义解空间：x[n]，其中x[i]表示i号集装箱是否加入第1艘船
（2）确定解空间结构：子集树
（3）深度优先+剪枝：
约束条件：cw+w[i] < C1
限界条件：cw+up > bestw

(仅得到一个解）
Model:

class Loading
{
	friend int MaxLoading(vector<int>&,int,int,vector<int>&);
private:
	void backtrace(int i);
	int n;
	vector<int> bestx;
	vector<int> x;
	int bestw;
	int cw;
	int r;			//剩余集装箱的重量  初始化时即-w[i]
};

void Loading::backtrace(int i)
{
	if(i >n){		//叶节点
		if(cw >bestw) {
			bestw = cw;
			for(int i=1;i<=n;i++)
				bestx[i] = x[i];
		}
		return;
	}
	else {			//非叶节点
		//r -= w[i];	//剩余集装箱重量
		//1.左子树约束条件判断
		if(cw+w[i] < c){
			cw +=w[i];
			x[i] = 1;
			backtrace(i+1);
			x[i] = 0;
			cw -=w[i];
		}
		//2.右子树限界条件判断
		if(cw+r >bestw) {
			x[i] = 0;
			bracktrace(i+1);
		}
		//r +=w[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

（18）符号三角形问题

问题描述：在一般情况下，符号三角形第一行有n个符号，对于给定的n，计算有多少个不同的符号三角形，使其所含的’+‘和’-'的个数相同

输入：n(n>0)
输出：解向量x(1:n)(其中+:1,-:0)
约束条件：三角形包含的+个数和-个数相等。n为奇数无解
限界条件：size1 = size0 <=n*(n+1)/4,±号个数不超过总数的一半
解空间：完全二叉树
算法思路：BackTrace(i)表示搜索第i层子树。① 当i>n时，算法搜索到叶节点，得到一个新的+个数和-个数相同的符号三角形，当前找到的符号三角形个数+1.②i<=n时，当前扩展结点Z是解空间中的内部节点，有x[i]=1和x[i]=0共2个儿子节点。对当前扩展结点Z的每个儿子节点，计算相应的符号三角形中+和-个数，然后或剪去不可行树，或以DFS的方式递归地对可行子树(i+1,…,n)进行搜索。

Class Triangle
{
friend int Compute(int);
private:
	void BackTrace(int t);
	int n;  
	int half;
	int count;  //当前+的个数
	int **p;    //符号三角形矩阵
	long sum;   //已找到的符号三角形个数
};
void Triangle::BackTrace(int t)  //第一行的第七列
{
//剪枝(限界)条件：+ -的个数大于 half=n*(n+1)/4
	if(count >half || (t*(t+1)/2-count) >half)
		return; //t*(t+1)/2为当前t个元素的符号三角形元素总数
	if(t >n)  
		sum++;  //成功建立符号二叉树
	else {
//回溯法：选择-->小三角型形成-->DFS-->取消选择-->新选择-->...
		for(int i=0;i<2;i++) {  //01二值选择
			p[1][i] =i;
			count +=i;  //+个数加1
			for(int j=2;j<=t;j++) {
				//gap =j-1   3-->2or1  
				p[j][t-j+1] =p[j-1][t-j+1]^p[j-1][t-j+2];
				count +=p[j][t-j+1];
				/*
				101
				10  这是从下网上看的  下一列的由上一行的同列和下一列异或
				*/
			}
			BackTrace(t+1);
			//取消选择count:生成的子树和本身还原
			for(int j=2;j<=t;j++)
				count -=p[j][t-j+1];
			count -=i;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

时间复杂度：计算可行性约束的条件的时间复杂度是O(n)：检查第一行为n个节点的符号三角形的可行性for(j=2;j<=n;j++)，需要执行n次。在最坏情况下，有2^n个节点需要计算可行性约束。
T(n)=O(n*2^n)

（19）n后问题

问题描述：

分析：i个皇后放在i行x[i]列，其中x[i]∈[1,n]且满足约束条件，可以使用完全n叉树表示，可以采用回溯法解决。
①定义解空间：x[1,n]表示n后问题的解，x[i]表示第i个王后放在第i行第x[i]列
显示约束：xi∈[1,n]
隐式约束：x[i] !=x[j], |i-j| !=|x[i]-x[j]|
②确定解空间结构：完全n叉树

class Queen
{
friend int nQueen(int);
private:
	bool Place(int k);
	void backtrace(int t);
	int n;       //王后个数
	int *x;      //x[i]
	long sum;    //当前解的方案数
};

bool Queen::Place(int k)
{//判断k层与之前的x[i]是否满足隐式条件
	for(int j=1;j<k;j++)
	if((abs(j-k)==abs(x[j]-x[k]))||(x[j]==x[k]))
		return false;
	return true;
}
void Queen::backtrace(int t)
{
	if(t >n) sum++;
	else {     //扩展节点
		for(int i=1;i<=n;i++) {
			x[t] =i;
			if(Place(t))
				backtrace(t+1);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

（20）0-1背包问题

问题描述：

输入：c(c>0), w[n+1] (w[i]>0), v[n+1] (v[i]>0)
输出：(x1,x2,…,xn), (xi=0,1)
约束条件：Σxiwi<=c, max(Σxivi)
物品i可选(x[i]=1)可不选(x[i]=0)，或者是理解为从n个物品中挑选出i个物品，是子集选取问题，可以使用回溯法解决
①定义解空间：解向量为(x1,x2,…,xn)其中x[i]=1代表第i个物品被选进入背包时的背包最优价值
显式约束：xi=0,1
隐式约束：Σxi*wi<=c
②确定解空间结构：每个物品i有2种选择，解空间可以用子集树(完全二叉树)表示。
③回溯+剪枝
key code:
可扩展节点判断–>左子树约束条件判断–>右子树剪枝条件判断

class Knap
{
	friend int Knapsack(vector<int>&,vector<int>&,int,int);
private:
	int Bound(int i);		//右子树上界
	void backtrack(int i);	//回溯
	int bestp;				//最优价值
	int c;
	int n;
	int cw;					//当前背包容量
	int cp;					//当前背包价值
	vector<int> w;
	vector<int> p;	
};
//右子树上界计算
/*
1.将剩余物品按照单位重量价值排序
2.依次装入物品，在装入物品的一部分直至背包装满
*/
int Knap::bound(int i)
{
//剩余容量-->装入物品-->装入部分物品
	int cleft =c-cw;	//剩余容量
	int b =cp;			//剩余价值
	//2.装入物品
	while((i<=n)&&(w[i]<=cleft)) {
		cleft -=w[i];
		b +=p[i];
		i++;
	}
	//3.装入部分物品
	b +=p[i]*cleft/w[i];
	return b;
}
void Knap::backtrack(int i)
{
	if(i >n) {
		bestp =cp;			//当前最优解
		return;
	}
	else {
		//1.左子树(1)约束条件判断
		if(cw+w[i] <=c) {   //容量可装载
			cw +=w[i];		//当前背包重量
			cp +=v[i];      //当前价值
			backtrack(i+1);
			cw -=w[i];
			cp -=v[i];		//返回上层i 变为死结点
		}
		//2.右子树(0)剪枝判断:右子树中解的上界与bestp
		if(bound(i+1) >bestp)
			backtrack(i+1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

为方便排序（按单位重量价值对序号进行排序）建立Object类，同时Knapsack函数用做对backtrack回溯函数数据的初始化

class Object
{
	friend int Knapsack(vector<int>&,vector<int>&,int,int);
public:
	operator <(Object a) const  //sort
	{return (d>a.d);}
private:
	int id;
	float d;					//单位价值
};
/*Knapsack
1.统计初始数据W P，判断物品能否全部装入背包
2.物品按照单位重量价值排序，并赋值给Knap类
*/
int Knapsack(vector<int> w,vector<int> p,int n,int c)
{
	int W =0,P =0;
	vector<Object> Q(n+1);
	//录入排序基本信息 ID
	for(int i=1;i<=n;i++) {
		Q[i].id =i;
		Q[i].d =p[i]*1.0/w[i];
		W +=w[i];
		P +=p[i];
	}
	//1.判断特殊情况：背包能装入所有物品
	if(W <=c)
		return P;
	//2.按照单位重量价值排序
	sort(Q.begin()+1,Q.end());
	//3.赋值给Knap类
	Knap K;
	K.p.resize(n+1);
	K.w.resize(n+1);
	for(int i=1;i<=n;i++){
		K.p[i] =p[Q[i].id];
		k.w[i] =w[Q[i].id]
	}
	K.cp =K.cw =K.bestp =0;
	K.c =c;
	K.n =n;
	K.backtrack(1);  //调用函数
	return K.bestp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

根据上述代码：回溯法能够很好的得到0-1背包问题的最大价值，但并没有显示各个物品的使用情况。
时间复杂度：计算上界需要O(n)的时间，最坏情况下有O(2^n)右子树需要判断上界，因此T(n) =O(n*2^n)

（21）最大团问题

问题描述：求图G的最大团
相关定义：

输入：a[n+1][n+1]
输出：(x1,x2,…,xn) (x[i]=0,1，为1时表示在最大团中)
约束条件：顶点数最多的团
分析：x[i]=1表示i顶点在某个最大团中，因此最大团问题是一个子集选取问题，可以采用回溯法求解。
①定义解空间：解向量(x1,x2,…,xn),x[i]表示i顶点是否在某一个最大团中
②确定解空间结构：i顶点有两种选择(x[i]=0,1)，解空间为子集树（完全二叉树）
③回溯+剪枝：
进入左子树判断：当前顶点到选入的顶点集中的每个顶点相连（不存在a[i][j]=0）
进入右子树判断：cn+n-i >bestn

class Clique
{
	friend MaxClique(vector<vector<int> >&,vector<int>&,int);
private:
	void backtrack(int i);
	vector<vector<int> >a;
	vector<int> x;
	int n;
	int cn;					//当前团顶点数
	int bestn;				//最大团顶点数
	vector<int> bestx;		//最大团顶点集合
};
void Clique::backtrack(int i)
{
	if(i >n) {  //非扩展节点
		//因为剪枝条件是bestn <cn+n-i 因此每一次的值都是更大值
		bestn =cn;
		for(int i=1;i<=n;i++){
			btestx[i] =x[i];
		}
		return;
	}
	else {
		//1.判断i是否与当前顶点集所有顶点相交
		bool ok =true;
		for(int j=1;j<=n;j++){
			if((x[j])&&(!a[i][j])) { //不相交
				ok =false;
				break;
			}
		}
		if(ok) { //进入左子树
			x[i] =1;
			cn++;
			backtrack(i+1);
			x[i] =0;
			cn--;
		}
		else if(cn+n-i>bestn){ //右子树判断
			x[i] =0;
			backtrack(i+1);
		}
	}
}

//MaxClique用于初始化和调用最大团函数
int MaxClique(vector<vector<int> >a,vector<int> x,int n)
{
	Clique Y;
	Y.x.resize(n+1);
	Y.a.resize(n+1);
	for(int i=1;i<=n;i++) {
		Y.a[i].resize(i+1);
	}
	for(int i=1;i<=n;i++) 
	for(int j=1;j<=n;j++)
		Y.a[i][j] =a[i][j];
	Y.n =n;
	Y.cn =Y.bestn =0;
	backtrack(1);
	for(int i=1;i<=n;i++)
		x[i] =Y.x[i];
	return Y.bestn;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

（22）图的m着色问题

问题描述：

输入：a[n+1][n+1] (邻接矩阵a[i][j]=1表示(i,j)∈E)
输出：x[n+1],(x[i]=0,1,…,m为0时是不可着色)
约束条件：一条边的两个顶点着不同颜色
分析：解向量是x[n+1],x[i]有m中颜色选择，可以用完全m叉树表示，由此可以尝试回溯法。
①定义解空间：解向量(x1,x2,…,xn),x[i]=k(k=1,2,…m)表示i顶点的着色
显式约束：x[i]∈[1,m]
隐式约束：if(a[i][j]) x[i] !=x[j]
②确定解空间结构：高度为n+1的完全m叉树
③回溯+剪枝：
进入左子树的条件：该节点所着颜色x[i]和其相邻节点不同
进入右子树的条件：（着色数可以<m）无

class Color
{
	friend int mColoring(int,int,vecotr<vector<int>>);
private:
	bool OK(int k);
	void backtrack(int t);
	int n;			
	int m;
	vector<vector<int> >a;
	vector<int> x;
	long sum;
};

bool Color::OK(int k)   //约束函数  k相邻节点颜色不同
{
	for(int i=1;i<=n;i++)
		if((a[i][k])&&(x[i] ==x[k])) return false;
	return true;
}

void Color::backtrack(t)
{
//扩展节点判断-->扩展可选项-->约束限界条件判断
	if(t >n) {   //非扩展  得到新的m染色方案
		sum++;
		for(int i=1;i<=n;i++)
			cout<<x[i]<<' ';
		cout<<endl;
	}
	else {
		for(int i=1;i<=m;i++) {
			x[t] =i;
			if(OK(t))
				backtrack(t+1);
			x[t] =0;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间复杂度：解空间中的节点个数是Σm^i(i=0,1,…,n-1)，OK()函数检查当前扩展结点的每个子节点颜色可用性的时间复杂度O(mn)，因此
*T(n)=Σ(mn)mi =n m(m^n-1)/(m-1)=O(n * m^ n)

(23)旅行售货员问题

问题描述：

输入：a[n+1][n+1] (邻接矩阵a[i][j]=1表示(i,j)∈E)
输出：最小总路程bestc 和 驻地路线x[n+1] (1~n的某种排列)
约束条件：经过每个节点一次且最终回到原点
分析：行走的路线（经过的节点）形成的路径是1~n排列的子集，可以尝试排列树的回溯算法解决
①定义解空间：解向量x[n+1]是1~n的某种排列情况
显式约束：x[i] !=x[j]
隐式约束：a[1][n+1]=1(首尾相连) 路径之和最短
②确定接空间结构：排列数
③回溯+剪枝：约束条件是当前扩展节点的父节点到当前节点有路径相连，剪枝条件是加上当前路径距离后小于当前最优距离bestc

class Traveling
{
	friend int TSP(vector<vector<int> >,vector<int>,int,int);
private:
	void backtrack(int i);
	int n;
	vector<vector<int> >a;
	vector<int> x;			//当前路径
	vector<int> bestx;		//当前最优路径
	int bestc;				//当前最短路径和
	int cc;					//当前路径和
	int NoEdge;				//无边标记
}
void Traveling::backtrack(int i)
{
	if(i ==n) {    			//新的路径x[1~n]保存实际的顺序
//需要判断 能否经过所有节点、能否首尾相连且距离最短
		if((a[x[n-1]][x[n]]!=NoEdge)&&(a[x[n]][1]!=NoEdge)&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc ==NoEdge)){
			bestc =cc+a[x[n-1]][x[n]]+a[x[n]][1];
			for(int j=1;j<=n;j++)
				bestx[j] =x[j];
		}	
	}
	else {
		for(int j=i;j<=n;j++) {
//判断约束剪枝条件-->能否进入子树(路程小于当前最优且父节点i-1有边连接)
			if((a[x[i-1]][x[j]] !=NoEdge)&&(cc+a[x[i-1]][x[j]]<bestc||bestc ==NoEdge))  {
				swap(x[i],x[j]);
				cc +=a[x[i-1]][x[i]]; //x[i]此时为扩展结点
				backtrace(i+1);
				cc -=a[x[i-1]][x[i]];
				swap(x[i],x[j]);
			}
		}
	}
}
int TSP(vector<vector<int> >a,int n,int NoEdge)
{//初始化与调用
	Traveling Y;
	Y.x.resize(n+1);
	Y.bestx.resize(n+1);
	Y.a.resize(n+1);
	for(int i=1;i<=n;i++){
		Y.a[i].resize(n+1);
		Y.x[i] =Y.bestx[i] =i;
	}
	Y.bestc =NoEdge;
	Y.cc =0;
	Y.NoEdge =NoEdge;
	Y.backtrace(2);
	return Y.bestc;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

五：分支限界法

（25）单源最短路径问题

问题描述：

①定义解空间：dist[i]
②确定解空间结构：子集树
③广度优先搜索+剪枝
遍历当前扩展节点的所有儿子节点，是否加入活结点序列需要判断：
（1）可行性：1、i,j有边相连 2、从源节点出发，途经顶点i到顶点j的相应路径小于当前最小路长。
（2）限界函数：一个节点的下界不小于当前最小路长（本题未用到）
（3）优先级：length当前路径长度

#define inf 99999
class Gragh
{
	friend void main(void);
public:
	void shortestPaths(int);
private:
	int n;
	vector<int> prev;	//前驱顶点数组
	vector<vector<int> >c;
	vector<int> dist;	//最短距离数组-->btestd
};
class MinHeapNode
{
	friend Gragh;
public:
	operator int()const{return length; }
private:
	int length;		//当前路长
	int i;			//当前顶点编号
};
//初始化在调用函数中，此为实现函数
void Gragh::shortestPaths(int v)
{
	MinHeap<MinHeapNode> H(1000);
	MinHeapNode E;
	E.i =v;
	E.length =0;
	dist[v] =0;
	//搜索解空间
	while(1){
		for(int j=1;j<=n;j++) {
		//考虑可行性:有边且距离较短
			if((c[E.i][j]<inf)&&(E.length+c[E.i][j] <dist[j])) {
				dist[j] =E.length+c[E.i][j];  //更新距离
				prev[j] =E.i;
				//加入活结点序列
				MinHeapNode N;
				N.length =dist[j];
				N.i =j;
				H.Insert(N);
			}
		}
		//当前节点扩展完毕，取出下一扩展节点
		try {H.DeleteMin(E); }
		catch(OutOfBounds) break; //优先队列为空 找到最优解
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

（26）装载问题

问题分析：本质是将第一艘船尽可能的装满，装载问题是子集选取问题，解空间是一颗子集树
①定义解空间：x[i]
②确定解空间结构：子集树
③广度优先搜索+剪枝：活结点加入活结点列表的条件+剪枝条件
【1】队列式分支限界法
队列Q用于存放活结点表，表中元素值表示活结点所对应的当前载重量。当元素值为-1时，队列已到达解空间树同一层的末尾。
（1）可行性(左儿子节点)：Ew+w[i] <=c（Ew是当前扩展结点载重量，c是船的总载重量），且为非叶节点
可行结点：更新besrw+加入活结点序列
（2）限界性（右儿子节点）：Ew+r <=bestw （r是剩下集装箱的重量,bestw是当前最优载重量），且为非叶节点
为了尽快使右子树测试生效，算法每次进入左子树时更新bestw值
（3）while截止条件：队列取值为-1且队列为空

Notations:
r: 剩余集装箱重量（每次选取一个集装箱，就减去对应集装箱的重量）

int MaxLoading(vector<int> w,int c,int n)
{
	//初始化：Q AND R
	Queue<int> Q;
	Q.Add(-1);
	int i=1;		//i:层数
	int Ew =0;		//当前载重量
	int bestw =0;
	int r =0;		//剩余集装箱重量
	for(int j=2;j<=n;j++)
		r +=w[j];	//剩下的n-1个集装箱的重量
	while(1){
	//判断可行性与限界性并加入活结点序列
		//判断节点可行性（进入左子树）
		int wt =Ew+w[i];
		if(wt <=c) {	//可行结点:更新+进入活结点序列
			//更新bestw
			if(wt >bestw) bestw =wt;
			//进入活结点序列(非叶节点)
			if(i <n) Q.Add(wt);
		}
		else {
			//判断限界性与非叶节点
			if(Ew+r >bestw&&i<n)
				Q.Add(Ew);
		}
	//取出活结点作为当前扩展结点(若为-1且为空 则退出 否则+ -1)
		Q.Delete(Ew);		//下一个扩展节点
		if(Ew ==-1) {
			if(Q.IsEmpty())
				return bestw;
			else {
				Q.Add(-1);
			 	Q.Delete(Ew);
			 	i++;
			 	r -=w[i];	//减去当前扩展结点的重量
			}
		}
			
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

【2】优先队列分治限界法
最大优先队列H（用元素类型为HeapNode的最大堆表示）存储活结点表，优先队列中活结点的优先级为x.uweight，优先队列中优先级最大的活结点成为下一个扩展结点。
问题：为什么当一个叶节点成为当前扩展结点时，可以断言该叶节点对应的解为最优解？
以节点x为根的子树中所有节点相应的路径的载重量不超过x.uweight。子集树中叶节点相应的载重量与其优先级相同
（1）可行性：Ew+w[i] <c；（左子树） 则加入子集树的i+1层，并插入最大堆。（右子树）总是可行的，直接插入子集树的最大堆
（2）优先级：x.uweight=Ew+w[i]+r[i] or Ew+r[i],其中r[i]表示剩余重量数组，即选择了i个物品后的剩余重量
（3）while截至条件：当叶节点成为当前扩展结点

bbnode:子集空间树中的节点类型，用于构建最优解路径
HeapNode:最大堆优先队列数据类型，用于优先级排序

class bbnode {
	friend void AddLiveNode(MaxHeap<HeapNode>& bbnode*,int,bool,int);
	friend int MaxLoading(vector<int>,int,int,vector<int>);
	friend class AdjanceyGragh;
private:
	bbnode *parent;		//指向父节点
	bool LChild;		//左儿子节点标志(是否加入最优解路径)
};

class HeapNode {
	friend void AddLiveNode(MaxHeap<HeapNode>& bbnode*,int,bool,int);
	friend int MaxLoading(vector<int>,int,int,vector<int>);
public:
	operator int() const {return uweight;}
private:
	bbnode *ptr;		//指向该节点的子集树
	int uweight;		//活结点上界(当前载重量+剩余载重量)
	int level;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

AddLiveNode将新产生的活结点加入到子集树中，并将新节点插入到表示活结点优先队列的最大堆中

void AddLiveNode(MaxHeap<HeapNode>& H,bbnode *E,int wt,bool ch,int lev)
{
	bbnode *b =new bbnode;
	b->parent =E;
	b->LChild =ch;
	HeapNode N;
	N.uweight =wt;   //Ew+r[i]+w[i]*0/1
	N.level =lev;
	N.ptr =b;
}
1
2
3
4
5
6
7
8
9
10

第i+1层的剩余重量r[i]定义为r[i]=Σ(i+1~n)w[j]

int MaxLoading(vector<int> w,int c,int b,vector<int> bestx)
{
	//初始化最大堆和剩余重量r[i]
	MaxHeap<HeapNdoe> H(1000);
	vector<int> r(n+1);
	r[n] =0;
	for(int i=n-1;i>0;i--)  //r[i]:第i+1层的剩余重量
		r[i] =r[i+1]+w[i+1];
	int i=1;
	bbnode *E =0;			//当前扩展结点
	int Ew =0;				//当前载重量
	//搜索子集树空间  第一层的根节点为空 边表示实际物品
	whiile(i !=n+1) {  
		//1.可行性分析
		if(Ew+w[i] <c) 
			AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);  //左
		AddLiveNode(H,E,Ew+r[i],false,i+1);//i物品未加入
		//2.扩展下一个节点(一般的 左儿子节点优先级>右儿子节点)
		HeapNode N;
		H.DeleteMax(N);
		i =N.level;   //i+1层  第i个物品的节点在i+1层
		E =N.ptr;		//子集树节点
		Ew =N.uweight-r[i-1];//EW+w[i]+r[i]-r[i]
	}
	//3.构造当前最优解
	for(int j=n;j>0;j--) {
		bestx[j] =E->LChild;
		E =E->parent;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

（27）0-1背包问题

问题描述：

问题分析：0-1背包是子集选取问题，可以用子集树表示
①定义解空间：x[i] (0,1表示物品i是否被选取)
②确定解空间结构：子集树
③广度优先搜索+剪枝
（1）可行性：当前载重量小于背包总重量：wt <=c。且装入物品后背包价值大于当前最优价值：cp+p[i] >bestp。左儿子节点加入子集树和活结点优先队列，右儿子节点一定是可行结点
（2）限界函数：右儿子节点满足上界约束：bound(i+1) >bestw。满足时，右儿子节点才加入子集树和活结点优先队列
（3）优先级：上界函数Bound函数值uprofit
（4）while截止条件：叶节点成为扩展结点（其他活结点的价值上界均不超过当前叶节点的价值）

子集空间树中结点类型为bbnode，最大堆的元素类型是HeapNode，Object类用于按照单位重量价值的物品排序

class Object{
	friend int Knapsack(vector<int>,vector<int>,int,int,vector<int>&);
public:
	int operator <=(Object a) const {return (d >=a.d);}
private:
	int ID;
	float d;			//单位重量价值
};
class Knap;
 
class bbnode{
	friend Knap;
	friend int Knapsack(vector<int>,vector<int>,int,int,vector<int>&);
private:
	bbnode *parent;
	bool LChild;
};

class HeapNode{			//优先级排序类
	friend Knap;
public:
	operator int() const {return uprofit;}
private:
	int weight;			//结点对应重量
	int profit;			//结点对应价值
	int uprofit;		//结点价值上界
	int level;			//节点在子集树的层数
	bbnode *ptr;		//指向活结点的子集树上的指针
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Knap类用于调用函数和存储相应的数据信息，与回溯法类似，但是不包含bestp，而新增成员bestx,bestx[i]=1时，当前最优解包含物品i
Knapsack:用于函数的数据预处理
MaxKnapsack:分支限界法，各物品已经按照单位重量价值进行排序。先检查左儿子结点，若满足可行性则加入子集树和最大堆并尝试更新bestp。对右子树当满足上界约束时，加入子集树和最大堆

class Knap{
	friend int Knapsack(vector<int>,vector<int>,int,int,vector<int>&);
public:
	int MaxKnapsack();
private:
	MaxHeap<HeapNode> *H;
	int Bound(int i);
	void AddLiveNode(int up,int cp,int cw,bool ch,int leve);
	bbnode *E;			//指向扩展结点的指针
	int n;
	int c;
	vector<int> w;
	vector<int> p;
	int cw;
	int cp;
	vector<int> bestx;
};

int Knap::Bound(int i)		//计算结点上界
{
	int cleft =c-cw;	//剩余容量
	int b =cp;			//当前价值
	//整个装入
	while(i<=n&&w[i]<=cleft) {
		cleft -=w[i];
		b +=p[i];
		i++; 
	}	
	//部分装入(已经按照单位价值进行排序)
	if(i <=n)
		b +=p[i]*1.0*cleft/w[i];
	return b;
}
//将活结点加入子集树和最大堆
void Knap::AddLiveNode(int up,int cp,int cw,bool ch,int leve)
{
	bbnode *b =new bbnode;
	b->parent =E;			//父节点为当前扩展结点
	b->LChild =ch;			
	HeapNode N;
	N.uprofit =up;
	N.profit =cp;
	N.weight =cw;
	N.ptr =b;				//加入子集树
	H->Insert(N);			//插入最大堆
}

//对子集树的优先队列式分支限界搜索
int Knap::MaxKnapsack()
{
	//初始化最大堆和当前最优质
	MaxHeap<HeapNode> H(1000);
	bestx.resize(n+1);
	//子集树第一层结点为空 对应元素为边
	int i=1;
	E =0;
	cw =cp =0;
	int bestp =0;
	int up =Bound(1);		//所有物品的价值上界
	//搜索子集树
	while(i !=n+1) {
		//1.左儿子结点：可行性判断  容量+价值
		int wt =cw+w[i];
		if(wt <c) {
			//更新最值
			if(cp+p[i] >bestp)
			{
				 bestp =cp+p[i];
				 AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);
			}
		}
		//2.右儿子结点：限界条件判断
			up =Bound(i+1);		//剩余物品上界
			if(up >bestp)
				AddLiveNode(up,cp,cw,false,i+1);
		//相比于左儿子 右儿子进行限界判定 同时不进行最优值更新
		//取下个扩展结点
		HeapNode N;
		H->DeleteMax(N);
		E =N.ptr;
		cw =N.weight;
		cp =N.profit;
		up =N.uprofit;
		i =N.level;	
	}
	//构造当前最优解
	for(j=n;j>0;j--){
		bestx[j] =E->LChild;
		E =E->parent; 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

KnapSack函数对输入数据进行预处理(按照单位重量价值排序)，再调用子集树的优先队列分支限界搜索

int KnapSack(vector<int> p,vector<int> w,int c,int n,vector<int>& bestx)
{
	//初始化
	int W =0;				//总价值
	int P =0;				//总重量
	vector<Object> Q(n+1);
	for(int i=1;i<=n;i++) {
		Q[i].ID =i;
		Q[i].d =1.0*p[i]/w[i];
		P +=p[i];
		W +=w[i];
	}
	if(W <=c)
		return P;
	//1.单位价值排序
	sort(Q.begin()+1,Q.end());
	Knap K;
	//2.初始化
	K.p.resize(n+1);
	K.w.resize(n+1);
	for(int i=1;i<=n;i++){
		K.p[i] =P[Q[i].ID];
		K.w[i] =W[Q[i].ID];
	}
	K.cp =0;
	K.cw =0;
	K.c =c;
	K.n =n;
	int bestp =MaxKnapSack();
	//3.输出最优序列
	for(int j=1;j<=n;j++)
		bestx[Q[j].ID] =K.bestx[j];
	return bestp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

（28）最大团问题

问题描述：求图G的最大团
相关定义：

问题分析：最大团问题是子集树问题，可以采用分支限界法搜索
①定义解空间：x[i]
②确定解空间结构：子集树
③广度优先搜索+剪枝
（1）可行性分析：考察左儿子结点，当顶点i与当前团中所有顶点之间都有边相连，则为可行结点，加入子集树和最大堆中。
（2）限界性分析：考察右儿子结点，当un(当前团的最大顶点数上界)>bestn时，右儿子节点加入子集树和最大堆
（3）优先级：un=cn+(n-level+1)当前团的最大顶点数上界
（4）while截止条件：叶节点(n+1层)成为当前扩展结点
（5）bestn更新时间：进入左子节点判断更新

CliqueNode:优先级排序的最大堆元素类型
bbnode:子集树结点类型

class bbnode{
	friend class Clique;
private:
	bbnode* parent;
	bool LChild;
};

class CliqueNode{
	friend class Clique;
public:
	operator int () const {return un;}
private:
	int cn;				//当前团顶点数
	int un;				//当前团顶点数上界
	int level;
	bbnode* ptr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Clique类用二维矩阵存储图G

class Clique{
	friend main(void);
public:
	int BBMaxClique(vector<int>&);
private:
	void AddLiveNode(MaxHeap<CliqueNode>&H,int cn,int un,int level,vecotr<bbnode> E,bool ch);
	vector<vector<int> > a;
	int n;
};

//当前活结点加入子集树和最大堆中
void Clique::AddLiveNode(MaxHeap<CliqueNode>&H,int cn,int un,int level,bbnode* E,bool ch)
{
	bbnode* b =new bbnode;
	b->parent =E;
	b->LChild =ch;
	CliqueNode N;
	N.cn =cn;
	N.un =un;
	N.ptr =b;
	N.level =level;
	H.Insert(N);
}

//分支限界搜索
int Clique::BBMaxClique(vecotr<int>& bestx)
{
	//初始化最大堆和根节点
	MaxHeap<CliqueNode> H(1000);
	int i =1;
	int bestn =0;
	int cn =0;
	bbnode* E =0;			//当前扩展结点
	while(i !=n+1) {
		//1.可行性检查  回溯法检查 团中结点是否与i相连
		bool OK =true;
		bbnode *B =E;
		for(int j=i-1;j>0;B=B->parent,j--) {
			if(B->LChild&&a[i][j] ==0) {  //团中顶点+相连
				OK =false;
				break;
			}
		}
		if(OK) {
			if(cn+1 >bestn) bestn =cn+1;
			AddLiveNode(H,cn+1,cn+n-i,i+1,E,true);
		}
		//2.右儿子结点 限界性分析
		if(cn+n-i >bestn) 
			AddLiveNode(H,cn,cn+n-i,i+1,E,false);
		//3.取下一个扩展结点
		CliqueNode N;
		H.DeleteMax(N);
		E =N.ptr;
		cn =N.cn;
		i =N.level;
	}
	//退出循环 
	for(int j=n;j>0;j--)
	{
 		bestx[j] =E->LChild;
 		E =E->parent; 
 	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

（29）旅行售货员问题

问题分析：TSP问题的解空间树是排列树，采用优先队列式分支限界法求解
（1）定义解空间：x[n]
（2）确定解空间结构：排列树
（3）广度优先+剪枝
①约束条件：有边相连
②限界条件：cc+rcost <bestc
rcost初始化为MinSum，即各节点最小出边权值和。每访问一个节点，减去该节点的最小出边
③循环终止条件：排列树的叶节点成为当前扩展结点s=n-1

Model:
MinHeapNode：最小堆中的元素类型

class Traveling
{
	friend void main(void);
public:
	int BBTSP(vector<int>& v);
private:
	int n;
	vecotr<vecotr<int> > a;
	int NoEdge;
	int cc;
	int bestc;			//当前最小费用
}

class MinHeapNode
{
	friend Traveling;
public:
	operator int() const {return lcost;} //子树下界为优先级
private:
	int lcost;		//子树费用下节
	int cc;		
	int rcost;		//剩下结点的最小出边和
	int s;			//第s层
	vector<int> x;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

（1）优先级：每个结点的子树下界lcost =rcost+cc。
（2）思路：①当s=n-1时，扩展结点为叶节点。此时剩余的活结点的lcost不小于已找到回路的费用，算法结束。对非叶节点进行扩展时，②当s=n-2时，扩展结点是某个叶节点的父节点，如果此叶节点能形成一条可行回路，且费用小于当前费用，则将叶节点加入优先队列。③当s<n-2时，依次产生所有可行的儿子节点，并根据限界函数lcost <bestc，判断是否加入优先队列。
注意（1）当G为不连通图时，没有TSP回路。（2）bestc在扩展结点为某叶节点的父节点时更新

int Traveling::BBTST(vecotr<int>& v)
{
	MinHeap<MinHeapNode> H(1000);
	vector<int> MinOut(n+1);
	int MinSum;				//最小出边和
	//1.找每个结点的最小出边并保存在MinOut
	for(int i=1;i<=n;i++) {
		int Min = NoEdge;
		for(int j=1;i<=n;j++){
			if((a[i][j] !=NoEdge)&&(a[i][j] <Min||Min ==NoEdge))
				Min =a[i][j];
		}
		//注：当为不连通图时 没有TSP回路
		if(Min ==NoEdge) return NoEdge;
		MinSum +=Min;		
		MinOut[i] = Min;  //保存 有边且最小
	}
	//初始化
	MinHeapNode E;
	E.x.resize(n);		//某种排列顺序
	for(int i=0;i<n;i++)
		E.x[i] = i+1;
	E.s =E.cc = 0;
	E.rcost = MinSum;		//剩余结点的最小出边和
	int bestc = NoEdge;
	//2.广度优先搜索+剪枝
	while(E.s < n-1) {  //当前扩展结点非叶节点
		if(E.s ==n-2){    //某个叶节点的父节点 （回路与最优）
			if(a[E.x[n-2]][E.x[n-1]] !=NoEdge&&a[E.x[n-1]][E.x[1] !=NoEdge &&(E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][E.x[1]] <bestc||bestc ==NoEdge)) {
				bestc =E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][E.x[1]];
				E.cc = bestc;
				E.lcost = bestc;
				E.s++;
				H.Insert(E);
			}
		}
		else {  
			for(int i=E.s+1;i<n;i++){  //产生儿子节点
				if(a[E.x[E.s]][E.x[i]] !=NoEdge) {//约束条件
					int cc = E.cc+a[E.x[E.s]][E.x[i]];
					int rcost -=MinOut[E.x[E.s]]; 
					//减去当前扩展结点的最小出边
					int b =cc+rcost;
					//限界条件检验
					if(b <bestc||bestc ==NoEdge){
						MinHeapNode N;
						N.x.resize(n);
						for(int j=0;j<n;j++)
							N.x[j] =E.x[j];	//复制父节点路径
						//当前为s+1层（交换s+1与i的排列顺序）
						N.x[E.s+1] =E.x[i];
						N.x[i] =E.x[E.s+1];
						N.cc =cc;
						N.s =E.s+1;
						N.lcost =b;
						N.rcost =rcost;
						H.Insert(N);
					}
				}
			}
			if(H.size() ==0) break;
			E =H.top();
			H.pop();
		}
	}
	if(bestc ==NoEdge)
		return NoEdge;
	for(int i=0;i<n;i++)
		v[i+1] =E.x[i];
	return bestc;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

六：实验题目

(1) 集合划分问题

问题描述：

输入：n(n>0), m(0<m<n)
输出：t(n,m)
约束条件：t(n,m)是n个元素集合划分为m个元素集合的集合个数
观察题目中n=4的例子，t(4,2)由t(3.1)和t(3,2)变化组成。
思路：t(4,2)可以看作是新增加的元素添加在t(3,2)中元素或t(3,1)加上此元素，因此t(n,m)可以转化为t(n-1,m), t(n-1,m-1)的组合情况
（1）求什么设什么：求n个元素集合划分为m个元素集合的个数，令t(n,m)为此解
（2）最优子结构：t(n,m)由t(n-1.m)和t(n-1,m-1)组成，前者①在集合内增加元素，后者②在集合的元素中填充元素。若①非最优解，最优解为T’，则T‘+t(n-1,m) >t(n,m)矛盾
（3）递推公式：
t(i,j) = t(i-1,j-1) + t(i-1,j) * j

Model:

void setDivision(vector<vector<int> >&t,int n)
{
	//1.矩阵初始化   m=1与n=m时t(n,m)=1
	t.resize(n+1);
	for(int i=0;i<=n;i++)
	t[i].resize(n+1);
	for(int i=1;i<=n;i++)
		t[i][1] = t[i][i] =1;
	//2.递推公式 自底向上运算
	for(int k=3;k<=n;k++){   //第3行开始
		for(int i=k;i<=n;i++){
			int j =i-(k-2);
			t[i][j] = t[i-1][j-1]+j*t[i-1][j];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(2) 树的最大连通分支

问题描述：
输入：w(n+1), Edge(a->b)
输出：权值和最大的连通子图的权值
约束条件：权值和最大
（1）思路：一个连通子图的根节点的权值和与其本身和子节点有关，若子节点的权值和大于0，则加入根节点的连通子图。
（2）重叠子问题性质
（3）最优子结构性质：一个连通子图的根节点的权值和可能有两种情况，①某个子节点的权值和>0，根节点权值+该子节点的权值和，否则②根节点自身的权值。若①时子节点的权值和非最优，T’>s因此T’+w[root] >root.Vmax，产生矛盾。
（4）递推公式（访问i结点）
[[i].father].Vmax = [[i].father].Vmax ([i].Vmax <0)
=[[i].father].Vmax+[i].Vmax ([i].Vmax >0)

Model
①遍历查找root结点–>②访问叶节点与父节点转换，自底向上求解

class Cnode
{
	int weight;
	int father;
	int childnum;		//该节点的子节点数目
	int Vmax;			//该节点的最大连通分支权值
	bool visited;
}
/*vector<vector<Cnode> >tree初始化为[n+1][n+1]类型
并对Cnode元素进行初始化
*/
LBranch(vector<vector<Cnode> >tree,int n)
{
	//1.找根节点
	int root =0;
	for(int i=1;i<=n;i++){
		if(tree[i].father ==0)
			root = i;
	}
	//2.遍历树，自底向上求解每个节点的Vmax
	for(int i=1;i<=n;i++){
		if((tree[i].childnum==0)&&(!tree[i].visited)){ //叶节点才进入
			tree[i].visited =true;
			tree[tree[i].father].childnum--;
			if(tree[i].Vmax >0)
			tree[tree[i].father].Vmax +=tree[i].Vmax;
			//子节点权值和>0 累加到父节点的权值和
		}
	}		
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

（3）工作分配问题

问题描述：

输入：n(n>0),a[n+1][n+1] (a[i][j]表示第i个工作分配给第j个人所需的费用)
输出：最小的总费用
①定义解空间：x[n+1] (x[i]表示第i个工作分配人的序号)
②确定解空间结构：排列树
③深度优先+剪枝：
限界条件：cc+a[i][j] < bestc
判断是否需要剪枝–>不需要则向下探索
注意：仅当进入叶节点时才判断是否需要更新最优解

Model:

class Working
{
	friend int workDistribution(vector<vector<int> >,int);
private:
	void backtrace(int i);
	int n;
	vector<vector<int> >a;	
	vector<int> bestx;		//最优花费的排列情况
	vector<int> x;
	int bestc;
	int cc;
};
//仅当进入叶节点后 才更新最优值！
void Working::backtrace(int i)
{
	//1.为叶节点，根据判断条件选择是否更新当前最优解
	if(i ==n) {		//n个工作
		if(cc+a[n][x[n]] <bestc || bestc ==0){
			bestc = cc+a[n][x[n];
			for(int j=1;j<=n;j++)
				bestx[j] = x[j];
		}
	}
	else {  //非叶节点，判断是否需要剪枝
		for(int j=1;j<=n;j++) {
			int tmp = cc+a[i][x[j]];
			if(tmp <bestc||bestc ==0){
				swap(x[i],x[j]);
				cc +=a[i][x[i]];
				backtrace(i+1);
				cc -=a[i][x[i]];
				swap(x[i],x[j]);
			}
		}
	}
}

int workDistribution(vector<vector<int> > a,int n)
{
    Working W;
    W.x.resize(n+1);
    W.bestx.resize(n+1);
    W.a.resize(n+1);
    for(int i=1;i<=n;i++)
        W.a[i].resize(n+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        W.a[i][j] =a[i][j];
    for(int i=1;i<=n;i++)
        W.x[i] =i;
    W.n =n;
    W.bestc =W.cc =0;
    W.backtrace(1);             //搜索x[1~n]的全排列
    return W.bestc;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

（4）字符串比较问题

问题描述：

输入：string:x, y; k(k>0)
输出：x, y两个字符串的最短距离
设D(i,j)为长度为i,j的两字符串的最短距离。距离的比较对象可以是字符&字符，空格&字符。①字符&字符时，D(i,j) =D(i-1,j-1)+dist(x[i],y[j])。②空格&字符时，D(i,j) = D(i-1,j)+k或D(i,j-1)+k。因此对于字符串位置i,j处，D(i,j)可能有三种情况，取三种情况的最小值就是当前最短距离。
（1）重叠子问题性质
（2）最优子结构性质：拿①距离，当长度为i-1,j-1的字符串的最短距离为T’ <D(i-1,j-1)时，T’+dist(x[i],y[j]) < D(i,j)，矛盾。
（3）递推公式：
D(i,j) = Min( D(i-1,j-1)+dist(x[i],y[j]), D(i-1,j)+k, D(i,j-1)+k )

Model:

//D[n+1][n+1]已初始化为二维数组
int minStrCmp(string x,string y,int k,vector<vector<int> >D)
{
	int len1 = x.size();
	int len2 = y.size();
	for(int i=0;i<=len1;i++)
	D[i][0] = i*k;
	for(int j=0;j<=len2;j++)
	D[0][j] = j*k;

	//2.递推公式 自底向上
	for(int i=1;i<=len1;i++) {
		for(int j=1;j<=len2;j++){
			D[i][j] = Min(D[i-1][j-1]+abs(a[i-1]-b[j-1]),D[i-1][j]+k,D[i][j-1]+k);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（5）最长上升子序列问题

问题描述：给定N个数，求着N个数的最长上升子序列
输入：N(N>0)，a[N] (a[i]>0)
输出：最长的严格上升子序列
约束：上升子序列中，a[i] > a[j] (j < i)
①求什么，设什么：设m[i]是以a[i]结尾的最长上升子序列长度
②重叠子问题性质：m[i]涉及到m[1],m[2]…m[i-1]的大小
③最优子结构性质：m[i]的值可能为①a[i]是a[1~i-1]中最小的，则m[i] = 1②存在X’，使得j∈X’，a[j] < a[i]。因此m[i] = max(a[j])+1。
递推公式：
m[i] = 1(a[i] =min(a[j])),j∈[1,i]) 或者
=max(m[j])+1

Model:

int LCS(vector<int> a,vector<int>& m,vector<int> &prev,int n)
{
	//a,m初始化为n大小的数组
	//递推公式 自底向上运算
	for(int i=1;i<=n;i++)
		prev[i] = 0; //前驱为0
	for(int i=1;i<=n;i++){
		m[i] = 1;
		for(int j=1;j<=i;j++){
			if(a[j] <a[i]){
				m[i] = m[j]+1;
				prev[i] = a[j];
			}
		}
	}
	return m[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（6）半数集问题

问题描述：

输入：n(n>0)
输出：半数集set(n)的个数m
约束：左边添加的自然数不能超过最近添加的数的一半
（1）思路：首先想到的是递归方法，当n为奇数时，set(n) =set(n-1)。而当n为偶数时，set(n)=Σset(i),i∈[1,n/2]。但是使用递归法就会存在很多的重叠子问题。发现当n为偶数时set(n-1)=set(n-2)=set(n)=Σset(i),i∈[1,n/2 -1]，可以得到递推关系set(n) =set(n-1)+set(n/2)
（2）重叠子问题性质与最优子结构性质
（3）递推公式
set(n) = set(n-1) (n&1== 0)
=set(n-1)+set(n/2) (n&1==1)

Model:

int halfSet(int n,vector<int>& set)
{
	set.resize(n+1);
	//自底向上求解
	set(1) =1;
	for(int i=2;i<=n;i++){
		if(i&1 ==0)
			set(i) = set(i-1);
		else 
			set(i) = set(i-1)+set(i/2);
	}
	return set(n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13