实验报告3.1
学号：201208070103 姓名：陈明班级：智能1201
第17 周
课程名称算法设计与分析实验课时 2
实验项目最优服务次序问题实验时间2015年1月17日
实验目的
设有n个顾客同时等待一项服务。顾客i需要的服务时间为t i，1≤i≤n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n恶搞顾客等待服务时间的总和除以n。
实验环境Eclipse Luna, Java JDK1.8, Windows 8.1
实验内容（算法、程序、步骤和方法）一、算法策略
求解最优服务次序问题的贪心策略为：先为所需服务时间最短的顾客服务。使用贪心算法求解最优服务次序问题的算法，用C++语言描述。
二、算法设计
对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最
T变成了需对n-1个顾客服务的新问题T n减小为n-1。基于此种T n-1顾客中选择服务时间最
假如顾客的所需要的服务时间分别为：1,2,3,4,5
那么等待时间是
第一位顾客：1
第二位顾客：1，2
第三位顾客：1，2，3
第四位顾客：1，2，3，4
第五位顾客：1，2，3，4，5
则总等待时间可写成：1*5+2*4+3*3+4*2+5*1
三、复杂度分析
程序主要是花费在对各顾客所需服务时间的排序和贪心算法即
重循环影响时
O(n)
O(nlogn)O(nlogn)。
数据记录和计算
结论（结果）
实验运行结果如上截图，测试的结果为，平均等待时间的最小值=6.0
小结
最短服务时间优先，先将服务时间排序，然后注意后面的等待服务时间既包括等待部分，也包括服务部分。
指导老师
评议
成绩评定：指导教师签名：
