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

《《算法分析与设计》最优服务次序问题的答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、最优服务次序问题设有n个顾客同时等待同一项服务。顾客i需要的服务时间为ti,1<=i<=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。参考答案一、最优服务次序问题二、运行环境（软、硬件环境）运行软件：Window764位硬件：华硕PC机编写程序：C++语言编译环境：VC++6.0三、算法设计的思想首先，要使n个顾客平均等待时间最小，即为：让n个顾客等待服务时间总和最小。因为，平均等待时间=等待服务时间总和/n。接着，由于每个顾客i的服务时间为ti,要实

2、现等待服务时间总和最小，应该尽可能安排ti值小的顾客，进行服务。因此，本题属于局部最优的设计问题，即为贪心算法。四、算法的流程图等待服务时间总和最小顾客平均等待时间最小最优解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)+......+

3、t(i)五、算法设计分析假设原问题的时间为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)；那么，总的等待时间，即为最优解Tmin=n*t(1)+(n-1)*t(2)+(n-2)*t(3)......+(n+1-i)*t(i)+......+2*t(n-1)+1*t(n)；由于，平

4、均等待时间是n个顾客等待时间总和除以n，则本题转化为求使得顾客等待时间总和最小的服务次序问题。六、源代码#include#include#include#includelongn=-1；//顾客数为nlong*wait；//顾客各自等待时间waitvoidinputData(){//输入数据n，等待时间waitifstreamfin；fin．open(*input．txt’，los::nocreate)；if(!fin){co

5、ut<<“FileOpenError!"<>n；wait==newlong[n]；for(1ongi=0；i>wait[i]；)fin．close0；}voidShellSort(long*x)(//Shell排序，实现数据从小到大排序longi，j，temp．gap=n／2；while(gap>0){for(i=gap；i=0){if(x[j]>x[j+gap]){temp=x[j]；x[j]=x[j+g

6、ap]；x[j+gap]=temp；//实现大小交换j=j-gap；}else{j=-1；}}}gap=gap／2；}}／**函数名：AveWait0描述：计算平均等待时问参数：各顾客等待时间**／doubleAveWait(long*x){doubleave=0.0；ShellSort(x)；for(longi=0；i

7、ut；fout．open("output．txt")；fout<

8、本题将顾客平均等待时间最小，转化为服务等待时间总和最小。利用局部最优，通过贪心算法来解决该题。通过本题，也更深入了解贪心算法的本质，今后对于其他类似的局部最优问题、最优子结构问题，都可采用贪心算法解决。