算法分析_最优服务次序问题

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

1、最优服务次序问题一、问题描述：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1wiwn。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到故小？平均等待时间是n个顾客等待服务时间的总和除以n。二、贪心选择策略假设原问题为T，而我们已经知道了某个最优服务系列，即最优解为A={t(1),t(2),....t(n)}快中t(i)为第i个用户需要的服务时间),则每个用户等待时间为:T⑴=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；那么总

2、等待时问，即最优值为：TA=n*t(1)+(n-1)*t(2)+...+(n+1J)W.--2*t(n-1)+t(n)；由于平均等待时间是n个顾客等待时间的总和除以n,故木题实际上就是求使顾客等待吋间的总和最小的服务次序。本问题采用贪心算法求解，贪心策略如下：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n・1个顾客服务的新问题T'。新问题和原问题相同，只是问题规模由n减小为基于此种选择策略，対新问题T',选择顾客中选择服务时间最短的先进行服务，如

3、此进行下去，直至所有服务都完成为止。三、问题的贪心选择性质先來证明该问题具冇贪心选择性质，即最优服务A中t⑴满足条ft：t(1)<=t(i)(2t(i)(i>1)o设另一服务序列8=(t(i),t(2),t(1)...,t(n))那么TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0即TA>TB,这与A是最优服务相矛盾。故最优服务次序问题满足贪心选择性质。四、问题的最优子结构性质在进行了贪心

4、选择示，原问题T就变成了如何安排剩余的个顾客的服务次序的问题F,是原问题的子问题。若A是原问题T的最优解，则A={t(2),...t(i)...t(n))是服务次序问题子问题F的最优解。证明：假设A'不是子问题T'的最优解，其子问题的最优解为B',则有TB'vTA',而根据TA的定义知，TA'十t(1)=TA。因此TB'+t⑴vTA'+t(1)=TA,即存在一个比最优值TA更短的总等待时间，而这与TA为问题T的最优值相矛盾。因此，A'是子问题T，的最优值。从以上贪心选择及最优了结构性质的证明，可知对最优服务次序问题用贪

5、心算法可求得最优解。根据以上证明，最优服务次序问题可以用最短服务吋间优先的贪心选择可以达到最优解。故只需对所冇服务先按服务时间从小到大进行排序，然后按照排序结果依次进行服务即可。平均等待时间即为TA/no五、算法实现山多处最优服务次序问题具有贪心选择性质和最优子结构性质，容易证明算法greedy的正确性。本算法釆用最短服务时间优先的贪心策略。首先将每个顾客所需要的服务时间从小到人排序。然后屮请2个数红st[]是服务数组，st[j]为第j个队列上的某一个顾客的等待时间;su[]是求和数组，su[j]的值为第j个队列上所冇

6、顾客的等待时间；doublegreedy(vectorvint>x,ints){vectorst(s+1,0);vectorvint>su(s+1,0);intn=x.size();sort(x.begin(),x.end());inti=0,j=0;while(i

7、杂性分析程序主要是花费在对各顾客所需服务时间的排序和贪心算法，即计算平均服务时间上面。其屮，贪心算法部分只有一重循环影响吋间复杂度，其吋间复杂度为O(n)：ifij排序算法的吋间复杂度为O(nlogn)o因此，综合来看算法的时间复杂度为O(nlogn)0八、参考文献[1]王晓东•计算机算法设计与分析(第3版)[M].北京：电子工业出版社,2007.[2]陈媛.《算法与数据结构》[M],清华大学出版社，第1版,2005.4.⑶王晓东.算法设计与实验题解[M],北京：电子工业出版社,2008.附录(程序代码)#includ

8、e#inelude#includeusingnamespacestd;usingstd::vector;doublegreedy(vectorvint>x,ints){vectorst(s+1,0);vectorvint>su(s+1,0);intn=x.size