最优服务次序问题.doc

算算法法与与分分析析课课程程设设计计报报告告题题 目：目： 最优服务次序问题 专专 业：业： 软件工程 班班 级：级： 学学 号：号： 姓姓 名：名： 太原工业学院计算机工程系2012 年年 11 月月 23 日日一、一、 算法问题描述算法问题描述设有 n 个顾客同时等待一项服务顾客 i 需要的服务时间为 ti, 1≦i≦n 应如何安排 n 个顾客的服务次序才能使平均等待时间达到最小?总的等待时间是每个顾客等待服务时间的总和二、二、 算法问题形式化表示算法问题形式化表示对于给定的 n 个顾客需要的服务时间，编程计算最优服务次序，使总的等待时间最小三、三、 期望输入与输出期望输入与输出期望输入：第一行输入整数 n，表示有 n 个顾客且，第二行输入整数 s，表示有 s 处可以提供顾客需要的服务期望输出：接下来的一行输出服务点顾客的等待时间，最后输出平均等待时间的最小值四、四、 算法分析与步骤描述算法分析与步骤描述假设原问题为 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)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)由于平均等待时间是 n 个顾客等待时间的总和除以n故本题实际上就是求使顾客等待时间的总和最小的服务次序。

本问题采用贪心算法求解，对服务时间最短的顾客先服务的贪心选择策略首先对需要服务时间最短的顾客进行服务即做完第一次选择后原问题 T 变成了需对 n-1 个顾客服务的新问题 T’ 新问题和原问题相同只是问题规模由n 减小为 n-1基于此种选择策略对新问题 T’选择 n-1 顾客中选择服务时间最短的先进行服务如此进行下去直至所有服务都完成为止五、五、 问题实例及算法运算步骤问题实例及算法运算步骤在一个服务窗口有九个顾客，服务时间依次为｛2，6 ，9，8，14，23，5，6，9｝ ，给出一个最优服务次序使总的等待时间最短采用贪心算法策略，先对服务时间最短的一个顾客服务，然后就剩下 n-1个，如此进行下去，直至所有的顾客服务完六、六、 算法运行截图算法运行截图七、七、算法复杂度分析算法复杂度分析程序主要是花费在对各顾客所需服务时间的排序和贪心算法即计算平均服务时间上面其中贪心算法部分只有一重循环影响时间复杂度其时间复杂度为 O(n)而排序算法的时间复杂度为 O(nlogn)因此综合来看算法的时间复杂度为 O(nlogn)。