3.6 多处最优服务次序问题

3.6 多处最优服务次序问题 算法设计思想： 该问题比 3.5（只有一个服务站）更具普遍性，需要考虑多个服务站的整体最优服 务次序。问题要使顾客的平均等待时间最短，容易想到要对顾客和服务站分别采用不同 的贪心策略：一方面，对于顾客，需要服务时间短的优先进行服务；另一方面，对于服 务站，处理当前服务任务的结束时间早的优先分配新的顾客。通过这两种贪心策略，即 可保证顾客的等待时间尽量短，得到最优服务次序，即整体的最优解。 对于第一个贪心策略，我们对顾客的服务次序进行预处理，按照服务时间升序排列； 对于第二个贪心策略，我们定义函数，得到当前结束时间最早的服务站。 对顾客的服务时间采用快速排序。虽然程序代码比冒泡排序和选择排序复杂，但对 于处理大规模的问题，在时间复杂度上有明显的改善。 为顾客、服务处分别定义了一个结构体，在处理过程中，只需要对结构体变量的属 性进行判断和修改。为服务次序定义了一个类，并且类的公有函数只有一个求解函数， 其他处理函数和参数被定为保护和私有，增强了类对象的封装性。通过类和对象来解决 规划问题，使程序思路清晰，简单易懂。 采用动态数组，节省了内存，使程序变得灵活，可以处理大规模数据。 求解函数 Solve()很简洁，首先是一个对服务时间的快排函数，然后在一个 for 循环 内，用一个指派函数完成对顾客的服务分配，最后一个输出函数记录结果。 除此之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。 程序设计代码： /*头文件 最优服务次序问题.h*/ #ifndef KNAP_H #define KNAP_H #include #include #include #include using namespace std; struct client /顾客 unsigned int number; /顾客编号 float service_time; /所需服务时间 float wait_time; /等待时间 ; struct service /服务处 unsigned int number; /服务处编号 unsigned int client_num; /接待顾客数量 unsigned int *clients_num; /接待的顾客编号数组 float current_time; /服务处计时器 ; class Service /最优服务次序 public: Service(char *in, char *out); /构造函数 Service(); /析构函数 void Solve(); /输出结果到文件 protected: void QuickSort(int low, int high); /按服务时间从小到大快速排序 int Partition(int low, int high); /快速排序的一次划分 void GetService(int i, int j); /贪心策略：顾客 i 到服务处 j int EarliestPlace(); /最早可以服务的服务处下标 void Output(); /输出最优服务次序 private: unsigned int client_num; /顾客数 unsigned int service_num; /服务处数 client *clients; /顾客数组 service *services; /服务处数组 float ave_ser_time; /平均服务时间 ofstream fout; /输出结果文件指针 ; #endif /*函数实现文件 最优服务次序问题.cpp*/ #include “最优服务次序问题.h“ Service:Service(char *in, char *out) : fout(out) ifstream fin(in); if( !fin ) cerr client_num; /初始化顾客数 fin service_num; /初始化服务处数 clients = new clientclient_num; /申请顾客数组 for(unsigned int i = 0; i clientsi.number; /初始化顾客编号 fin clientsi.service_time; /初始化顾客所需服务时间 clientsi.wait_time = FLT_MAX; /初始化顾客等待时间 fin.close(); services = new serviceservice_num; /申请服务处数组 for(unsigned int i = 0; i = temp.service_time /从右向左扫描，查找第 1 个小于 temp 服务时间的顾 客 if(low high) clientslow+ = clientshigh;/交换 low 和 high while(clientslow.service_time = temp.service_time /从左向右扫描，查找第 1 个大于 temp 服务时间的顾 客 if(low high) clientshigh- = clientslow; /交换 low 和 high while(low != high); clientslow = temp; /基准已被最后定位 return low; void Service:GetService(int i, int j) servicesj.current_time += clientsi.service_time; /调整服务处计时器 servicesj.clients_numservicesj.client_num+ = clientsi.number; /记录顾客编 号 clientsi.wait_time = servicesj.current_time; /记录顾客等待时间 int Service:EarliestPlace() float earliest_time = services0.current_time; int earliest_num = 0; for(unsigned int i = 0; i service_num; i+) if(servicesi.current_time earliest_time) earliest_time = servicesi.current_time; earliest_num = i; return earliest_num; void Service:Output() foutsetiosflags(ios:fixed); fout.precision(2); /输出数字为两位小数 fout ave_ser_time endl; for(unsigned int i = 0; i service_num; i+) fout servicesi.number; for(unsigned int j = 0; j servicesi.client_num; j+) fout servicesi.clients_numj; fout endl; /*主函数文件 test.cpp*/ #include “最优