1、算法設計與分析上機報告姓名： 張先榮 學號： SA16225439 日期： 2016/12/20'實驗七：最佳調度問題（回溯算法）日：實驗環境：CPU:coreI7 ;內存： 8G ;操作系統:Win10 ;軟件平臺 Visual studio 2013;一、算法設計與分析: 題目:一最佳調度問題（回溯算法） 設有n個任務由m個可并行工作的機器來完成，完成任務i需要時間為ti。 試設計一個算法找出完成這個任務的最佳調度，使完成全部任務的時間最早。算法思想：解空間的表示：一個深度為N的M叉樹。int N;/任務數int M;/機器數int best;/最優值int t;/每個任務所需要的

2、時間序列int len;/每臺機器所需要的時間int x;/當前路徑int bestx;/最優調度基本思路：1 、搜索從開始結點（根結點）出發，以DFS搜索整個解空間。2、每搜索完一條路徑則記錄下t和best序列，開始結點就成為一個活結點， 同時也成為當前的擴展結點。在當前的擴展結點處向縱深方向移至一個 新結點，并成為一個新的活結點，也成為當前擴展結點。3、如果在當前的擴展結點處不能再向縱深方向擴展，則當前擴展結點就成 為死結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當 前的擴展結點；直至找到一個解或全部解。二、核心代碼：1.如圖所示，即為回溯算法，以深度優先遍歷方式

3、遍歷解空間樹，每次向下遍歷一層，意味著記錄一次任務的完成序列。Len加上任務序列的時間T,如果不是最優的，回溯，len減去任務的序列時間Tynid backtrackCint dep)(if (dep = N)Iint tnp = conpO ;if (tnp < best) (best - tirp;for (int i = 0: i < N; i+) (bests Ei = di;)return)for (Int i = 0; i < M； 1+) (4= tdep;idep =i + lFif (lenEi < best) (backtrackCdep + 1);

4、)leni -= tdep;)2.計算任務完成的時間。某個機器時間最大，則他就是任務結束的時間"計算完成任務的時間1個引用 iin <oiup ()(int t 8噸=0;ior (int i = 0； i < K, i") (if (leni > teirj>)(temp - leni;Teturn te匹，3.解空間如圖。在這個圖中能清晰地說明問題。 3叉樹，機器數為3.深度為4, 總共4層，則任務數為4,用3臺機器去調度4個任務，把這棵樹深度遍歷，最 后選出最優值。三、結果與分析: 題目一：想序運打總共花/X, 口 ：葭（）聞是世時河是I站每十

5、住身所花折的時境占67 45 8059 95 3：端 20最佳畫度序.K星：L23245at14愕就排有半如圖所示，當任務數為10,機器數為7,總共耗時34.0782ms,最有時間為95單位時間，每個任務所花費時間就是隨機數生成的時間序列是：67, 45, 80,32, 59,95, 37,46,28,20.機器調度順序是1, 2, 3, 2,4,5,6,6, 1,4性主運打生於花生因1再9uif量俾時再是4?4年個任畀所證艮安憫173 31崎7衲9 ”雕萌加的道3T $1 31躅9眈60強 般住國度序列是Tb 1 1 1 I I 1 L2 1222231222牌就拼有半如圖所示，當任務數為2

6、0,機器數為2,總共耗時18.2999ms,最有時間為 474單位時間，每個任務所花費時間就是隨機數生成的時間序列是： 73, 31 , 66, 7, 50, 9, 11, 53, 66, 90, 99, 12, 37, 31, 31, 38, 9, 82, 60, 93.M = 5;Randomr = new Random);t= new int N; /每個任務的時間for ( int i = 0; i < N; i+)ti = r.Next(1,100);/隨機數生成每個任務所需要的時間len= new int M; /記錄每臺機器已安排的時間 best = 9999999;bes

7、tx =new int N;x = new int N;Stopwatch sw = new Stopwatch ();sw.Start();backtrack(0);sw.Stop();TimeSpan ts2 = sw.Elapsed;Console .WriteLine("程序運行總共花費0ms."ts2.TotalM川iseconds);Console .WriteLine("最優時間是：");Console .Write(best+ "");Console .WriteLine("每個任務所花費的時間是："

8、;);for ( int i = 0; i < N; i+)Console .Write(ti +"");Console .WriteLine();Console .WriteLine("最佳調度序列是：");for ( int i = 0; i < N; i+) Console .Write(bestxi +"");Console .ReadKey(); void backtrack( int dep)if (dep = N)int tmp = comp();if (tmp < best)1best = tmp;|for ( int i = 0; i < N; i+)(bestxi = xi;) return ;)for ( int i = 0; i < M; i+) (leni += tdep;xdep = i + 1;Iif (leni < best) backtrack(dep + 1);)leni -= tdep;)/計算完成任務的時間int comp()int temp = 0;for ( int i = 0; i < M; i+)if (leni