实验三 贪心算法与回溯算法的设计与实现.doc

第页共NUMPAGES2页
实验三贪心算法与回溯算法的设计与实现
实验目的：
了解贪心算法的设计思路与设计技巧，了解最优子结构性质和贪心选择性质，如何证明局部最优解同时又是全局最优解；
了解回溯算法的原理、设计思路与步骤，掌握回溯算法搜索过程中，数据的组织结构、搜索策略。
试验内容：
1、单源最短路径、最小生成树、哈夫曼编码，运用贪心算法设计策略，选作其一；
2、符号三角形问题、旅行售货员问题、n后问题、运用回溯算法设计策略，任选其一。
三、核心程序源代码：
单源最短路径:
voidDijkstra(intv)
{
inti,j,temp,u,newdist;
for(i=0;i<N;i++)
{
dist[i]=c[v][i];
s[i]=false;
if(dist[i]==MAX)
prev[i]=-1;
elseprev[i]=v;
}
dist[v]=0;
s[v]=true;
for(i=0;i<N-1;i++)
{
temp=MAX;
u=v;
for(j=0;j<N;j++)
if(!s[j]&&(dist[j]<temp))
{
u=j;
temp=dist[j];
}
s[u]=true;
for(j=0;j<N;j++)
if((!s[j])&&(c[u][j]<MAX))
{
newdist=dist[u]+c[u][j];
if(newdist<dist[j])
{
dist[j]=newdist;
prev[j]=u;
}
}
}
}

符号三角形问题:
voidBacktrack(intt)
{
inti,j;
if(t>n)
{//符号填充完毕
sum++;//打印符号
cout<<"第"<<sum<<"个:\n";
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
cout<<"";
for(j=1;j<=n-i+1;j++)
cout<<c[p[i][j]]<<"";
cout<<"\n";
}
}
else
for(i=0;i<2;i++)
{
p[1][t]=i;
count+=i;
for(j=2;j<=t;j++)
{
if(p[j-1][t-j+1]==p[j-1][t-j+2])
p[j][t-j+1]=1;
else

p[j][t-j+1]=0;
count+=p[j][t-j+1];
}
if((count<=half)&&(t*(t+1)/2-count<=half))
{//若符号统计未超过半数，并且另一种符号也未超过半数
Backtrack(t+1);//在第一行增加下一个符号
}
for(j=2;j<=t;j++)//回溯，判断另一种情况
count-=p[j][t-j+1];
count-=i;
}
四、试验结果：