《算法分析与设计》最优服务次序问题的答案(共4页).doc

精选优质文档-倾情为你奉上最优服务次序问题设有n个顾客同时等待同一项服务。顾客i需要的服务时间为ti,1=i=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。参考答案一、最优服务次序问题二、运行环境（软、硬件环境）运行软件：Window7 64位硬件：华硕PC机编写程序：C+语言编译环境：VC+6.0三、算法设计的思想首先，要使n个顾客平均等待时间最小，即为：让n个顾客等待服务时间总和最小。因为，平均等待时间=等待服务时间总和/n。接着，由于每个顾客i的服务时间为ti,要实现等待服务时间总和最小，应该尽可能安排ti值小的顾客，进行服务。因此，本题属于局部最优的设计问题，即为贪心算法。4、 算法的流程图等待服务时间总和最小顾客平均等待时间最小最优解min = t(1),t(2).t(n)ti值小的顾客,先服务 局部最优贪心算法第i个顾客等待时间 总的等待时间，即最优解Tmin