《算法分析與設(shè)計(jì)》最優(yōu)服務(wù)次序問題的答案

1、精選文檔最優(yōu)服務(wù)次序問題設(shè)有n個顧客同時(shí)等待同一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti,1<=i<=n。應(yīng)如何安排n個顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最??？平均等待時(shí)間是n個顧客等待服務(wù)時(shí)間的總和除以n。參考答案一、最優(yōu)服務(wù)次序問題二、運(yùn)行環(huán)境（軟、硬件環(huán)境）運(yùn)行軟件：Window7 64位硬件：華碩PC機(jī)編寫程序：C+語言編譯環(huán)境：VC+6.0三、算法設(shè)計(jì)的思想首先，要使n個顧客平均等待時(shí)間最小，即為：讓n個顧客等待服務(wù)時(shí)間總和最小。因?yàn)?，平均等待時(shí)間=等待服務(wù)時(shí)間總和/n。接著，由于每個顧客i的服務(wù)時(shí)間為ti,要實(shí)現(xiàn)等待服務(wù)時(shí)間總和最小，應(yīng)該盡可能安排ti值小的顧客，進(jìn)行服務(wù)。

2、因此，本題屬于局部最優(yōu)的設(shè)計(jì)問題，即為貪心算法。4、 算法的流程圖等待服務(wù)時(shí)間總和最小顧客平均等待時(shí)間最小最優(yōu)解min = t(1),t(2).t(n)ti值小的顧客,先服務(wù) 局部最優(yōu)貪心算法第i個顧客等待時(shí)間 總的等待時(shí)間，即最優(yōu)解Tmin程序?qū)崿F(xiàn)，引入Shell排序，實(shí)現(xiàn)數(shù)據(jù)從小到大排序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、 算法設(shè)計(jì)分析假設(shè)原問題的時(shí)間為T，已經(jīng)知道了某個最優(yōu)服務(wù)系列，最優(yōu)解為min=t(1)，t(2)，.，t(n)（其中t(i)為第i個客戶需要的服務(wù)時(shí)間）

3、，那么每個客戶需要的等待是時(shí)間為：T(1)=t(1)；T(2)=t(1)+t(2)；.T(n)=t(1)+t(2)+.+t(n)；那么，總的等待時(shí)間，即為最優(yōu)解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)；由于，平均等待時(shí)間是n個顧客等待時(shí)間總和除以n，則本題轉(zhuǎn)化為求使得顧客等待時(shí)間總和最小的服務(wù)次序問題。6、 源代碼#include<fstreamh>#include<iostreamh>#include<stdlibh>#include<iomaniph>

4、long n=-1； /顧客數(shù)為nlong *wait； /顧客各自等待時(shí)間waitvoid inputData () /輸入數(shù)據(jù)n，等待時(shí)間waitifstream fin；finopen(*inputtxt，los:nocreate)；if(!fin)cout<<“File Open Error!"<<endl；return；fin>>n；wait=new longn；for(1ong i=0；i<n；i+)fin>>waiti；)finclose0；void ShellSort(long *x)( /Shell排序，實(shí)現(xiàn)數(shù)據(jù)

5、從小到大排序long i，j，tempgap=n2；while(gap>0)for(i=gap；i<n；i+) j=i-gap；while(j>=0)if(xj>xj+gap)temp=xj；xj=xj+gap；xj+gap=temp； /實(shí)現(xiàn)大小交換j=j-gap； elsej=-1；gap=gap2；*函數(shù)名：AveWait0描述：計(jì)算平均等待時(shí)問參數(shù)：各顧客等待時(shí)間*double AveWait(long *x)double ave=0.0；ShellSort(x)；for(long i=0；i<n；i+)ave+=1.0*(n-i)*xi；ave=n； /

6、求平均等待時(shí)間return ave；)void outputData(double out)( /輸出結(jié)果ofstream fout；foutopen("outputtxt")；fout<<setiosflags(ios：fixed)<<setprecision(2)<<out<<endl；foutclose0；)void main0 /主調(diào)函數(shù)inputData()；if(n!=-1)(double avewait=AveWait(wait)；outputData(avewait)：7、 運(yùn)行結(jié)果分析試驗(yàn)結(jié)果：inputtxt：12 56 22 l9 90 1002 234 33 45 97 810outputtxt：532008、 收獲及體會本題將顧