《算法分析与设计》最优服务次序问题的答案

最优服务次序问题设有n个顾客同时等待同一项服务。顾客i需要的服务时间为ti,1=i=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。参考答案一、最优服务次序问题二、运行环境（软、硬件环境）运行软件：Window7 64位硬件：华硕PC机编写程序：C+语言编译环境：VC+6.0三、算法设计的思想首先，要使n个顾客平均等待时间最小，即为：让n个顾客等待服务时间总和最小。因为，平均等待时间=等待服务时间总和/n。接着，由于每个顾客i的服务时间为ti,要实现等待服务时间总和最小，应该尽可能安排ti值小的顾客，进行服务。因此，本题属于局部最优的设计问题，即为贪心算法。4、 算法的流程图等待服务时间总和最小顾客平均等待时间最小最优解min = t(1),t(2).t(n)ti值小的顾客,先服务 局部最优贪心算法第i个顾客等待时间 总的等待时间，即最优解Tmin程序实现，引入Shell排序，实现数据从小到大排序Tmin=n*t(1)+(n-1)*t(2)+.(n+1-i)*t(i)+.+2*t(n-1)+1*t(n)T(i)=t(1)+t(2)+.+t(i)5、 算法设计分析假设原问题的时间为T，已经知道了某个最优服务系列，最优解为min=t(1)，t(2)，.，t(n)（其中t(i)为第i个客户需要的服务时间），那么每个客户需要的等待是时间为：T(1)=t(1)；T(2)=t(1)+t(2)；.T(n)=t(1)+t(2)+.+t(n)；那么，总的等待时间，即为最优解T min=n*t(1)+(n-1)*t(2)+(n-2)*t(3).+(n+1-i)*t(i)+.+2*t(n-1)+1*t(n)；由于，平均等待时间是n个顾客等待时间总和除以n，则本题转化为求使得顾客等待时间总和最小的服务次序问题。6、 源代码#include#include#include#includelong n=-1； /顾客数为nlong *wait； /顾客各自等待时间waitvoid inputData () /输入数据n，等待时间waitifstream fin；finopen(*inputtxt，los:nocreate)；if(!fin)cout“File Open Error!n；wait=new longn；for(1ong i=0；iwaiti；)finclose0；void ShellSort(long *x)( /Shell排序，实现数据从小到大排序long i，j，tempgap=n2；while(gap0)for(i=gap；i=0)if(xjxj+gap)temp=xj；xj=xj+gap；xj+gap=temp； /实现大小交换j=j-gap； elsej=-1；gap=gap2；*函数名：AveWait0描述：计算平均等待时问参数：各顾客等待时间*double AveWait(long *x)double ave=0.0；ShellSort(x)；for(long i=0；in；i+)ave+=1.0*(n-i)*xi；ave=n； /求平均等待时间return ave；)void outputData(double out)( /输出结果ofstream fout；foutopen(outputtxt)；foutsetiosflags(ios：fixed)setprecision(2)outendl；foutclose0；)void main0 /主调函数inputData()；if(n!=-1)(double avewait=AveWait(wait)；outputData(avewait)：7、 运行结果分析试验结果：inputtxt：12 56 22 l9 90 1002 234 33 45 97 810outputtxt：532008、 收获及体会本题将顾客平均等待时间最小，转