计算机算法实验3 贪心算法 报告

1、算法设计与分析姓名： 班级：学号：课题：贪心算法指导教师： 2014/1/6目录1实验目的与要求12实验内容12.1基本题一：多机调度问题12.1.1问题概述12.1.2实验截图12.2提高题一：用贪心算法求解最小生成树22.2.1问题概述22.2.2实验截图22.3提高题二：汽车加油问题32.3.1问题概述32.3.2实验截图33实验心得4代码附后面1实验目的与要求1、熟悉多机调度问题的算法2、初步掌握贪心算法3、熟悉贪心算法的基本原理与适用范围4、使用贪心算法编程，求解最小生成树问题5、掌握汽车加油问题的算法2实验内容2.1基本题一：多机调度问题2.1.1问题概述要求给出一种作业调度方案，

2、使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。提示：1、把作业按加工所用的时间从大到小排序2、如果作业数目比机器的数目少或相等，则直接把作业分配下去3、 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。2.1.2实验截图 按照书本例题数据，7个作业分给3台机器，完成时间为17，实验结果如下：2.2提高题一：用贪心算法求解最小生成树2.2.1问题概述任选一种贪心算法（Prim或Kruskal），求解最小生成树。对算

3、法进行描述和复杂性分析。编程实现，并给出测试实例2.2.2实验截图 算法为Kruskal，选用书本例题数据，六个定点，十条边，求解结果如下：2.3提高题二：汽车加油问题2.3.1问题概述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。把两加油站的距离放在数组中，a1.n表示从起始位置开始跑，经过n个加油站，ak表示第k1个加油站到第k个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。2.3.2实验截图 输入3代表加油站段目，50代表加油后最大行驶距离结果如下：

4、再换一个例子：3实验心得这次算法实验的主要内容是贪心算法的使用，包括多机调度问题，最小生成树问题（采用Kruskal算法），汽车加油问题。贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法

5、不要回溯。贪心算法是算法的重要内容之一，可以高效地解决许多问题。采用贪心算法会比动态规划高效方便，如果都能解决某个问题的话。现在我学习贪心算法的时间还不长，理解还很浅显，以后要多加练习，这样才能做到熟练运用。基本题一：多机调度问题#include<iostream> using namespace std;#define N 10 typedef struct node int ID, time;/作业所需时间 jobnode; typedef struct Node int ID, avail;/ID 机器编号 avail 每次作业的初始时间 manode; manode mac

6、hineN; jobnode jobN; /* 找出下个作业执行机器 */manode* Find_min(manode a, int m) manode* temp = &a0; for (int i = 1; i<m; i+) if (ai.avail<temp->avail) temp = &ai;return temp; /* 对作业时间由大到小进行排序 */void Sort(jobnode t, int n) jobnode temp;for (int i = 0; i<n - 1; i+) for (int j = n - 1; j>

7、i; j-) if (jobj.time>jobj - 1.time) temp = jobj;jobj = jobj - 1; jobj - 1 = temp;void main() int n, m, temp, i; manode* ma;printf("输入作业数目(作业编号按输入顺序处理)n"); cin>>n;printf("输入相应作业所需处理时间:n"); for (i = 0; i<n; i+) cin>>jobi.time; jobi.ID = i + 1;printf("输入机器数目(机

8、器编号按输入顺序处理)n"); cin>>m;for (i = 0; i<m; i+)/给机器进行编号并初始化 machinei.ID = i + 1; machinei.avail = 0;putchar('n'); if (n <= m) printf("为每个作业分配一台机器,可完成任务!n"); return;Sort(job, n);for (i = 0; i<n; i+) ma = Find_min(machine, m);printf("将机器: M%d 从 %d -> %d 的时间段分配

9、给作业: %dn",ma->ID,ma->avail,ma->avail+jobi.time,jobi.ID); ma->avail+=jobi.time; temp = machine0.avail; for (i = 1; i<m; i+) if (machinei.avail>temp) temp = machinei.avail;putchar('n');printf("该批作业处理完成所需加工时间为: %dn", temp); 2提高题一：用贪心算法求解最小生成树/*该程序用贪心算法来求解最小生成树问题

10、采用贪婪准则：每次选择边权值最小边。如果该边加入后不构成环，则加入。*/#include <iostream> #include <string.h> using namespace std;int const CNST_Numgrphedge = 100;struct TTreeEdge/最小生成树的边类型 long v1, v2;/边的起点与终点编号 float weight;/边权 ;/*全局变量*/int ty = 0;/纪录返回边的个数（作为引用参数中数组的下标） /*该函数通过贪心算法求出最小生成树，返回值为最小生成树中的边（起点与终点编号与边权），通过引用

11、参数edge返回值*/void minspanningTree(TTreeEdge treeedge, int n, int e, TTreeEdge* edge)/*treeedge为图最初的起点与终点编号与边权n为顶点数e为边数引用参数edge为最小最小生成树中的边（起点与终点编号与边权）*/int i, j, u, v, p;int tempaCNST_Numgrphedge;/临时数组，该数组存储连通变量 long temp1, temp2;/改进的冒泡排序中所用参数 float temp3;/改进的冒泡排序中所用参数 int m, kk;/改进的冒泡排序中所用参数 /*按照边的权值从

12、小到大排序(采用改进的冒泡排序)*/m = e - 1;while (m>0)kk = 0;for (j = 0; j<m; j+)if (treeedgej.weight>treeedgej + 1.weight)temp1 = treeedgej.v1;treeedgej.v1 = treeedgej + 1.v1;treeedgej + 1.v1 = temp1;temp2 = treeedgej.v2;treeedgej.v2 = treeedgej + 1.v2;treeedgej + 1.v2 = temp2;temp3 = treeedgej.weight;tr

13、eeedgej.weight = treeedgej + 1.weight;treeedgej + 1.weight = temp3;kk = j;m = kk;/while /*初始化临时数组，该数组存储连通变量*/for (i = 0; i<e; i+)tempai = i;p = 1;for (j = 0; p<n; j+)/生成的边数如果小于顶点数，继续执行循环 u = treeedgej.v1; /边的起点 v = treeedgej.v2;/边的终点 /*如果起点与终点的连通变量不相等，则加入，将这条边的起点与终点编号与边权存入引用参数edge中,并改变临时数组的值*/

14、if (tempau != tempav)edgety.v1 = u;/将选中边的起点编号存入引用参数edge中 edgety.v2 = v;/将选中边的终点编号存入引用参数edge中 edgety.weight = treeedgej.weight;/将选中边的边权存入引用参数edge中 ty+;/边数加1 p+; /边数加1 for (i = 0; i<n; i+)if (tempai = tempav)tempai = tempau;/改变临时数组的值 void main()int i, e, n;int b;int Again = 0;char yn;TTreeEdge tree

15、edgeCNST_Numgrphedge;TTreeEdge edgeCNST_Numgrphedge;cout << "*" << endl;cout << "该程序用贪心算法来求解最小生成树问题。" << endl;cout << "采用贪婪准则：每次选择边权值最小边。" << endl;cout << "如果该边加入后不构成环，则加入。" << endl;cout << "*" &l

16、t;< endl;while (!Again)cout << "-" << endl;cout << "请输入图的顶点数:"cin >> n;/*判断输入图的顶点数的合法性！*/b = 0;while (!b)if (n<3)cout << "输入错误!顶点数不能小于3个!" << endl;cout << "请重新输入图的顶点数："cin >> n;elseb = 1;/while cout <<

17、; "请输入图的边数(最多" << CNST_Numgrphedge << " 个）："cin >> e;/*判断输入图的边数的合法性！*/b = 0;while (!b)if (e>(n*(n - 1) / 2)cout << "输入错误!顶点数为" << n << "的图其边数不能超过" << n*(n - 1) / 2 << "个!" << endl;cout <<

18、 "请重新输入图的边数(最多" << CNST_Numgrphedge << " 个）："cin >> e;elseb = 1;/while cout << "请输入图的各条边的起点位置、终点位置、边权（起/终点位置用数字输入）：" << endl;for (i = 0; i<e; i+)cin >> treeedgei.v1 >> treeedgei.v2 >> treeedgei.weight;/*判断输入图的各条边的起点位置、终

19、点位置、边权的合法性！*/b = 0;while (!b)if (treeedgei.v1<0 | treeedgei.v2<0 | treeedgei.weight<0)cout << "输入错误!边的起点位置、终点位置、边权不能小于0!" << endl;cout << "请重新输入该条边的起点位置、终点位置、边权（起/终点位置用数字输入）：" << endl;cin >> treeedgei.v1 >> treeedgei.v2 >> treeed

20、gei.weight;elseb = 1;/while /*调用函数*/minspanningTree(treeedge, n, e, edge);/*输出引用参数edge中存储的边的起点位置、终点位置、边权*/cout << "最小生成树所包含的边为：（依次为边的起点位置、终点位置、边权）" << endl;for (i = 0; i<ty; i+)cout << edgei.v1 << " " << edgei.v2 << " " << ed

21、gei.weight << endl;/*是否进行下一个最小生成树问题的求解*/cout << "n继续进行另一个最小生成树问题的解答吗?(Y/N)"cin >> yn;if (yn = 'Y' | yn = 'y')Again = 0;elseif (yn = 'N' | yn = 'n')Again = 1;else break;3提高题二：汽车加油问题#include<iostream>using namespace std;int main()int OilStationNum;/加油站的数目int MaxDist; /汽车加满油以后行驶的最大距离int DiscOfCar; /汽车一次加油后已经行驶的距离int Count;int * OilStationDist;printf("请