实验三,,贪心算法与回溯法范文.doc

　 实验三

　贪心算法与回溯法 一、 实验目的 ：

　1、理解贪心算法与回溯法的概念； 2、掌握贪心算法与回溯法的基本要素； 3、掌握贪心算法与回溯法的解题步骤与算法柜架； 4、通过应用范例学习贪心算法与回溯法的设计技巧与策略； 二、 实验 内容及 要求 ：

　1． 使用贪心算法解决最小生成树问题。

　2.

　使用回溯法解决 0-1 背包问题。

　3． 通过上机实验进行贪心算法与回溯算法实现。

　4.

　保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

　三、 实验 原理：

　1 1 、 贪心算法 ：

　贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

　2 2 、贪心算法的基本思想：

　 1）建立数学模型来描述问题。

　2）把求解的问题分成若干个子问题。

　3）对每一子问题求解，得到子问题的局部最优解。

　4）把子问题的解局部最优解合成原来解问题的一个解。

　3 3 、 回溯法：

　回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树

　 的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

　4 4 、 回溯法的 基本思想：

　确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

　 运用回溯法解题通常包含以下三个步骤：

　 1）针对所给问题，定义问题的解空间；

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

　 3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索； 四、程序代码：

　贪心算法求最小生成树: #include"stdio.h" int point[100],key_point[100],tree[100][100]; //定义三个数组用于存放关键点和最小生成树 int INT_MAX=0x7fff; void prim(int end,int V);

　 //prim 算法函数 int main() {

　int V,E;

　 //定义顶点数 V 和边数 E

　int i,j;

　int start,end,distance;

　 //定义开始顶点 start 和结束顶点end，以及他们的权值 distance

　printf("请输入连通带权图的顶点数和边数：");

　while(scanf("%d%d",&V,&E))

　 //开始输入你要求最小生成树的顶点数和边数

　{

　 printf("\n------------------------------------");

　 for(i=1;i<=V;i++)

　 {

　for(j=1;j<=V;j++)

　 tree[i][j]=INT_MAX;

　 }

　 printf("\n 请输入%d 条边的起点和终点，以及权值。\n",E);

　 printf("\n----------------------------------------\n");

　 int x=1;

　 //用 x 记录输入的边数

　 while(E--)

　 {

　 printf("第%d 条边的起点：终点：权值：",x);

　scanf("%d%d%d",&start,&end,&distance);

　//记录输入的起点、终点、权值

　 tree[start][end]=tree[end][start]=distance;

　 x=x+1;

　 }

　 prim(1,V);

　//调用 prim 计算最小生成树

　 printf("\n");

　}

　return 0; } void prim(int end,int V) {

　int min;

　//定义权值最小值 min

　for(int i=1;i<=V;i++)

　{

　 point[i]=end;

　 key_point[i]=tree[end][i];

　}

　key_point[end]=0;

　 printf("该最小生成树的画法为：\n");

　for(int i=2;i<=V;i++)

　{

　 min= INT_MAX;

　 for(int j=1;j<=V;j++)

　if(key_point[j]>0 && key_point[j]<min)

　{

　 end=j;

　 min=key_point[j];

　}

　 printf("起点%d-->终点%d 连通\n",point[end],end);

　//输出最小生成树的连通边

　 key_point[end]=0;

　 for(int j=1;j<=V;j++)

　 //继续判断条件

　if(tree[end][j]<key_point[j])

　 point[j]=end,key_point[j]=tree[end][j];

　} } 回溯法解决 0-1 背包问题: #include<iostream> using namespace std; double c;//背包容量 int n; //物品数 double w[100];//物品重量数组 double p[100];//物品价值数组 double cw=0;//当前重量 double cp=0;//当前价值 double bestp=0;//当前最优值 double bound(int i) { double cleft,b;

　//计算上界

　cleft=c-cw;//剩余容量

　b=cp;

　//以物品单位重量价值递减序装入物品

　while(i<=n&&w[i]<=cleft)

　{

　cleft-=w[i];

　b+=p[i];

　i++;

　}

　//装满背包

　if(i<=n)

　 b+=p[i]*cleft/w[i];

　return b; } void Backtrack(int i) {

　 if(i>n)

　 {

　if(cp>bestp)

　bestp=cp;

　return;

　 }

　 if(cw+w[i]<=c) //搜索左子树

　 {

　cw+=w[i];

　cp+=p[i];

　Backtrack(i+1);

　cp-=p[i];

　cw-=w[i];

　 }

　if(bound(i+1)>bestp)//搜索右子树

　 Backtrack(i+1); }

　 double Knapsack (double pp[],double ww[],double d) {

　int i;

　double TP=0,TW=0;

　cw=0.0;cp=0.0;bestp=0.0;//计算所有物品的重量及价值

　for(i=1;i<=n;i++)

　{

　 TP=TP+pp[i];

　 TW=TW+ww[i];

　}

　if(TW<=d)//所有物品装入背包

　 bestp=TP;

　else

　{Backtrack(1);

　}

　return bestp; }; int main() {

　 int i,j;

　double t,a,x[100];

　cout<<"请输入物品种类数和最大载重量："<<endl;

　cin>>n;cin>>c;

　cout<<"请输入各物品重量："<<endl;

　for(i=1;i<=n;i++)

　 cin>>w[i];

　cout<<"请输入各物品价值："<<endl;

　for(i=1;i<=n;i++)

　 cin>>p[i];

　//排序

　for(i=1;i<=n;i++)

　 x[i]=p[i]/w[i];

　for(i=1;i<=n;i++)

　 for(j=i+1;j<=n;j++)

　 if(x[i]<x[j])

　 { t=x[i];

　x[i]=x[j];

　x[j]=t;

　a=p[i];

　p[i]=p[j];

　p[j]=a;

　a=w[i];

　w[i]=w[j];

　w[j]=a;

　 }

　Knapsack(p,w,c);

　cout<<"结果："<<endl;

　cout<<bestp<<endl;

　return 0; } 五、结果运行与分析：

　贪心算法结果：

　 回溯法解决 0-1 背包问题：

　六、心得与体会：

　通过本次试验，我对算法分析设计里的贪心算法和回溯法有了更深的了解，用贪心算法求最小生成树问题，用回溯法解决 0 0- -1 1 背包问题，很好的解决了这些问题。也对自己的编程能力有了更好的提高，总之，这次试验收获很大！

推荐访问:回溯 贪心 算法