算法设计与分析课程大作业

::与信息工程专科与技术41、描述 42、分析 43.的描述 54、部分实现 65.86、时空效率分析 8二贪心多机81、描述 82、分析 99计复杂性分析 1112三回溯批1212131415时间复杂性分析 15四比较 16五课程学习总结 、从而提运行效益的关键环节之一。把各个分配到车间现有的设备上并确定它们的先后次序这是一项复杂的工本文就排序进行了研究通过对几个经典算法的分析讨论总结了各个算法对的求解过程并给出了每个算法的复杂及性能分析。关键词；动态规划；贪心算法；回溯法；1、描述给定n个，每个有两工序，分别在两台机器上处理。台机器次只能处理工序并且工序旦开始就必须进行下去直到完成个只有在机器1上的处理完成以后才能由机器2处理。假设已知i在机器j上需要的处理时间为。就是要求确定个的处理顺序使得尽快完成这n 个。2、分析直观上，个最优M1上会有机器空闲和积2种情况。在M1S中M2还在加tS所。T(N,0)。由的最优子结构性质可知，T(N,0)

min{ai1in

T(N

{i},bi

)}（1）

T(S

}ba})}i

i i2）N。将规模缩小。S2M1完max{t-ai,0}。3. 算法描述分析知流水定存满足Johnson法则且易由下面算法确定。流水Johnson算法：令N1

|],2},N2

|],2}；将依非减序；将依非增序；接种Johnson法则。4、部分算法实现intFlowShop(intn,inta[],intb[],intc[]){inti;Jobtype*d=newJobtype[n];for(i=0;i<n;i++){d[i].key=a[i]>b[i]?b[i]:a[i];//按Johnson法则分别取对应的b[i]或a[i]值作为关键字d[i].job=a[i]<=b[i];//给符合条件a[i]<b[i]的放入到N1子集标记为trued[i].index=i;}//对数组d按关键字升序进行排序intj=0,k=n-1;for(i=0;i<n;i++){if(d[i].job){c[j++]=d[i].index;//将排过序的数组d，取其中作业序号属于N1的从前面进入}else{c[k--]=d[i].index;//属于N2的从后面进入，从而实现N1的非减序排序，N2的非增序排序}}}j=a[c[0]];k=j+b[c[0]];for(i=1;i<n;i++){j+=a[c[i]];12]谁后完kj<k?k+b[c[i]]:j+b[c[i]];//计算优加工}deleted;returnk;}: 6、时空效率分析Flowshop的主要计算时间花在对作业集的排序上。wb所需要的计算时间为O(og)然是。二．贪心算法解多机调度1、描述nm台机器加工处理完成。约定，每个作业均可在任何NP,用贪心选择策略有时可以设计出较好的近似算法。::2、算法分析贪心算法只需按顺序以数组方式提供各作业的加工时间和机器近的机器，所需要的加工时间，即为最长作业所需时间。若作业数大于机器台数，将作业按加工时间的多少降序排序，以mm个机器，最小堆顶是即m部分算法实现typedefstructNodetypedefstructNode{ intID,avail;}manode;//ID号 avail每次作业的初始时间manodemachine[N];jobnodejob[N];/*找出下个作业执行机器*/manode*Find_min(manodea[],intm){ manode*temp=for(inti=1;i<m;i++){if(a[i].avail<temp->avail)temp=&a[i]; }returntemp; }/* voidSort(jobnodet[]intn){ jobnodetemp;for(inti=0;i<n-1;i++)for(intj=n-1;j>i;j--){ if(job[j].time>job[j-1].time){ temp=job[j];job[j]=job[j-job[j-1]=temp;}}}voidmain(){for(i=0;i<n;i++){ cin>>job[i].time;job[i].ID=i+1; ()\n");cin>>m;for(i=0;i<m;i++)//给机器进行编号并初始化{ machine[i].ID=i+1;machine[i].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%d\n",putchar('\n');printf(":%d\n",temp);}n≤m 有以次安排各法要o(1)。n>m ，排序耗O(nlogn)。初始化堆要。和put运共耗O(nlogm),因此法O(nlogn+nlogm)=O(nlogn)。: 三．回溯法解决批作业调度描述入：NMt[i],t[i]=xi个任务完成需要时间x，出：bestx[i]=xi个任务分::x：NMt[i]:ix[i]=j:Res[i]=j:ijtime_machine[i]:i1、搜索从开始点（根点）DFS搜索整2、每搜索完条time_min和Res[i]序列，开始结同同也成扩展点扩展点处向纵方向移至新点，并成新活点，也成扩展点。3、如3、如扩展点处不能再向纵方向扩展，则扩展点就成死点。活点成扩展点；直至找到或全部部分算法实现boolplacetest(intk){inttime_max_K=time_machine[1];for(inti=2;i<=K;i++){if(time_machine[i]>time_max_K)time_max_K=time_machine[i];}if(time_max_K>time_min)returnfalse;elsereturntrue;}voidBacktrack(intk,intt[],intx[]){if(k>N){inttime_max_K=time_machine[1];for(inti=2;i<=K;i++){if(time_machine[i]>time_max_K)time_max_K=time_machine[i];}if(time_max_K<time_min){time_min=time_max_K;for(inti=1;i<=N;i++)Res[i]=x[i] } }else{for(inti=1;i<=K;i++): {x[k{x[ki;//ki上面if(placetest(k)){time_machine[i]+=t[k];Backtrack(k+1,t,x);time_machine[i]-=t[k];}}运行结果时间复杂性分析题目:输油管道问题题目:输油管道问题由于没有使用限界函数进行优化，算法时间和空间复杂度呈指由于没有使用限界函数进行优化，算法时间和空间复杂度呈指数 级增长。所以该算法不适合较大规模的计算级增长。所以该算法不适合较大规模的计算。 蓝线表示机器数一定 M=3时，n增大时求解最佳调度对所消耗的时 间，该趋势随着指数增加。 四．作业调度算法比较 算法这是在只有两台设备情况下的最优排序算法，同时说明工件的第一道工序和最后一道工序的加工时间对排序的影响是主要的。贪心算法只需按顺序以数组方式提供各作业的加工时间和机O(nlogn)。算法解作业调度问题两个问题不同，两个是求所有作业在