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

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

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

3、是時間為：T(1)=t(1)；T(2)=t(1)+t(2)；.T(n)=t(1)+t(2)+.+t(n)；那么，總的等待時間，即為最優(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)；由于，平均等待時間是n個顧客等待時間總和除以n，則本題轉(zhuǎn)化為求使得顧客等待時間總和最小的服務次序問題。6、 源代碼#include#include#include#includelong n=-1； /顧客數(shù)為nlong *wait； /顧客各自等待時間waitvoid inputData () /輸入數(shù)據(jù)n，等待時間waiti

4、fstream 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排序，實現(xiàn)數(shù)據(jù)從小到大排序long i，j，tempgap=n2；while(gap0)for(i=gap；i=0)if(xjxj+gap)temp=xj；xj=xj+gap；xj+gap=temp； /實現(xiàn)大小交換j=j-gap； elsej=-1；gap=gap2；*函數(shù)名：AveWait0

5、描述：計算平均等待時問參數(shù)：各顧客等待時間*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)( /輸出結(jié)果ofstream fout；foutopen(outputtxt)；foutsetiosflags(ios：fixed)setprecision(2)outendl；foutclose0；)void main0 /主調(diào)函數(shù)inputData()；if(n!=-1)(double avewait=AveWait(wait)；outputData(avewait)：7、 運行結(jié)果分析試驗結(jié)果：inputtxt：12 56 22 l9 90 1002 234 33 45 97 810outputtxt：532008、 收獲及體會本題將顧客平均等待時間最小，轉(zhuǎn)