6.3 最佳調度問題算法設計思想：(1) 分支限界法求解假設有n個任務和k個機器，首先將問題轉化為一顆解空間樹：樹高為n，每一層對應一個任務；每個節點代表一個調度狀態，記錄了每個機器完成任務的時間；每個節點有k個孩子，代表下一個任務可以由k個機器來完成。這樣，問題所求的最佳調度方案就是找所有機器完成時間最大值的最小值葉子節點。分支限界法的本質是對解空間樹的BFS（廣度優先）搜索，即將下一個任務由每個機器完成的調度狀態入隊，而后再依次將出隊的每一個狀態的子狀態入隊。為了實現剪枝，我們需要定義一個處理時間上界up，其含義為：當前剩下的任務全部由完成時間最早的機器處理之后，所有機器完成任務的最晚時間。這樣，在搜索過程中不斷縮小up，并判斷當前狀態的最晚完成時間，一旦大于up，說明該支路沒有發展前景，進行剪枝。另外，為了使up正確地指示上界，需要首先對任務按照完成時間降序排序，并且預處理得到剩下的后m項任務的完成時間，避免在搜索過程中重復計算。(2) 采用優先隊列容器在進行BFS搜索時，需要用隊列來存儲解空間樹的各個節點，即當前的調度狀態。該算法采用函數庫提供的特殊容器：優先隊列容器priority_queue（包含在庫queue中），并且自己定義了優先隊列容器所需的對象比較優先權bool operator()const為調度狀態中最大機器完成時間，使隊列每次出隊的元素為最大完成時間最小的調度方案，實現了優先隊列式的分支限界法。(3) 搜索過程中動態申請釋放數組在BFS搜索過程中，解空間樹的每個狀態節點所記錄的各機器完成時間都采用動態數組記錄。這就要求我們不能僅靠構造函數中那一次動態數組申請，而是需要對每個新的狀態申請一個動態數組。同樣，我們也不能只靠類對象的析構函數來釋放一個動態數組，而需要在算法每次剪枝時釋放懸空的動態數組。我們用全局變量NUMBER（初始為0）對動態數組的申請（+）和釋放（-）進行了監視，結果顯示（NUMBER=0）所有申請的動態數組都得到了釋放。（相應代碼已刪去）算法的重點是處理時間上界up的定義，優先隊列容器的使用，以及對動態數組的動態申請和釋放。除了上述三點之外，程序對魯棒性做了增強，對非法輸入和文件錯誤進行了檢測。程序設計代碼： /*頭文件 最佳調度問題.h*/#ifndef KNAP_H#define KNAP_H#include #include #include /包含優先隊列容器using namespace std;class state/記錄調度狀態public:state(int k);/構造函數，k是機器數state();/析構函數int x;/任務序號int *time;/記錄各機器當前時間bool operator(const state &y)const; /定義優先隊列所需的關系state& operator=(const state &y); /定義狀態賦值運算符=private:int n;/任務數;class Task/任務類public:Task(char *in, char *out);/構造函數Task();/析構函數void Solve();/輸出結果到文件protected:void Sort();/將工作時間從大到小排序void Schedule();/分枝限界法采用優先隊列求解void PreProcess(int *last);/預處理，后幾個工作的時間和int MinMachine(int* time);/當前狀態下處理最小時間機器int *Fresh(int* old);/更新狀態中的時間int Max(int* time);/返回最大時間void Print();/輸出結果private:int n, k;/任務數和機器數int *t;/完成任務的時間int *time;/記錄各機器工作時間int min;/最小工作時間ofstream fout;/輸出結果文件;#endif/*函數實現文件 最佳調度問題.cpp*/#include 最佳調度問題.hstate:state(int k)/構造函數，k是機器數n = k;x = 0;/表示從選0個任務開始time = new intn+1;/需要記錄n個機器的當前時間for(int i = 1; i (const state &y)const/定義優先隊列所需的關系int this_max = 0;int y_max = 0;for(int i = 1; i = n; i+)/找到該狀態機器最大處理時間if(this_max timei)this_max = timei;if(y_max y_max)/機器最大處理時間大于yreturn true;elsereturn false;state& state:operator=(const state &y) /定義狀態賦值運算符=x = y.x;n = y.n;time = y.time;return *this;Task:Task(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr 文件 in 無法打開! n k;/初始化任務數n和機器數kt = new intn+1;for(int i = 1; i ti;/初始化各任務所需處理時間fin.close();time = new intk+1;for(int i = 1; i = k; i+)timei = 0;/初始化各機器處理時間min = INT_MAX;/最小時間開始初始化為最大值if( !fout )cerr 文件 out 無法打開! endl;exit(1);Task:Task()if(fout)fout.close();if(t)delete t;if(time)delete time;void Task:Solve()Sort();/將工作時間從大到小排序Schedule();/分枝限界法采用優先隊列求解Print();/輸出函數void Task:Sort()int temp;for(int i = 1; i n; i+)for(int j = i+1; j = n; j+)if(ti tj)temp = ti;ti = tj;tj = temp;void Task:Schedule()int *last;/存儲剩下工作時間的數組last = new intk;/元素為之后剩余工作時間和PreProcess(last);/預處理int up = last0;/處理時間上界，初始為總時間state temp(k);/輔助狀態，構造k個機器/存儲狀態的優先隊列容器，按照當前狀態機器最大完成時間升序排列priority_queuestate, vector, greater Queue;Queue.push(temp);int num;/任務序號int min_machine;/當前狀態處理時間最少的機器while(1)temp = Queue.top();/取隊頭元素if(temp.x = n)/處理結束break;Queue.pop();num = temp.x;for(int i = 1;i 1 & temp.timei = temp.timei-1)if(i = k)/需要釋放數組time內存delete temp.time;continue;/同等剪枝if(Max(temp.time) up)if(i = k)/需要釋放數組time內存delete temp.time;continue;/限界剪枝temp.timei += tnum+1;/加上下一個任務的時間min_machine = MinMachine(temp.time);temp.timemin_machine += lastnum+1;if(Max(temp.time) max)min = max;/找到最優方案delete temp.time;void Task:PreProcess(int *last)for(int i = 0; i n; i+)/預處理last數組lasti = 0;for(int j = i+1; j = n; j+)lasti += tj;int Task:MinMachine(int* time)int min = INT_MAX;int min_machine;for(int i = 1; i = k; i+)if(timei min)min = timei;min_machine = i;return min_machine;int* Task:Fresh(int* old)int *temp;temp = new intk+1;for(int i = 1; i = k; i+)tempi = oldi;return temp;int Task:Max(int* time)int max = 0;for(int i = 1; i = k; i+)if(max timei)max = timei;return ma