[算法分析与设计]最优服务次序问题的答案_最优服务次序问题算法
最优服务次序问题
设有n个顾客同时等待同一项服务。顾客i需要的服务时间为ti,1
参考答案
一、最优服务次序问题
二、运行环境（软、硬件环境）
运行软件：Window7 64位
硬件：华硕PC机
编写程序：C++语言
编译环境：VC++6.0
三、算法设计的思想
首先，要使n个顾客平均等待时间最小，即为：让n个顾客等待服务时间总和最小。因为，平均等待时间=等待服务时间总和/n。
接着，由于每个顾客i的服务时间为ti,要实现等待服务时间总和最小，应该尽可能安排ti值小的顾客，进行服务。
因此，本题属于局部最优的设计问题，即为贪心算法。
四、算法的流程图
第
五、算法设计分析
假设原问题的时间为T，已经知道了某个最优服务系列，最优解为min={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(n)；
那么，总的等待时间，即为最优解
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，则本题转化为求使得顾客等待时间总和最小的服务次序问题。
六、源代码
#include
#include
#include
#include
long n=-1； //顾客数为n
long *wait； //顾客各自等待时间wait
void inputData ()
{ //输入数据n，等待时间wait
ifstream fin；
fin．open(*input．txt’，los::nocreate)；
if(!fin){
cout
return；
}
fin>>n；
wait==new long[n]；
for(1ong i=0；i
{
fin>>wait[i]；
)
fin．close0；
}
void ShellSort(long *x)
( //Shell排序，实现数据从小到大排序 long i，j，temp．gap=n／2；
while(gap>0){
for(i=gap；i
j=i-gap；
while(j>=0){
if(x[j]>x[j+gap])
{
temp=x[j]；x[j]=x[j+gap]；x[j+gap]=temp； //实现大小交换
j=j-gap；
}
else{j=-1；}
}
}
gap=gap／2；
}
}
／**
函数名：AveWait0
描述：计算平均等待时问
参数：各顾客等待时间
**／
double AveWait(long *x)
{
double ave=0.0；
ShellSort(x)；
for(long i=0；i
{
ave+=1.0*(n-i)*x[i]；
}
ave／=n； //求平均等待时间
return ave；
)
void outputData(double out)
( //输出结果
ofstream fout；
fout．open("output．txt")；
fout
fout．close0；
)
void main0
{ //主调函数
inputData()；
if(n!=-1)(
double avewait=AveWait(wait)；
outputData(avewait)：
}
}
七、运行结果分析
试验结果：
input．txt：
12 56 22 l9 90 1002 234 33 45 97 810
output．txt：
532．00
八、收获及体会
本题将顾客平均等待时间最小，转化为服务等待时间总和最小。利用局部最优，通过贪心算法来解决该题。
通过本题，也更深入了解贪心算法的本质，今后对于其他类似的局部最优问题、最优子结构问题，都可采用贪心算法解决。