首页 范文大全 古典文学 职场知识 中国文学 公文书信 外国名著 寓言童话 百家讲坛 散文/诗歌 美文欣赏 礼仪知识 民俗风情
  • 范文大全
  • 古典文学
  • 职场知识
  • 中国文学
  • 公文书信
  • 外国名著
  • 寓言童话
  • 百家讲坛
  • 散文/诗歌
  • 美文欣赏
  • 礼仪知识
  • 民俗风情
  • 谜语大全
  • 名言警句
    • 蒲公英阅读网 > 古典文学 > 正文

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

    时间：2021-05-14 00:13:55 来源：蒲公英阅读网 本文已影响人 蒲公英阅读网手机站

    相关热词搜索：回溯 贪心 算法

    　 实验三

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

    　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 背包问题，很好的解决了这些问题。也对自己的编程能力有了更好的提高，总之，这次试验收获很大！

  • [win7电脑怎么查看系统内存使用情况] win7
  • [毕业班主任意见范文]大学毕业生班主任意见
  • 八年级下册历史教案 八年级下册历史第三单
  • 怎么修复电脑错误711_电脑一开机连不上网络
  • 记账凭证是编制报表的直接依据 记账凭证编
  • 哄女友讲的睡前小故事_搞笑睡前故事大全
  • 比较成功的餐饮创业案例|餐饮营销方案成功
  • 【word文档打开出现应用程序错误怎么办】wo
  • 适合龙的传人的朗诵词_关于秋天的多人朗诵
    • 范文大全
    • 职场知识
    • 精美散文
    • 名著
    • 讲坛
    • 诗歌
    • 礼仪知识
    最新文章

    推荐访问

    大反思大讨论活动 保安全” 筑防线 “查思想 贡献伟大时代” “以青春之我 工作评议报告 创建活动综述 市社保局党支部 自述报告 “党员先锋示范岗” 党建德育工作 达标创星活动 “星级党支部”创建 评星定级管理 社会组织党支部 第四巡察组 新进年轻干部 委厅机关 党性教育培训班 履职能力建设专题培训班 新考录社区工作者 “头雁领航”重点培训班 党组织业务培训 能力提升培训会 赋能经济高质量发展 “五好”园区 三年攻坚行动 行政管理能力建设提升班 高质量发展能力提升培训班 市疾控系统 中基层管理人员 专业能力提升专题培训班 新发展预备党员 进驻工作 迎接审计组 讲评推进大会 “三抓三促”行动动员 “永不过时的红岩精神” 市委党史研究室 科学绿化现场会 深化以案促改 一体推进不敢腐不能腐不想腐 奋斗精神 专题辅导讲稿 坚守使命追求 涉密 《党史学习教育工作条例》 百年新征程 “百年定位” 党课教育

    本文实验三,,贪心算法与回溯法范文.doc由蒲公英阅读网整理提供，版权归原作者、原出处所有。

    Copyright © 蒲公英阅读网 All Rights Reserved.