贪心算法多机调度实验报告

//多机调度问题/*贪心法求解多级调度问题的贪心策略师最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样就可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的时间。

按照最长处理时间作业优先的贪心测落，当m>n,时，只要将机器ide [0,ti)时间去见分配给作业j即可，当m<n时，首先将n个作业从大到小排序，然后依次顺序将作业分配给空闲的处理机算法伪代码将数组t[n]从大到小排序，对应的作业序号存储在数组p[n]中；将数组d[m]初始化为零3：for（i0;i<=m;i++)3.1:s[i]={p[i]}:将m个作业分配给m个机器3.2 d[i]=t[i];for(i=m+1;i<=n;i++)4.1 j=数组d[m]中最小值对应的下标；//j为最先空闲的机器序号4.2 s[j]=s[j]+{p[i]};//将作业分配给最先空闲的的机器j4.3 d[j]=d[j]+d[t];//机器j将在d[j]后空闲*/#include<iostream>using namespace std;void lowsort(int *t,int *p,int n)//将数组t[n]按从小到大的顺序排序，相应的任务编号数组p[n]也要随之改变{int index;for(int i=0;i<n;i++){index=i;for(int j=i+1;j<n;j++){if(t[index]<t[j])index=j;}if(index!=i){int temp;temp=t[index];t[index]=t[i];t[i]=temp;temp=p[i];p[i]=p[index];p[index]=temp;}}int find(int *d,int m){int min=d[0];int k;for(int i=0;i<m;i++){if(d[i]<min){min=d[i];k=i;}}return k;}void ajust(int *t,int *d,int *p,int *s,int n,int m){lowsort(t,p,n);for(int i=0;i<m;i++){d[m]=0;}for(i=0;i<m;i++){s[i]=p[i];cout<<"机器"<<i+1<<"做了任务"<<p[i]<<endl;d[i]=t[i];}for(i=m;i<n;i++){int j=find(d,m);//查找数组d[m]中最小值对应的下标s[j]=s[j]+p[i];cout<<"机器"<<j+1<<"做了任务"<<p[i]<<endl;d[j]=d[j]+t[i];}}void main()int n,m;cout<<"输入任务数量"<<endl;cin>>n;cout<<"输入机器个数"<<endl;cin>>m;int *t=new int [n];int *s=new int [n];int *d=new int [m];int *p=new int[n];cout<<"输入任务编号"<<endl;for(int k=0;k<n;k++)cin>>p[k];cout<<"每件任务所花费的时间"<<endl;for(int i=0;i<n;i++)cin>>t[i];ajust(t,d,p,s,n,m);}。

贪⼼算法-多机调度问题题⽬：要求给出⼀种作业调度⽅案，使所给的n个作业在尽可能短的时间内由m台机器加⼯处理完成。

约定，每个作业均可在任何⼀台机器上加⼯处理，但未完⼯前不允许中断处理。

作业不能拆分成更⼩的⼦作业。

这个问题是⼀个NP完全问题，到⽬前为⽌还没有⼀个有效的解法。

对于这⼀类问题，⽤贪⼼选择策略有时可以设计出较好的近似算法。

可以考虑以下的贪⼼策略：（1）最长处理时间作业优先的贪⼼选择策略。

（2）最短处理时间作业优先的贪⼼选择策略。

（3）作业到达时间优先的贪⼼选择策略。

假设7个独⽴的作业由3台机器加⼯处理，各作业所需的处理时间为：{2，14，4，6，16，5，3}，写出以上算法求解此问题的结果。

#include<iostream>#include<algorithm>#define T 3//处理器using namespace std;bool comps(int a,int b){return a>b;}int sum(int w[],int n){int i;int time[101]={0};for(i = 0;i < n;i++){*min_element(time,time+T)+=w[i];//m是机器数，依次对m台机器添中最⼩的加speed}cout<<endl;return *max_element(time,time+T);}void longWork(int w[],int n)//最长处理时间作业优先{sort(w,w+n,comps);cout<<" 最长处理时间作业优先策略的时间为:"<<sum(w,n)<<endl;}void shortWork(int w[],int n)//最短处理时间作业优先{sort(w,w+n);cout<<" 最短处理时间作业优先策略的时间为:"<<sum(w,n)<<endl;}void arrivedT(int w[],int n)//作业到达时间优先{cout<<" 作业到达时间优先策略的时间为:"<<sum(w,n)<<endl;}int main(){int n=7;int a1[7]={2,14,4,6,16,5,3};int a2[7];int a3[7];memcpy(a2,a1,sizeof(a2));memcpy(a3,a1,sizeof(a3));longWork(a1,n);shortWork(a2,n);arrivedT(a3,n);return 0;}注：*min_element ：找最⼩元素*max_element：找最⼤元素。

《算法设计与分析》实训实验报告日期：2016年6月27日电子信息工程学院【问题描述】1、把作业按加工所用的时间从大到小排序2、如果作业数目比机器的数目少或相等，则直接把作业分配下去3、如果作业数目比机器的数目多，则每台机器上先分配一个作业【算法设计】运用贪心算法解决多机调度问题【算法实现】packagecom.test;importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.Scanner;public class Duojidiaodu {public static void main(String[] args) {// TODO Auto-generated method stubBufferedReaderbr=new BufferedReader(new InputStreamReader(System.in));try {System.out.println("请输入机器个数：");intjiqigeshu=Integer.parseInt(br.readLine());System.out.println("请输入作业个数：");intzuoyegeshu=Integer.parseInt(br.readLine());Start start=new Start(jiqigeshu, zuoyegeshu);//指明有几台机器以及几道作业start.show();//显示每台机器都有哪些作业} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();}finally{if(br!=null)try {br.close();} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();}}}}classJiqiManger{ArrayList<Jiqi> al=new ArrayList<Jiqi>();public void addjiqi(Jiqijiqi){this.al.add(jiqi);}publicJiqigetjiqi(int id){for(int i=0;i<this.al.size();i++){if(this.al.get(i).getId()==id){returnthis.al.get(i);}}return null;}}classJiqi{privateint id;privateArrayList<Zuoye> al;privateintzongshaoshi;publicJiqi(int id) {this.id=id;al=new ArrayList<Zuoye>();}publicintgetId(){return this.id;}public void addzuoye(Zuoyezuoye){this.al.add(zuoye);this.zongshaoshi+=zuoye.getHaoshi();}publicArrayList<Zuoye>getZuoye(){return this.al;}publicintgetZonghaoshi(){returnthis.zongshaoshi;}}classZuoyeManger{ArrayList<Zuoye>zuoye=new ArrayList<Zuoye>();public void addzuoye(Zuoyezuoye){this.zuoye.add(zuoye);}public void paixu(){Object[] temp=this.zuoye.toArray();for(int i=0;i<temp.length-1;i++)for(int j=i+1;j<temp.length;j++){if(((Zuoye)temp[i]).getHaoshi()<((Zuoye)temp[j]).getHaoshi()){Zuoyezuoye=(Zuoye)temp[i];temp[i]=temp[j];temp[j]=zuoye;}}this.zuoye.clear();for(int i=0;i<temp.length;i++)this.zuoye.add(((Zuoye)temp[i]));}publicZuoyegetZuoye(int index){returnthis.zuoye.get(index);}}classZuoye{privateint id;privateinthaoshi;publicZuoye(int id , inthaoshi ) {this.id=id;this.haoshi=haoshi;}publicintgetHaoshi(){returnthis.haoshi;}publicintgetId(){return this.id;}}class Start{privateJiqiMangerjiqiManger=null;privateZuoyeMangerzuoyeManger=null;privateintjiqigeshu,zuoyegeshu;public Start(intjiqigeshu , intzuoyegeshu) {jiqiManger=new JiqiManger();zuoyeManger=new ZuoyeManger();this.jiqigeshu=jiqigeshu;this.zuoyegeshu=zuoyegeshu;Jiqijiqi;Zuoyezuoye;for(int i=0;i<jiqigeshu;i++){jiqi=new Jiqi(i+1);jiqiManger.addjiqi(jiqi);}for(int i=0;i<zuoyegeshu;i++){inthaoshi;Scanner sc=new Scanner(System.in);System.out.println("请输入第"+(i+1)+"号作业的时间:");haoshi=sc.nextInt();zuoye=new Zuoye(i+1, haoshi);zuoyeManger.addzuoye(zuoye);}this.zuoyeManger.paixu();this.fenfa();}private voidfenfa(){int index=0;for(int i=0;i<this.jiqigeshu;i++){jiqiManger.getjiqi(i+1).addzuoye(zuoyeManger.getZuoye(index++));}while(index<this.zuoyegeshu){if(this.getJiqi()==null){System.out.println("对不起，没有机器可以分发作业！");break;}this.getJiqi().addzuoye(zuoyeManger.getZuoye(index++));}}privateJiqigetJiqi(){if(this.jiqiManger.getjiqi(1)==null)return null;int min=jiqiManger.getjiqi(1).getZonghaoshi();intminindex=1;for(int i=1;i<this.jiqigeshu;i++){if(jiqiManger.getjiqi(i+1).getZonghaoshi()<min){min=jiqiManger.getjiqi(i+1).getZonghaoshi();minindex=i+1;}}returnjiqiManger.getjiqi(minindex);}public void show(){ArrayList<Zuoye> al=null;for(int i=0;i<this.jiqigeshu;i++){al=jiqiManger.getjiqi(i+1).getZuoye();System.out.print(i+1+"号机器包含的作业有：{");for(int j=0;j<al.size();j++){if(j==(al.size()-1))System.out.println(al.get(j).getId()+"号作业}");elseSystem.out.print(al.get(j).getId()+"号作业,");}}}}【运行结果】。

贪心算法在多机调度问题中的应用
贪心算法在多机调度问题中可以应用于任务调度和资源分配的问题。

在多机调度问题中，我们通常需要将一组任务分配到多台机器上，并优化某个指标（如任务完成时间的最小化、机器的负载均衡等）。

贪心算法在多机调度问题中的应用可以通过以下步骤进行：
1. 确定任务的排序方式：根据任务的一些特征，如任务的处理时间、优先级等，确定一种排序方式。

例如，可以按照任务的处理时间递增顺序进行排序。

2. 初始化机器的状态：在开始调度之前，需要初始化每台机器的状态，如设置机器的剩余处理时间、当前任务等。

3. 贪心选择：从排序后的任务列表中，依次选择任务进行分配。

通过贪心选择，选择当前能够使得指标最小化的任务，并将任务分配给剩余处理时间最短的机器。

4. 更新机器状态：根据分配给机器的任务，更新机器的状态，如更新剩余处理时间、当前任务等。

5. 重复步骤3和步骤4，直到所有任务被分配完毕。

贪心算法在多机调度问题中的应用的核心思想是每次选择局部最优解，并希望通过不断地选择局部最优解，最终得到全局最
优解。

然而，需要注意的是，贪心算法并不能保证一定能够得到全局最优解，因此需要根据具体的问题进行分析和验证。

《算法设计与分析》课程实验报告实验序号：07实验项目名称：实验8 贪心算法（一）一、实验题目1.删数问题问题描述：键盘输入一个高精度的正整数N（不超过250 位），去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。

编程对给定的N 和k，寻找一种方案使得剩下的数字组成的新数最小。

若输出前有0则舍去2.区间覆盖问题问题描述：设x1,x2,...xn是实轴上的n个点。

用固定长度为k的闭区间覆盖n个点，至少需要多少个这样的固定长度的闭区间？请你设计一个有效的算法解决此问题。

3.会场安排问题问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

设计一个有效的贪心算法进行安排。

（这个问题实际上是著名的图着色问题。

若将每一个活动作为图的一个顶点，不相容活动间用边相连。

使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。

）4.导弹拦截问题问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

给定导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

二、实验目的（1）通过实现算法，进一步体会具体问题中的贪心选择性质，从而加强对贪心算法找最优解步骤的理解。

（2）掌握通过迭代求最优的程序实现技巧。

（3）体会将具体问题的原始数据预处理后（特别是以某种次序排序后），常能用贪心求最优解的解决问题方法。

三、实验要求（1）写出题1的最优子结构性质、贪心选择性质及相应的子问题。

（2）给出题1的贪心选择性质的证明。

（3）（选做题）：写出你的算法的贪心选择性质及相应的子问题，并描述算法思想。

一、实验背景贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。

贪心算法并不保证能获得最优解，但往往能获得较好的近似解。

在许多实际应用中，贪心算法因其简单、高效的特点而被广泛应用。

本实验旨在通过编写贪心算法程序，解决经典的最小生成树问题，并分析贪心算法的优缺点。

二、实验目的1. 理解贪心算法的基本原理和应用场景；2. 掌握贪心算法的编程实现方法；3. 分析贪心算法的优缺点，并尝试改进；4. 比较贪心算法与其他算法在解决最小生成树问题上的性能。

三、实验内容1. 最小生成树问题最小生成树问题是指：给定一个加权无向图，找到一棵树，使得这棵树包含所有顶点，且树的总权值最小。

2. 贪心算法求解最小生成树贪心算法求解最小生成树的方法是：从任意一个顶点开始，每次选择与当前已选顶点距离最近的顶点，将其加入生成树中，直到所有顶点都被包含在生成树中。

3. 算法实现（1）数据结构- 图的表示：邻接矩阵- 顶点集合：V- 边集合：E- 已选顶点集合：selected- 最小生成树集合：mst（2）贪心算法实现```def greedy_mst(graph):V = set(graph.keys()) # 顶点集合selected = set() # 已选顶点集合mst = set() # 最小生成树集合for i in V:selected.add(i)mst.add((i, graph[i]))while len(selected) < len(V):min_edge = Nonefor edge in mst:u, v = edgeif v not in selected and (min_edge is None or graph[u][v] < graph[min_edge[0]][min_edge[1]]):min_edge = edgeselected.add(min_edge[1])mst.add(min_edge)return mst```4. 性能分析为了比较贪心算法与其他算法在解决最小生成树问题上的性能，我们可以采用以下两种算法：（1）Prim算法：从任意一个顶点开始，逐步添加边，直到所有顶点都被包含在生成树中。

（贪⼼）多机调度问题某⼯⼚有n个独⽴的作业，由m台相同的机器进⾏加⼯处理。

作业i所需的加⼯时间为ti，任何作业在被处理时不能中断，也不能进⾏拆分处理。

现⼚长请你给他写⼀个程序：算出n个作业由m台机器加⼯处理的最短时间。

输⼊第⼀⾏T（1<T<100)表⽰有T组数据。

每组测试数据的第⼀⾏分别是整数n，m（1<=n<=10000，1<=m<=100），接下来的⼀⾏是n个整数ti（1<=t<=100)。

输出所需的最短时间样例输⼊22 21 56 32 5 13 15 16 20样例输出528这并不是⼀道oj上的题⽬，反正我是没找到。

应该属于⼀类题⽬。

解题思路就是贪⼼的思想。

我们现将所有的时间排序。

第⼀种情况：n<=m 时间最长的⼯作就是我们需要求解的总时间。

第⼆种情况：n>m这时候我们就将m个机器分配给前m个时间最长的⼯作，直到有机器空闲下来，我们将闲下的机器继续向后分配。

直到分配到没有⼯作可做了。

当前的时间再加上还没有做完的⼯作的最长时间就是我们所要求的总时间。

代码：1 #include<iostream>2 #include<stdio.h>3 #include<algorithm>4 #include<string.h>5using namespace std;6int a[1005],b[1005];7bool cmp(int a,int b){8return a>b;9 }10int main(){11int n,m;12int T;13 cin>>T;14while(T--){15int n,m;16 cin>>n>>m;17for(int i=0;i<n;i++){18 scanf("%d",a+i);19 }20 memset(b,0,sizeof(b));21 sort(a,a+n,cmp);22if(n<=m){23 cout<<a[0]<<endl;24continue;25 }else{26int sum=0;27int now=m;28while(now<n){29 sum++;30int cnt=0; //cnt是这分钟结束后有⼏台机器空闲下来31for(int i=0;i<now;i++){32 b[i]++;33if(b[i]==a[i]){34 cnt++;35 }36 }37 now+=cnt;38 }39int mx=0;40for(int i=0;i<n;i++){41if(a[i]>b[i])42 mx=max(mx,a[i]-b[i]); //找出还没做完的⼯作的最长时间43 }44 cout<<sum+mx<<endl;45 }46 }47return0;48 }。

一、实验目的1. 理解多机调度的基本概念和原理；2. 掌握多机调度算法的设计与实现；3. 分析和比较不同调度算法的性能。

二、实验环境1. 操作系统：Windows 10；2. 编程语言：Python3.8；3. 调度算法：先来先服务（FCFS）、最短作业优先（SJF）、优先级调度（Priority）。

三、实验内容1. 定义进程结构体：包含进程ID、到达时间、运行时间、优先级等属性。

2. 实现多机调度算法：（1）先来先服务（FCFS）算法：a. 按进程到达时间顺序排列进程队列；b. 循环遍历进程队列，依次执行进程；c. 每个进程执行完毕，更新完成时间。

（2）最短作业优先（SJF）算法：a. 按进程运行时间顺序排列进程队列；b. 循环遍历进程队列，依次执行进程；c. 每个进程执行完毕，更新完成时间。

（3）优先级调度（Priority）算法：a. 按进程优先级顺序排列进程队列；b. 循环遍历进程队列，依次执行进程；c. 每个进程执行完毕，更新完成时间。

3. 分析和比较不同调度算法的性能：（1）计算平均周转时间：完成时间 - 到达时间；（2）计算平均带权周转时间：平均周转时间 / 平均运行时间；（3）计算吞吐量：单位时间内完成的进程数量。

四、实验结果与分析1. FCFS算法：- 平均周转时间：20- 平均带权周转时间：1.2- 吞吐量：52. SJF算法：- 平均周转时间：16- 平均带权周转时间：0.96- 吞吐量：53. Priority算法：- 平均周转时间：18- 平均带权周转时间：1.09- 吞吐量：5通过对比分析，SJF算法在平均周转时间和平均带权周转时间方面均优于FCFS算法和Priority算法，且吞吐量相同。

这表明SJF算法在多机调度中具有较好的性能。

五、实验总结1. 本实验通过Python编程实现了多机调度算法，加深了对多机调度原理的理解；2. 通过对比分析不同调度算法的性能，为实际应用提供了参考；3. 实验结果表明，SJF算法在多机调度中具有较高的性能。

实验三贪心算法一、实验目的与要求1、熟悉多机调度问题的算法；2、初步掌握贪心算法；二、实验题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。

作业不能拆分成更小的子作业。

三、实验提示1、把作业按加工所用的时间从大到小排序2、如果作业数目比机器的数目少或相等，则直接把作业分配下去3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。

# include <iostream># include <iomanip>using namespace std;typedef struct Job //作业{int ID;int time;}Job;typedef struct JobNode //作业链表的节点{int ID;int time;JobNode *next;}JobNode,*pJobNode;typedef struct Header //链表的表头{int s; //处理机上的时间；JobNode *next;}Header,pHeader;int main(){void QuickSort(Job *job,int left,int right); //将job时间排序void outSort(Job *job,int n); //输出排序void display(Header *M,int m); //输出每个每台机器处理的工作序号数int SelectMin(Header *M,int m); //分配作业时选取机器函数；void solve(Header *head,Job*job,int n,int m); //作业分配函数；int m,n;cout<<"\t\t《多机调度问题》\n";cout<<"请输入机器台数m:";cin>>m;Header *head=new Header [m]; //动态构建数组结构体，用于记录机器的作业时间；cout<<"请输入作业个数n:";cin>>n;Job *job=new Job [n]; //动态构建作业的数组结构体；cout<<"\n请按序号输入每个作业调度所需时间time：";for(int i=0;i<n;i++){cin>>job[i].time;job[i].ID=i;}QuickSort(job,0,n-1); //作业排序outSort(job,n); //输出排序solve(head,job,n,m); //作业分配display(head,m); //输出分配cout<<endl<<endl;return 0;}int SelectMin(Header* M,int m) //选择s最小的机器序号k;{int k=0;for(int i=1;i<m;i++){if(M[i].s<M[k].s)k=i; //k记录S最小的序号；}return k;}void QuickSort(Job *job,int left,int right) //小到大，排序{int middle=0,i=left,j=right;Job itemp;middle=job[(left+right)/2].time;do{while((job[i].time>middle)&&(i<right))i++;while((job[j].time<middle)&&(j>left))j--;if(i<=j){itemp=job[j];job[j]=job[i];job[i]=itemp;i++;j--;}}while(i<=j);if(left<j)QuickSort(job,left,j);if(right>i)QuickSort(job,i,right);}void display(Header *M,int m) //作业分配输出函数；{JobNode *p;for(int i=0;i<m;i++){cout<<"\n第"<<i<<"台机器上处理的工作序号：";if(M[i].next==0)continue;p=M[i].next;do{cout<<p->ID<<' ';p=p->next;}while(p!=0);}}void outSort(Job *job,int n) //作业时间由大到小排序后输出函数；{cout<<"\n按工作时间由大到小为:\n时间：\t";for(int i=0;i<n;i++)cout<<setw(4)<<job[i].time;cout<<"\n序号：\t";for( i=0;i<n;i++)cout<<setw(4)<<job[i].ID;}void solve(Header *head,Job*job,int n,int m) //作业分配函数；{int k;for(int i=0;i<m&&i<n;i++){JobNode *jobnode=new JobNode;jobnode->time=job[i].time;jobnode->ID=job[i].ID;jobnode->next=0;head[i].s=jobnode->time;head[i].next=jobnode;}if(i<=m) //n<m的情况续处理；{for(i;i<m;i++){head[i].s=0;head[i].next=0;}}if(n>m){for(i;i<n;i++){JobNode *p;JobNode *jobnode=new JobNode;jobnode->time=job[i].time;jobnode->ID=job[i].ID;jobnode->next=0;k=SelectMin(head,m);p=head[k].next;head[k].s+=jobnode->time;while(p->next!=0)p=p->next;p->next=jobnode;}}}运行结果：提高题一：用贪心算法求解最小生成树一、实验要求与目的1、熟悉贪心算法的基本原理与适用范围。