C++回溯法实例分析
本文实例讲述了C++的回溯法，分享给大家供大家参考之用。具体方法分析如下：
一般来说，回溯法是一种枚举状态空间中所有可能状态的系统方法，它是一个一般性的算法框架。
解向量a=(a1,a2,...,an)，其中每个元素ai取自一个有限序列集Si，这样的解向量可以表示一个排列，其中ai是排列中的第i个元素，也可以表示子集S，其中ai为真当且仅当全集中的第i个元素在S中；甚至可以表示游戏的行动序列或者图中的路径。
在回溯法的每一步，我们从一个给定的部分解a={a1,a2,...,ak}开始，尝试在最后添加元素来扩展这个部分解，扩展之后，我们必须测试它是否为一个完整解，如果是的话，就输出这个解；如果不完整，我们必须检查这个部分解是否仍有可能扩展成完整解，如果有可能，递归下去；如果没可能，从a中删除新加入的最后一个元素，然后尝试该位置上的其他可能性。
用一个全局变量来控制回溯是否完成，这个变量设为finished，那么回溯框架如下，可谓是回溯大法之精髓与神器
boolfinished=false;
voidbackTack(intinput[],intinputSize,intindex,intstates[],intstateSize)
{
intcandidates[MAXCANDIDATE];
intncandidates;
if(isSolution(input,inputSize,index)==true)
{
processSolution(input,inputSize,index);
}
else
{
constructCandidate(input,inputSize,index,candidates,&ncandidates);
for(inti=0;i<ncandidates;i++)
{
input[index]=candidates[i];
backTack(input,inputSize,index+1);
if(finished)
return;
}
}
}
不拘泥于框架的形式，我们可以编写出如下代码：
#include<iostream>
usingnamespacestd;
charstr[]="abc";
constintsize=3;
intconstructCandidate(bool*flag,intsize=2)
{
flag[0]=true;
flag[1]=false;
return2;
}
voidprintCombine(constchar*str,bool*flag,intpos,intsize)
{
if(str==NULL||flag==NULL||size<=0)
return;
if(pos==size)
{
cout<<"{";
for(inti=0;i<size;i++)
{
if(flag[i]==true)
cout<<str[i]<<"";
}
cout<<"}"<<endl;
}
else
{
boolcandidates[2];
intnumber=constructCandidate(candidates);
for(intj=0;j<number;j++)
{
flag[pos]=candidates[j];
printCombine(str,flag,pos+1,size);
}
}
}
voidmain()
{
bool*flag=newbool[size];
if(flag==NULL)
return;
printCombine(str,flag,0,size);
delete[]flag;
}
采用回溯法框架来计算字典序排列：
#include<iostream>
usingnamespacestd;
charstr[]="abc";
constintsize=3;
voidconstructCandidate(char*input,intinputSize,intindex,char*states,char*candidates,int*ncandidates)
{
if(input==NULL||inputSize<=0||index<0||candidates==NULL||ncandidates==NULL)
return;
boolbuff[256];
for(inti=0;i<256;i++)
buff[i]=false;
intcount=0;
for(inti=0;i<index;i++)
{
buff[states[i]]=true;
}
for(inti=0;i<inputSize;i++)
{
if(buff[input[i]]==false)
candidates[count++]=input[i];
}
*ncandidates=count;
return;
}
boolisSolution(intindex,intinputSize)
{
if(index==inputSize)
returntrue;
else
returnfalse;
}
voidprocessSolution(char*input,intinputSize)
{
if(input==NULL||inputSize<=0)
return;
for(inti=0;i<inputSize;i++)
cout<<input[i];
cout<<endl;
}
voidbackTack(char*input,intinputSize,intindex,char*states,intstateSize)
{
if(input==NULL||inputSize<=0||index<0||states==NULL||stateSize<=0)
return;
charcandidates[100];
intncandidates;
if(isSolution(index,inputSize)==true)
{
processSolution(states,inputSize);
return;
}
else
{
constructCandidate(input,inputSize,index,states,candidates,&ncandidates);
for(inti=0;i<ncandidates;i++)
{
states[index]=candidates[i];
backTack(input,inputSize,index+1,states,stateSize);
}
}
}
voidmain()
{
char*candidates=newchar[size];
if(candidates==NULL)
return;
backTack(str,size,0,candidates,size);
delete[]candidates;
}
对比上述两种情形，可以发现唯一的区别在于全排列对当前解向量没有要求，而字典序对当前解向量是有要求的，需要知道当前解的状态！
八皇后回溯法求解：
#include<iostream>
usingnamespacestd;
intposition[8];
voidconstructCandidate(int*input,intinputSize,intindex,int*states,int*candidates,int*ncandidates)
{
if(input==NULL||inputSize<=0||index<0||candidates==NULL||ncandidates==NULL)
return;
*ncandidates=0;
boolflag;
for(inti=0;i<inputSize;i++)
{
flag=true;
for(intj=0;j<index;j++)
{
if(abs(index-j)==abs(i-states[j]))
flag=false;
if(i==states[j])
flag=false;
}
if(flag==true)
{
candidates[*ncandidates]=i;
*ncandidates=*ncandidates+1;
}
}
/*
cout<<"ncandidates="<<*ncandidates<<endl;
system("pause");*/
return;
}
boolisSolution(intindex,intinputSize)
{
if(index==inputSize)
returntrue;
else
returnfalse;
}
voidprocessSolution(int&count)
{
count++;
}
voidbackTack(int*input,intinputSize,intindex,int*states,intstateSize,int&count)
{
if(input==NULL||inputSize<=0||index<0||states==NULL||stateSize<=0)
return;
intcandidates[8];
intncandidates;
if(isSolution(index,inputSize)==true)
{
processSolution(count);
}
else
{
constructCandidate(input,inputSize,index,states,candidates,&ncandidates);
for(inti=0;i<ncandidates;i++)
{
states[index]=candidates[i];
backTack(input,inputSize,index+1,states,stateSize,count);
}
}
}
voidmain()
{
//初始化棋局
for(inti=0;i<8;i++)
position[i]=i;
intstates[8];
intcount=0;
backTack(position,8,0,states,8,count);
cout<<"count="<<count<<endl;
}
希望本文所述对大家C++程序算法设计的学习有所帮助。