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

《实验三 贪心算法与回溯算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、,temp,u,newdist;for(i=0;i

3、][j]n){//符号填充完毕sum++;//打印符号cout<<"第"<

4、[i][j]]<<"";cout<<"";}}elsefor(i=0;i<2;i++)第2页共2页{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;elsep[j][t-j+1]=0;count+=p[j][t-j+1];}if((count<=half)&&(t*(t+1)/2-count<=half)){//若符号统计未超过半数，并且另一种符号也未超过半数Backtrack(t+1)

5、;//在第一行增加下一个符号}for(j=2;j<=t;j++)//回溯，判断另一种情况count-=p[j][t-j+1];count-=i;}第2页共2页四、试验结果：第2页共2页