回溯法的含义 百度百科

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束

（1）针对所给问题，定义问题的解空间；//解答树？

（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

 

例子1

N皇后问题

方法1就是动态判断 

void search(int cur){	if(cur==n+1)//说明已经处理完成了(cur==n-1时正在处理最后一排) 	{		tot++;		if(tot<=3)			{			for(int i=1;i<=n;i++)			{				printf("%d ",map[i]);			}			putchar('\n');		}	}		else	{		//尝试填入i于第cur行 		for(int i=1;i<=n;i++) 		{ 			int ok=1;			//开始检查是否在之前的皇后的攻击范围之内 			for(int j=1;j

但是此处因为每次动态判断的列，对角线有重复，所以会效率低下

下面采取了一种用二维数组进行记忆化判断的方法，此种方法可以提高效率。

int vis[3][50];//此处的20是用n-1+1+n-1 估算出来的 //vis[0][i]记录的是i列是否属于攻击范围 //vis[1][i]记录的是i号正对角线是否属于攻击范围//vis[2][i]记录的是i号副对角线是否属于攻击范围void search2(int cur){	if(cur==n+1)//说明已经处理完成了(cur==n-1时正在处理最后一排) 	{		tot++;		if(tot<=3)			{			for(int i=1;i<=n;i++)			{				printf("%d ",map[i]);			}			putchar('\n');		}	}		else	{		//开始尝试加入i		for(int i=1;i<=n;i++) 		{			int ok=1; 			//开始检查 			if(vis[0][i]||vis[1][cur+i]||vis[2][cur-i+n])				ok=0;			//为了清晰 写的比较啰嗦点 			if(ok)			{ 				//因为vis数组是全局变量，此处若想在递归中来当作局部变量一样入栈出栈，必须要手动恢复 				vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]	=1;				map[cur]=i;				search2(cur+1);				vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]	=0;			}					}	}}

这样效率就提高了不少

用wikioi的一张图进行对比

恰好是一半的时间左右，，这个好像是可以根据分析算出的。。。暂时先留个疑问。

例子2  素数环问题

也是有两个方法来进行比较。

第一个就是纯粹的动态判断+暴力枚举

因为这里需要不断得进行枚举排列。

那么就有stl进行下一个排列枚举的方法 还有动态生成的方法。

这里是要进行先枚举排列后进行判断，所以用do while循环来调用next_permutation

//生成第一个排列	for(int i=1;i<=n;i++) 		A[i-1]=i;	//用这个排列来使用np .但是要保证一直以1开头 	do	{	//开始判断		int ok=1;		for(int i=0;i

这种方法因为是无脑枚举...所以很慢

而用回溯法就可以解决这个问题，使得解答树的遍历过程显得很聪明。

void dfs(int cur){	//当cur==n时说明A[n-1] 已经有元素了 	if(cur==n&&isp[A[0]+A[n-1]])	{		for(int i=0;i

A[0]=1;

dfs(1);

这样的话，即使n=18依然可以跑得比较快。