贪心算法日历调度问题.docx
《贪心算法日历调度问题.docx》由会员分享，可在线阅读，更多相关《贪心算法日历调度问题.docx（11页珍藏版）》请在冰点文库上搜索。
贪心算法日历调度问题
《数据结构课程设计》报告
题目：
贪心算法：
任务调度问题
一、简介
算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。
任何程序基本上都是要用特定的算法来实现的。
算法性能的好坏，直接决定了所实现程序性能的优劣。
贪心算法通过一系列的选择来得到的一个问题的解。
它所做的每一个选择都是当前的状态下某种意义的最好选择，即贪心选择。
希望通过每次所做的贪心选择导致最终结果是问题的一个最优解。
这种启发式的策略并不总能奏效，然而在许多情况下能达到预期的目的。
贪心算法采用的是逐步构造最优解的方法。
在每个阶段，都做出一个看上去最优的决策，做出贪心决策的依据称为贪心准则。
本实验的目的是设计一个程序，具体实验内容步骤包括排序、计算总的平均完成时间、输出调度结果。
因此，实验任务如下：
有n项任务，要求按顺序执行，并设定第i项任务需要t[i]单位时间。
如果任务完成的顺序为1，2，……，n，那么第i项任务完成的时间为c[i]=t[1]+……+t[i],平均完成时间（AverageCompletiontime）即为（c[1]+……+c[n]）/n.本题要求找到最小的任务平均完成时间。
输入要求：
输入数据中包含几个测试案例。
每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n个非负整数t（t≤1000000000），每一个数之间用空格相互隔开，以一个负数来结束输入。
输出要求：
对每一个测试案例，打印它的最小平均完成时间，并精确到0.01.每个案例对应的输出结果都占一行。
如输入某一个案例中任务数目n=0，则对应输出一个空行。
二、算法说明
1、贪心算法的基本要素：
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一个基本要素。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。
首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。
而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。
然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。
其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
最优子结构性质是一个问题的最优解包含着它的子问题的最优解时，这个性质是该问题可用贪心算法求解的一个关键特征。
2、贪心算法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，已尽可能快的求更好的解。
当达到算法中的某一部不能继续前进时，算法停止。
Huffman编码：
Huffman编码也是贪心算法思想的一个较为典型的应用，被广泛的用于文件压缩合文件传输中。
它的应用背景主要是为了减少文件传输或者文件保存中的大小。
在文件中，通常都含有出现次数很多的符号如数字、空格和换行符，而某些特定字符如z和x等出现次数相对很少，也就是说，在文件中，出现频率最大和最小的字符之间通常存在着很大的差别。
Huffman编码就是提供一种较好的编码方法，它能保证出现频率高的字符的编码较短，从而降低表示文件所需的总比特数
三、测试结果
本实验通过输入数据进行排序、计算总的平均完成时间以及输出调度结果来认识贪心算法。
正确的数据输入与其运行结果是：
异常的数据输入与其运z是：
异常的数据输入与其运行结果是：
四、分析与探讨
这个题目属于贪心算法应用中的任务条度文图。
要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间爱你之和。
这样给出的调度三按照最短作业优先进行安排的。
明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。
首先，输入的测试案例可以有很多组，每一个案例的输入格式都是第一行输入任务的个数，然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继续输入下一个案例的数据。
最后用一个任意的负数来表示输入的结束。
这样，由于案例的个数开始不得知，所以可以套用一个for循环，如图所示：
For（n=0;n>=0;）/*当n小于0的时候，推出程序*/
{
Scanf（“%1d”，&n）；
if（n>0）
{
建立一个具有n个元素的数组；
For（i=0;i{
继续读入这n个作业的完成时间；
}
进行主要的调度运算；
输出得到的最优调度结果；
}
elseif（n==0）
{
输出一个空行：
}
}
所以，对每组输入，其基本过程是：
读入n个任务的运行时间，进行主要的调度运算。
已经明确了采用最短作业优先的程序思想，所以主要的调度运算包括3个步骤：
（1）排序：
将数组按从小到大排序。
排序方法很多，如：
冒泡排序、希尔排序、堆排序）此题用希尔排序实现，如图5.14所示.
它的基本思想是：
先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=>>1），把数组的全部元素分成d1个组。
所以距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；然后，取第二个增量d2该方法实质上是一种分组插入排序方法。
图5.14希尔排序的实现
（2）计算总的平均完成时间：
排序完成后，数组a中的元素以升序的方式排序，因此总的平均完成时间为
ACT=∑a[i]×（n-i）/n
（3）输出调度结果：
由于输出的结果要求精确到0.01，所以输出的时候需要采用以下输出格式。
图5.15要求输出的精度为0.01
另外，程序实现的时候，要求用户一次可以输入一组或多组测试案例的数据，
当用户的输入完成后，程序经过计算在屏幕上分行显示这几个案例的结果。
因此
在有多个测试案例的情况下，需要设置一个数组，用来存放每一组测试案例的计算结果，如图5.16所示
图5.16有多个测试案例的处理方法
附录原代码
#include
#include
#include
usingnamespacestd;
voidShellsort（long*a,longn）;
intmain（）
{
longn,i,j;
long*a,*b;
doubler[100];/****用来存放每个测试案例的计算结果***/
j=0;/***记录测试案例的个数***/
/*****读入用户的输入，若当前输入为负数，则程序终止******/
for（n=0;n>=0;）
{
scanf（"%ld",&n）;
if（n>2000000）{
printf（"toomuchfortheproject!
\n"）;
exit（0）;
}
if（n>0）
{
b=（long*）malloc（n*sizeof（long））;
a=b;
for（i=0;i{
scanf（"%ld",b+i）;
/***检查输入的数据是否大于1000000000****/
if（*（b+i）>1000000000）{
printf（"toomuchfortheproject!
\n"）;
exit（0）;
}
/***对输入中出现任务时间为负数的异常处理******/
if（*（b+i）<0）
{
printf（"inputerror！
\n"）;
return0;
}
}
Shellsort（b,n）;
/*****计算平均完成时间*****/
for（i=n,r[j]=0.0;i>0;i--,a++）
{
r[j]+=（double）*a/（double）n*i;
}
j++;
free（b）;
}
/***当n为0时，标志相应的r数组值为－1，输出时碰到－1则输出一个空行***/
elseif（n==0）
{
r[j++]=-1;
}
}
for（i=0;i{
if（r[i]==-1）printf（"\n"）;/**输出一个空行**/
else
printf（"%.2f\n",r[i]）;/**输出的结果要求精确到0.01**/
}
return1;
}
/***希尔排序方法***/
voidShellsort（long*a,longn）
{
longi,j,increment;
longtemp;
/**第一个增量值为（n/2），以后每一次的增量都是上一个增量值的一半**/
for（increment=n>>1;increment>0;increment>>=1）
{
for（i=increment;i{
temp=*（a+i）;
for（j=i;j>=increment;j-=increment）
{
if（temp<*（a+（j-increment）））
*（a+j）=*（a+（j-increment））;
else
break;
}
*（a+j）=temp;
}
}
}
参考文献
[1]严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月
[2]谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月
[3]魏宝刚，陈越，王申康.数据结构与算法分析.杭州：
浙江大学出版社，2004
[4]书本教材C语言程序设计
[5]书本教材C++程序设计
升级会员 