多处最优服务次序问题

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到服务处jint 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 最优服务次序问题.hService:Service(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr 文件 in 无法打开! 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 service_num; i+)servicesi.number = i+1;/初始化服务处编号servicesi.client_num = 0;/初始化服务处接待顾客数量servicesi.clients_num = new unsigned intclient_num;/服务处接待顾客号数组for(unsigned int j = 0; j client_num; j+)servicesi.clients_numj = 0;/初始化服务处接待顾客编号servicesi.current_time = 0;/初始化服务处计时器ave_ser_time = 0;/初始化平均等待时间if( !fout )cerr 文件 out 无法打开! endl;exit(1);Service:Service()if(fout)fout.close();if(clients)delete clients;if(services)delete services;void Service:Solve()QuickSort(0, client_num-1);/按服务时间从小到大快速排序for(unsigned int i = 0; i client_num; i+)GetService(i, EarliestPlace();/贪心策略求最优服务次序ave_ser_time += clientsi.wait_time;ave_ser_time /= client_num;/计算平均等待时间Output();/输出最优服务次序void Service:QuickSort(int low, int high)if(low = temp.service_time & low high)high-;/从右向左扫描，查找第1个小于temp服务时间的顾客if(low high)clientslow+ = clientshigh;/交换low和highwhile(clientslow.service_time = temp.service_time & low high)low+;/从左向右扫描，查找第1个大于temp服务时间的顾客if(low high)clientshigh- = clientslow;/交换low和highwhile(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