回溯算法经典问题算法：0-1背包,旅行商问题,N后问题,N排列,素数环,装载问题,批处理问题,.doc回溯算法经典问题算法：0-1背包,旅行商问题,N后问题,N排列,素数环,装载问题,批处理问题,.doc
0-1背包
float Bound(int i,int *v,int *w) { int left=c-cw; /*剩余容量*/
float b=(float)cv;
while (in) /*到叶结点*/
{ for (j=1;jbestv)/*搜索右子树*/
{ x[i]=0;
Backtrack(i+1,v,w,x);
}
}
}
旅行商问题
ublic static void ba...
回溯算法经典问题算法：0-1背包,旅行商问题,N后问题,N排列,素数环,装载问题,批处理问题,.doc
0-1背包
float Bound(int i,int *v,int *w) { int left=c-cw; /*剩余容量*/
float b=(float)cv;
while (i<=n&&w[i]<=left)
{ left-=w[i];
b+=v[i];
i++;
}
/*装满背包*/
if (i<=n)b+=(float)(v[i]/w[i])*left;
return b;
}
void Backtrack(int i,int *v,int *w,int *x)
{int j,t;
if(i>n) /*到叶结点*/
{ for (j=1;j<=n;j++)
bestx[j]=x[j];
bestv=cv;
}
else
{ if (cw+w[i]<=c)/*搜索左子树*/
{x[i]=1;
cw+=w[i];
cv+=v[i];
Backtrack(i+1,v,w,x);
cw-=w[i];
cv-=v[i];
}
if (Bound(i+1,v,w)>bestv)/*搜索右子树*/
{ x[i]=0;
Backtrack(i+1,v,w,x);
}
}
}
旅行商问题
ublic static void backtrack(int t) p
{ //到解空间数叶结点的处理
if(t > n - 1)
{ v += dist[0][x[n - 1]];
if(v < bestV)
{ bestV = v;
for(int i = 0; i < n; i++)
bestX[i] = x[i];
}
System.out.println(v);
v -= dist[0][x[n - 1]];
return;
}///////////////////////
for(int i = t; i < n; i++)
{ swap(x, i, t);
v += dist[x[t - 1]][x[t]];
//剪枝函数
if (v < bestV) backtrack(t + 1);
v - = dist[x[t - 1]][x[t]];
swap(x, i, t);
}
}//end
N后问题
Place(int k)
{
for(int j=1;j<=k;j++)
,if( asb(k-j)==asb(x[k]-x[j] ) )||(x[j]==x[k]) return false;,
else return true;
}
void Queen:Backtrack(int t) {
if(t>n) sum++;
else
for(int i=1;i<=n;i++)
{ x[t]=i;
if(Place(t)) Backtrack(t+1);
}
}
N排列
int perm(int b[], int i) { int k,j,temp;
if(i==num) //num即N
{ for(k=1;k<=num;k++)
cout<n)
{ if(isprime(a[1]+a[n]))
printresult();
return;
}
else
{
for(i=m;i<=n;i++)
{ swap(a[m],a[i]);
if(isprime(a[m-1]+a[m])) search(m+1);
swap(a[i],a[m]);
}
}//ENDELSE
}//END
装载问题
void Loading:Backtrack(int i) //搜索至第i 层
{ //到达叶节点
if(ibestw){for(j=1;j<=n;j++)bestw[j]=x[j]; bestw=cw;}
return;
}
//搜索子树
r - = w[i];
if(cw+w[i]<=c) //搜索左子树
{ x[i]=1; cw+=w[i];
Backtrack(i+1);
cw - = w[i];
}
if(cw+r>bestw) //搜索右子树
{ x[i]=0;
Backtrack(i+1);
}
r+=w[i];
}
批处理问题
public static void trackback(int i) {
if(i>n)
{ for(int j=1;j<=n;j++) bestx[j]=x[j];
bestf=f ;
}
else
for(int j=i;j<=n;j++)
{ f1+=M[x[j]] [1];//M[i][j]是第i个作业第j步需要时间
f2[i]=( (f2[i-1]>f1) ? f2[i-1]:f1 )+M[x[j]] [2];
f+=f2[i];
if(f
本文档为【回溯算法经典问题算法：0-1背包,旅行商问题,N后问题,N排列,素数环,装载问题,批处理问题,.doc】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483