用贪心算法求解最优服务次序问题.doc

《用贪心算法求解最优服务次序问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优服务次序问题：设有n个顾客同时等待同一项服务，顾客i需要的服务时间为ti，n>=i>=1，应如何安排这n个顾客的服务次序才能使平均等待时间达到最小。平均等待时间是n个顾客等待服务时间的总和除以n。贪心选择策略假设原问题为T，而我们已经知道了某个最优服务系列，即最优解为A={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(3)+……t(n)；那么总等待时间，即最优值为：TA=n。t(1)+(rrl)‘t(2)十…+(n+l—i)‘t(i)

2、+…2’t(n-1)+t(n)由于平均等待时问是n个顾客等待时间的总和除以n，故本题实际上就是求使顾客等待时间的总和最小的服务次序。本问题采用贪心算法求解，贪心策略如下：对服务时间最的顾客先服务的贪心选择策略。首先对需要服务时问最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T’。新问题和原问题相同，只是问题规模由n减小为n一1。基于此种选择策略，对新问题T’，选择n-l顾客中选择服务时间最短的先进行服务．如此进行下去，直至所有服务都完成为止。#include#nclude#include

3、ib．h>#includelongn：_1：／／顾客数nLong*wait；N各自等待时间voidinputDataO{／／输入数据n、waitifstreamfin；fin．open(*input．txt’，los::nocreate)；if(!fin){cout<<“FileOpenError!"<>n；Wait==newlong[n]；for(1ongi=0；i>wait[i]；)fin．close0；}voidShellSort(10ng*a)(//Shell排序，实现数据从小到大排序lo

4、ngi，j，x．gap=n／2；while(gap>0){for(i=gap；i=0){if(a[J]>a[j+gap]){x=a[j]；a[j]=a[j+gap]；a[j+gap]=x；j=j-gap；}else{j一1；}}}gap=gap／2；}}／函数名：AveWait0描述：计算平均等待时问参数：各顾客等待时间／doubleAveWait(10ng*a){doubleave=0.0；’ShellSort(a)；．for(10ngi=0；i

5、ave；)voidoutputData(doubleout)(∥输出结果ofstreamfout；fout．open("output．Txt")；fout<

6、最优服务次序问题：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1<=i<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。(输入的数据要求从文件input.txt中读到程序中，输出结果要求写入文件output.txt中。)法一：#include#includeusingnamespacestd;voidCountingSort(intt[],intn,intr[],inte,intq[]){inti;//计数排序for(i=0;i

7、)q[i]=0;//把数组元素全部赋初值为0for(i=0;i0;i--)//将顾客等待时间从小到大排列{r[q[t[i-1]]-1]=t[i-1];q[t[i-1]]-=1;}}voidmain(){inti=0,sum=0,n,max=0,u;//n为顾客个数floatvt,