当前位置:首页 > 商业/管理/HR > 资本运营 > 《算法分析与设计》最优服务次序问题的答案
最优服务次序问题设有n个顾客同时等待同一项服务。顾客i需要的服务时间为ti,1=i=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。参考答案一、最优服务次序问题二、运行环境(软、硬件环境)运行软件:Window764位硬件:华硕PC机编写程序:C++语言编译环境:VC++6.0三、算法设计的思想首先,要使n个顾客平均等待时间最小,即为:让n个顾客等待服务时间总和最小。因为,平均等待时间=等待服务时间总和/n。接着,由于每个顾客i的服务时间为ti,要实现等待服务时间总和最小,应该尽可能安排ti值小的顾客,进行服务。因此,本题属于局部最优的设计问题,即为贪心算法。四、算法的流程图局部最优贪心算法第i个顾客等待时间总的等待时间,即最优解Tmin五、算法设计分析假设原问题的时间为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);顾客平均等待时间最小等待服务时间总和最小ti值小的顾客,先服务最优解min={t(1),t(2)..t(n)}T(i)=t(1)+t(2)+......+t(i)Tmin=n*t(1)+(n-1)*t(2)+...(n+1-i)*t(i)+......+2*t(n-1)+1*t(n)程序实现,引入Shell排序,实现数据从小到大排序由于,平均等待时间是n个顾客等待时间总和除以n,则本题转化为求使得顾客等待时间总和最小的服务次序问题。六、源代码#includefstream.h#includeiostream.h#includestdlib.h#includeiomanip.hlongn=-1;//顾客数为nlong*wait;//顾客各自等待时间waitvoidinputData(){//输入数据n,等待时间waitifstreamfin;fin.open(*input.txt’,los::nocreate);if(!fin){cout“FileOpenError!endl;return;}finn;wait==newlong[n];for(1ongi=0;in;i++){finwait[i];)fin.close0;}voidShellSort(long*x)(//Shell排序,实现数据从小到大排序longi,j,temp.gap=n/2;while(gap0){for(i=gap;in;i++){j=i-gap;while(j=0){if(x[j]x[j+gap]){temp=x[j];x[j]=x[j+gap];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;in;i++){ave+=1.0*(n-i)*x[i];}ave/=n;//求平均等待时间returnave;)voidoutputData(doubleout)(//输出结果ofstreamfout;fout.open(output.txt);foutsetiosflags(ios::fixed)setprecision(2)outendl;fout.close0;)voidmain0{//主调函数inputData();if(n!=-1)(doubleavewait=AveWait(wait);outputData(avewait):}}七、运行结果分析试验结果:input.txt:125622l9901002234334597810output.txt:532.00八、收获及体会本题将顾客平均等待时间最小,转化为服务等待时间总和最小。利用局部最优,通过贪心算法来解决该题。通过本题,也更深入了解贪心算法的本质,今后对于其他类似的局部最优问题、最优子结构问题,都可采用贪心算法解决。
本文标题:《算法分析与设计》最优服务次序问题的答案
链接地址:https://www.777doc.com/doc-5440054 .html