(完整版)分支限界算法作業(yè)分配問題

1、分支限界法的研究與應(yīng)用摘要：分支限界法與回溯法的不同：首先，回溯法的求解目標(biāo)是找出解空間樹中滿足 約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。其次，回溯法以深度優(yōu)先的 方式搜索解空間樹，而分支限界法則一般以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索 解空間樹。再者，回溯法空間效率高；分支限界法往往更“快”。分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解 空間樹。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦 成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解 或?qū)е?/p>

2、非最優(yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活 結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直 持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。常見的分支限界法有：隊(duì)列式分支限界法，按照隊(duì)列先進(jìn)先出原則選取下一個(gè) 結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。棧式分支限界法，按照棧后進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié) 點(diǎn)。優(yōu)先隊(duì)列式分支限界法，按照規(guī)定的結(jié)點(diǎn)費(fèi)用最小原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展 結(jié)點(diǎn)（最采用優(yōu)先隊(duì)列實(shí)現(xiàn)）。分支搜索法是一種在問題解空間上進(jìn)行搜索嘗試的算法。所謂分支是采用廣度 優(yōu)先的策略國(guó)，依次搜索E-結(jié)點(diǎn)的所有分支，也就是所有的相鄰結(jié)點(diǎn)。和回溯法一樣, 在生成的結(jié)點(diǎn)中，拋棄那

3、些不滿足約束條件的結(jié)點(diǎn)，其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從 表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)，斷續(xù)搜索。關(guān)鍵詞：分支限界法回溯法廣度優(yōu)先分支搜索法第 1 章 緒論1.1 分支限界法的背景知識(shí) 31.2 分支限界法的前景意義3.錯(cuò) 誤 ! 未定義書簽。第 2 章 分支限界法的理論知識(shí)2.1 問題的解空間樹錯(cuò)誤!未定義書簽。2.2 分支限界法的一般性描述第3 章 作業(yè)分配問題 73.1 問題描述 73.2 問題分析 73.3 算法設(shè)計(jì) 83.4 算法實(shí)現(xiàn) 103.5 測(cè)試結(jié)果與分析 12第4 章 結(jié)論 1.3.參考文獻(xiàn)1.4.- 1 -第 1 章 緒論1.1 分支限界法的背景知識(shí)分支搜索法是一種在問題

4、解空間上進(jìn)行搜索嘗試的算法。所謂分支是采用廣度優(yōu)先的策略國(guó)，依次搜索E-結(jié)點(diǎn)的所有分支，也就是所有的相鄰結(jié)點(diǎn)。和回溯法一樣, 在生成的結(jié)點(diǎn)中 , 拋棄那些不滿足約束條件的結(jié)點(diǎn) , 其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)，斷續(xù)搜索。 1） FIFO 搜索先進(jìn)先出搜索算法要依賴“隊(duì)”做基本的數(shù)據(jù)結(jié)構(gòu)。一開始 , 根結(jié)點(diǎn)是唯一的活結(jié)點(diǎn) , 根結(jié)點(diǎn)入隊(duì)。從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后 , 作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn) , 先從左到右地產(chǎn)生它的所有兒子, 用約束條件檢查, 把所有滿足約束函數(shù)的兒子加入活結(jié)點(diǎn)隊(duì)列中。再?gòu)幕罱Y(jié)點(diǎn)表中取出隊(duì)首結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列

5、為空為止。 2） 2） LIFO 搜索后進(jìn)先出搜索算法要依賴“棧”做基本的數(shù)據(jù)結(jié)構(gòu)。一開始 , 根結(jié)點(diǎn)入棧. 從棧中彈出一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn) , 先從左到右地產(chǎn)生它的所有兒子 , 用約束條件檢查, 把所有滿足約束函數(shù)的兒子入棧 , 再眾棧中彈出一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到找到一個(gè)解或棧為空為止。（ 3）優(yōu)先隊(duì)列式搜索為了加速搜索的進(jìn)程， 應(yīng)采用有效地方式選擇E- 結(jié)點(diǎn)進(jìn)行擴(kuò)展。 優(yōu)先隊(duì)列式搜索，對(duì)每一活結(jié)點(diǎn)計(jì)算一個(gè)優(yōu)先級(jí)， 并根據(jù)這些優(yōu)先級(jí)，從當(dāng)前活結(jié)點(diǎn)表中優(yōu)先選擇一個(gè)優(yōu)先級(jí)最高的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。1.2 分支

6、限界法的前景意義在現(xiàn)實(shí)生活中，有這樣一類問題：?jiǎn)栴}有n 個(gè)輸入，而問題的解就由 n 個(gè)輸入的某種排列或某個(gè)子集構(gòu)成，只是這個(gè)排列或子集必須滿足某些事先給定的條件。把那些必須滿足的條件稱為約束條件；而把滿足約定條件的排列或子集稱為該問題的可行解。滿足約束條件的子集可能不止一個(gè)，也就量說可行解一般來說是不唯一的。為了衡量可行解的優(yōu)劣，事先也可能給出了一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)一般以函數(shù)形式給出，這些函數(shù)稱為目標(biāo)函數(shù)。那些使目標(biāo)函數(shù)取極值的可行解，稱為最優(yōu)解。 如工作安排問題，任意順序都是問題的可行解，人們真正需要的是最省時(shí)間的最優(yōu) 解。用回溯算法解決問題時(shí)，是按深度優(yōu)先的策略在問題的狀態(tài)空間中，嘗試搜索

7、 可能的路徑，不便于在搜索過程中對(duì)不同的解進(jìn)行比較，只能在搜索到所有解的情 況下，才能通過比較確定哪個(gè)是最優(yōu)解。這類問題更適合用廣度優(yōu)先策略搜索，因 為在擴(kuò)展結(jié)點(diǎn)時(shí)，可以在E-結(jié)點(diǎn)的各個(gè)子結(jié)點(diǎn)之間進(jìn)行必要的比較， 有選擇地進(jìn)行 下一步擴(kuò)展。分支限界法就是一種比較好的解決最優(yōu)化問題的算法。分支限界法是 由“分支”策略和“限界”策略兩部分組成?！胺种А辈呗泽w現(xiàn)在對(duì)問題空間是按廣度優(yōu)先的策略進(jìn)行搜索；“限界”策略是為了加速搜索速度而采用啟發(fā)信息剪枝 的策略。第2章分支限界法的理論知識(shí)2.1 問題的解空間樹子集樹在FIFO分支搜索方法中，在搜索當(dāng)前E-結(jié)點(diǎn)全部?jī)鹤雍螅鋬鹤映蔀榛罱Y(jié)點(diǎn)，目結(jié)點(diǎn)變?yōu)樗澜Y(jié)點(diǎn)

8、；活結(jié)點(diǎn)存儲(chǔ)在隊(duì)列中，隊(duì)首的活結(jié)點(diǎn)出隊(duì)后變?yōu)?E-結(jié)點(diǎn)，其再生成 其他活結(jié)點(diǎn)的兒子直到找到問題的解或活結(jié)點(diǎn)隊(duì)列為空搜索完畢.這里采用地構(gòu)造解空間二叉樹的方法 , 問題的解就是二叉樹中的某一個(gè)分支.這個(gè)解是要搜索到二叉樹的葉結(jié)點(diǎn)才能確定的 , 且只須記錄最優(yōu)解的葉結(jié)點(diǎn) , 就能 找到問題的解. 比較方便的存儲(chǔ)方式是二叉樹要有指向父結(jié)點(diǎn)的指針 , 以便從葉結(jié)點(diǎn)回溯解的方案. 又為了方便知道當(dāng)前結(jié)點(diǎn)的情況, 還要記錄當(dāng)前結(jié)點(diǎn)是父結(jié)點(diǎn)的哪一個(gè)兒子.FIFO分支搜索算法框架如下：假定問題解空間樹為T,T至少包含一個(gè)解結(jié)點(diǎn)(答 案結(jié)點(diǎn) ).u 為當(dāng)前的最優(yōu)解, 初值為一個(gè)較大的數(shù);E 表示當(dāng)前擴(kuò)展的活結(jié)點(diǎn)

9、 ,x 為 E的兒子聞x)為結(jié)點(diǎn)x下界函數(shù)，當(dāng)其值比u大時(shí),不可能為最優(yōu)解,不斷續(xù)搜索此分 支 , 該結(jié)點(diǎn)不入隊(duì); 當(dāng)其值比 u 小時(shí) , 可能達(dá)到最優(yōu)解, 斷續(xù)搜索此分支, 該結(jié)點(diǎn)入隊(duì) ;cost(X) 當(dāng)前葉結(jié)點(diǎn)所在分支的解.search(T) leaf =0;初始化隊(duì) ;ADDQ(T); parent(E) =0; while ( 隊(duì)不空 ) DELETEQ(E) for (E 的每個(gè)兒子X)if (s(X) <u) ADD Q(X);parent(X) =E;if (X是解結(jié)點(diǎn)) U=min(cost(X),u); leaf =x; printf( "least cos

10、t=%f" ,u);-3 -while (leaf != 0) printf( "%f" ,leaf);leaf =parent(leaf); 找最小成本的LC分支-限界算法框架與FIFO分支-限界算法框架結(jié)構(gòu)大致相同只是擴(kuò)展結(jié)點(diǎn)的順序不同 , 因而存儲(chǔ)活結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不同 .FIFO 分支 - 限界算法用隊(duì)存儲(chǔ)活結(jié)點(diǎn) ,LC 分支 - 限界算法用堆存儲(chǔ)活結(jié)點(diǎn) , 以保證比較優(yōu)良的結(jié)點(diǎn)行被擴(kuò)展且對(duì)于LC分支-限界算法，當(dāng)擴(kuò)展到葉結(jié)點(diǎn)就已經(jīng)找到最優(yōu)解，可以停止搜索.2.2 分支限界法的一般性描述分支限界有3種不同的搜索方式：FIFO、LIFO和優(yōu)先隊(duì)列。對(duì)于先進(jìn)先出

11、搜索(FIFO), 其算法要依賴“隊(duì)”做基本的數(shù)據(jù)結(jié)構(gòu)。一開始 , 根結(jié)點(diǎn)是唯一的活結(jié)點(diǎn) , 根結(jié)點(diǎn)入隊(duì)。從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后 , 作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn) , 先從左到右地產(chǎn)生它的所有兒子, 用約束條件檢查, 把所有滿足約束函數(shù)的兒子加入活結(jié)點(diǎn)隊(duì)列中。再?gòu)幕罱Y(jié)點(diǎn)表中取出隊(duì)首結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。對(duì)于后進(jìn)先出搜索(LIFO), 其算法要依賴“棧”做基本的數(shù)據(jù)結(jié)構(gòu)。一開始 , 根結(jié)點(diǎn)入棧 . 從棧中彈出一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn) , 先從左到右地產(chǎn)生它的所有兒子, 用約束條件檢查, 把所有滿足約束函數(shù)的兒子入棧, 再眾棧中彈出一個(gè)結(jié)點(diǎn)為當(dāng)

12、前擴(kuò)展結(jié)點(diǎn)，直到找到一個(gè)解或棧為空為止。對(duì)于優(yōu)先隊(duì)列式擴(kuò)展方式，不加入限界策略其實(shí)是無意義的，因?yàn)橐f明解的最優(yōu)性，必需搜索完問題全部解空間，才能下結(jié)論。優(yōu)先隊(duì)列式搜索通過結(jié)點(diǎn)的優(yōu)先級(jí)，可以使搜索盡快朝著解空間樹上有最優(yōu)解的分支推進(jìn)，這樣當(dāng)前最優(yōu)解一定較接近真正的最優(yōu)解。其后將當(dāng)前最優(yōu)解作為一個(gè)“標(biāo)準(zhǔn)” ，對(duì)上界(或下界)不可能達(dá)到(或大于)這個(gè)“標(biāo)準(zhǔn)”的分支，則不去進(jìn)行搜索，這樣剪枝的效率更高，能較好地縮小搜索范圍，從而提高搜索效率。這種搜索策略稱為優(yōu)先隊(duì)列式分支限界法，即“LC-檢索”。優(yōu)先隊(duì)列式分支限界法進(jìn)行算法設(shè)計(jì)的要點(diǎn)如下：( 1)結(jié)點(diǎn)擴(kuò)展方式：無論哪種分支限界法，都需要有一張活結(jié)點(diǎn)

13、表。優(yōu)先隊(duì)列的分支限界法將活結(jié)點(diǎn)組織成一個(gè)優(yōu)先隊(duì)列，并按優(yōu)先隊(duì)列中規(guī)定的結(jié)點(diǎn)優(yōu)先級(jí)選取優(yōu)先級(jí)最高的下一個(gè)結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。（ 2）結(jié)點(diǎn)優(yōu)先級(jí)確定：優(yōu)先隊(duì)列中結(jié)點(diǎn)優(yōu)先級(jí)常規(guī)定為一個(gè)與該結(jié)點(diǎn)相關(guān)的數(shù)值w， w 一般表示以該結(jié)點(diǎn)為根的子樹中的分支（其中最優(yōu)的分支）接近最優(yōu)解的程度。（ 3）優(yōu)先隊(duì)列組織：結(jié)點(diǎn)優(yōu)先級(jí)確定后，按結(jié)點(diǎn)優(yōu)先級(jí)進(jìn)行排序，就生成了優(yōu)先隊(duì)列。排序算法的時(shí)間復(fù)雜度較高，考試到搜索算法每次只擴(kuò)展一個(gè)結(jié)點(diǎn)，使用數(shù)據(jù)結(jié)構(gòu)中介紹的堆排序比較合適，這樣每次擴(kuò)展結(jié)點(diǎn)時(shí)，比較交換的次數(shù)最少。第 3 章 作業(yè)分配問題3.1 問題描述題1:作業(yè)分配問題：設(shè)有 A,B,C,D,E,等n個(gè)人從事J1,

14、J2,J3,J4,J5, 等 n 項(xiàng)工作，每人只能從事一項(xiàng)任務(wù)，每個(gè)任務(wù)由不同的工人從事有著不同的費(fèi)用，求最佳安排使費(fèi)用最低。要求：輸出每人所從事的工作任務(wù)以及最佳安排的最低費(fèi)用。題 2: 有兩艘船和需要裝運(yùn)的 n 個(gè)貨箱，第一艘船的載重量是c1 ，第二艘船的載重量是c2, Wi是貨箱i的重量，且 W1+W2+W3+W4+Wn<=c1+G2希望確定 是否有一種可將所有n 個(gè)貨箱全部裝船的方法。要求 : 輸出每艘船最終載重量 .3.2 問題分析分支搜索法是一種在問題解空間上進(jìn)行搜索嘗試的算法。是采用廣度優(yōu)先的策略國(guó) , 依次搜索 E- 結(jié)點(diǎn)的所有分支 , 也就是所有的相鄰結(jié)點(diǎn)。和回溯法一樣

15、, 在生成的結(jié)點(diǎn)中 , 拋棄那些不滿足約束條件的結(jié)點(diǎn) , 其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)E-結(jié)點(diǎn)，斷續(xù)搜索。在分支定界算法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。利用分支定界算法對(duì)問題的解空間樹進(jìn)行搜索，它的搜索策略是：（1） 產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)；（2） 在產(chǎn)生的孩子結(jié)點(diǎn)中，拋棄那些不可能產(chǎn)生可行解（或最優(yōu)解）的結(jié)點(diǎn)；- 5 -（3）將其余的孩子結(jié)點(diǎn)加入活結(jié)點(diǎn)表；（4）從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)。如此循環(huán)，直到找到問題的可行解（最優(yōu)解）或活結(jié)點(diǎn)表為空。分支限界法的 思想是：首先確定目標(biāo)值的上下界，邊搜索邊減掉搜索樹的某些支，提高搜索效率。

16、題1:先看一個(gè)實(shí)例，設(shè)有A,B,C,D,E 5人從事J1,J2,J3,J4,J5 項(xiàng)工作，每人只 能從事一項(xiàng)，他們的效益如圖所示，求最佳安排使效益最高。J1J2J3J4J5A10111047B13101085C59774D151210115E1011884要求：輸出每人所從事的工作項(xiàng)目以及最佳安排的最高效益考慮任意一個(gè)可行解，例如矩陣中的對(duì)角線是一個(gè)合法的選擇，表示將任務(wù)J1 分配給人員A,任務(wù)J2分配給人員B,任務(wù)J3分配給人員C,任務(wù)J4分配給D,任務(wù) J5分配給E,其總效益是10+10+7+11+4=42或者應(yīng)用貪心法求得一個(gè)近似解：人員A 從事J2時(shí)效益最大，將任務(wù)J2分配給人員A,剩

17、余工作中人員B從事J1時(shí)效益最大， 任務(wù)J1分配給人員B,J3、J4、J5中人員D從事J4時(shí)效益最大，任務(wù)J4分配給人 員D,J3和J5中人員C從事J3時(shí)效益最大，任務(wù)J3分配給人員C,任務(wù)J5只能分配 給人員E,其總效益是11+13+11+7+4=46顯然,42和46都不能確定是最優(yōu)解，有可能 還有比其更大的效益，這兩個(gè)解其一并不一定是一個(gè)最可行的選擇，它們僅僅提供了一個(gè)參考，這樣，可以以其中一個(gè)作為參考來進(jìn)一步對(duì)各種作業(yè)分配方案進(jìn)行搜 索，比較其每種分配方式的效益.最大的總效益為最優(yōu)解，其分配方案為最佳分配方 案.題2:先看一個(gè)實(shí)例，當(dāng)n=3,c1=c2=50,w=10,40,40時(shí)，可將

18、貨箱1,2裝到第 一艘船上，貨箱3裝到第二艘船上.但如果w=20,40,40,則無法將貨箱全部裝船. 由此可知問題可能有解，可能無解，也可能有多解.下面以找出問題的一個(gè)解為目標(biāo) 設(shè)計(jì)算法.雖然是關(guān)于兩艘船的問題，其實(shí)只討論一艘船的最大裝載問題即可.因?yàn)楫?dāng)?shù)?一艘船的最大裝載為bestw時(shí)，若w1+w2+ +wn-bestw<=c2則可以確定一種解,否則 問題就無解.這樣問題轉(zhuǎn)化為第一艘船的最大裝載問題.3.3 算法設(shè)計(jì)題1:問題的解空間為一個(gè)子集樹，所有可能的解都可通過一個(gè)求解樹給出.也 就是算法要考慮任務(wù)是否分配給人員的情況組合，n個(gè)任務(wù)分配給n個(gè)人員的組合共n*n種情況，作業(yè)分配子集

19、樹是n=4的子集樹它是用FIFO分支搜索算法解決該問題的擴(kuò)展結(jié)點(diǎn)的過程編號(hào)的544作業(yè)分配子集樹在任務(wù)分配中，如實(shí)例中若n=4時(shí),J1分配給A則向左走，否則往右走，直到走到 最后，把最終的總效益求出，并把第一次求出的總效益作為最大效益與后邊的總效 益相比較，比其大者，交換兩者，大的作為最大效益.依次方法，直到找到最優(yōu)解，并 輸出其值以及其最大效益時(shí)的最佳分配方案.(1)用FIFO分支搜索所有的分支，并記錄已搜索分支的最優(yōu)解，搜索算子集樹也 就找出了問題的解.圖中結(jié)點(diǎn)1為第零層，是初始E-結(jié)點(diǎn)；擴(kuò)展后結(jié)點(diǎn)2,3為第一 層;3,4,2是第一個(gè)任務(wù)分配出去后的下一層擴(kuò)展結(jié)點(diǎn)，4,5,3,4,5 是第

20、二個(gè)任務(wù)分 配出去后下一層的擴(kuò)展結(jié)點(diǎn)(即分配情況).(2)用taski來表示任務(wù)是否分配及分配了給哪個(gè)工人，即taski=0 時(shí)表示 任務(wù)i未分配，taski=j表示任務(wù)i分配給了工人j;用workerk=0或1來表示-7 -工人 k 是否分配了任務(wù), workerk=0 表示工人 k 未分配任務(wù), workerk=1 表示工人 k 已分配了任務(wù).(3) 把最低費(fèi)用用 mincost 來表示和 cij 表示工人 j 執(zhí)行任務(wù) i 時(shí)的費(fèi)用 , 并把 cij 和 mincost 分別初始化為 c10001000 和 100000; 同時(shí)把 aski 和 tempi 、 workeri 的存儲(chǔ)空間

21、初始為 task1000 和 temp1000 、 worker1000, 之后把其初始化為 0.(4) 用 Plan(int k,unsigned int cost) 來對(duì)分配作業(yè)的解空間樹進(jìn)行搜索 ,搜 索的時(shí)候 , 每個(gè)活結(jié)點(diǎn)要記錄下搜索的路徑( 即分配方案), 存儲(chǔ)在 tempi 中, 并求出費(fèi)用 cost, 然后 cost 與最小費(fèi)用 mincost 進(jìn)行比較 , 較小者是最小費(fèi)用 , 其分配方 案為最佳分配方案.(5) 下面的算法中用 Plan(int k,unsigned int cost) 中的第二個(gè)for 循環(huán)來實(shí)現(xiàn)對(duì)解空間樹的搜索 , 第一次 for(i=0) 時(shí)，找出 0

22、號(hào)工人分別執(zhí)行0， 1， 2， 3， 4號(hào)任務(wù)時(shí)總花費(fèi)最小 ; 第二次 for(i=1) 時(shí)， 找出 1 號(hào)工人分別執(zhí)行除0號(hào)工人的任務(wù)以外任務(wù)時(shí)總花費(fèi)最小，并與i=0時(shí)的總花費(fèi)最小比較；第五次for(i=4)時(shí)， 找出總花費(fèi)最小，并與上次的總花費(fèi)最小比較; 依次類推對(duì)解空間樹進(jìn)行搜索 . 第一個(gè) for 循環(huán)把 cost 與 mincost 進(jìn)行比較 , 求出最小費(fèi)用并記錄出最小費(fèi)用的分配方 案.題 2: 轉(zhuǎn)化為一艘船的最優(yōu)化問題后 , 問題的解空間為一個(gè)子集樹( 問題的解空間樹中的子集樹). 也就是算法要考慮所有物品取舍情況的組合.(1) 要想求出最優(yōu)解, 必須搜索到葉結(jié)點(diǎn) . 所以要記錄

23、樹的層次, 當(dāng)層次為 n+1 時(shí),搜索完全部葉結(jié)點(diǎn) , 算法結(jié)束 . 不同于回溯算法, 分支搜索過程中活結(jié)點(diǎn)的“層”是需要標(biāo)識(shí)的 , 否則在入隊(duì)后無法識(shí)別結(jié)點(diǎn)所在的層 . 下面算法 , 每處理完一層讓“ -1 ” 入隊(duì) , 以此來標(biāo)識(shí)“層” , 并用記數(shù)變量i 來記錄當(dāng)前層.(2) 每個(gè)活結(jié)點(diǎn)要記錄當(dāng)前船的裝載量.(3) 為了突出算法思想，對(duì)數(shù)據(jù)結(jié)構(gòu)隊(duì)及其操作只進(jìn)行抽象描述.用Queue代表 隊(duì)列類型，則QueueQ:定義了一個(gè)隊(duì)列 Q相關(guān)操作有：add (Q, .)表示入隊(duì)； Empty (Q)測(cè)試隊(duì)列是否為空，為空則返回真值。 Delete (Q .);表示出隊(duì)。3.4 算法實(shí)現(xiàn)算法 1

24、如下 :#include <iostream.h>#include <stdlib.h>#include <stdio.h>int n; / 工人和任務(wù)的數(shù)目int c10001000;unsigned int mincost = 100000; / 設(shè)置的初始值, 大于可能的費(fèi)用int task1000,temp1000,worker1000;void main()void Plan(int k,unsigned int cost);int i,j;printf("please input tasks and workers:");sc

25、anf("%d%d",&n,&n);printf(" 輸入每個(gè)工人完成各個(gè)工作的費(fèi)用 :n");for(i=0;i<n;i+) / 設(shè)置每個(gè)任務(wù)由不同工人承擔(dān)時(shí)的費(fèi)用及全局?jǐn)?shù)組的初值/*taski:值為 0表示任務(wù) i 未分配 , 值為 j 表示任務(wù) i 分配給工人j;workerk:值為 0 表示工人 k 未分配任務(wù), 值為 1 表示工人 k 已分配任務(wù) ;*/workeri = 0;taski = 0;tempi = 0;for(j=0;j<n;j+)scanf("%d",&cij);Plan(

26、0,0); / 從任務(wù) 0 開始分配printf(" 最小總費(fèi)用 :%dn",mincost);for(i=0;i<n;i+)printf(" 工人 :%d 執(zhí)行任務(wù) :%dn",i+1,tempi+1);void Plan(int k,unsigned int cost)int i;if(k>=n && cost<mincost)mincost = cost;for(i=0;i<n;i+)tempi = taski; / 工人 i 完成任務(wù) tempielsefor(i=0;i<n;i+)/ 分配任務(wù) ki

27、f(workeri=0) workeri = 1;taskk = i;/ 第一次 for(i=0) 時(shí)，找出 0 號(hào)工人分別執(zhí)行0， 1， 2， 3， 4 號(hào)任務(wù)時(shí)總花費(fèi)最小/ 第二次 for(i=1) 時(shí)， 找出 1 號(hào)工人分別執(zhí)行除0號(hào)工人的任務(wù)以外任務(wù)時(shí)總花費(fèi)最/ 小，并與 i=0 時(shí)的總花費(fèi)最小比較/./ 第 5 次 for(i=4) 時(shí)， 找出總花費(fèi)最小， 并與上次的總花費(fèi)最小比較Plan(k+1,cost+cki);workeri = 0;- 11 -taskk = 0;算法2如附件：3.5 測(cè)試結(jié)果與分析實(shí)驗(yàn)結(jié)果1截圖如下:作業(yè)分配實(shí)驗(yàn)結(jié)果2截圖如下:載重問題第4章結(jié)論分支限界法

28、是由“分支”策略和“限界”策略兩部分組成。“分支”策略體現(xiàn) 在對(duì)問題空間是按廣度優(yōu)先的策略進(jìn)行搜索； “限界”策略是為了加速搜索速度而采用啟發(fā)信息剪枝的策略。分支搜索的一種搜索方式FIFO,在搜索當(dāng)前E-結(jié)點(diǎn)全部?jī)鹤雍?，其兒子結(jié)點(diǎn)成為活結(jié)點(diǎn)，E-結(jié)點(diǎn)變?yōu)樗澜Y(jié)點(diǎn)；活結(jié)點(diǎn)存儲(chǔ)在隊(duì)列中，隊(duì) 首的活結(jié)點(diǎn)出隊(duì)后變?yōu)镋-結(jié)點(diǎn)，其再生成其他活結(jié)點(diǎn)的兒子直到找到問題的解 或活結(jié)點(diǎn)隊(duì)列為空搜索完畢， 例如算法 2 的載重問題。 在算法 2 中， 根據(jù)分支搜索，再加上限界策略把不符合約束條件的分支給剪掉。分支搜索的另一種搜索方式優(yōu)先隊(duì)列搜索，它通過結(jié)點(diǎn)的優(yōu)先級(jí)，可以使搜索盡快朝著解空間樹上有最優(yōu)解的分支推進(jìn)，這樣

29、當(dāng)前最優(yōu)解一定較接近真正的最優(yōu)解。其后將當(dāng)前最優(yōu)解作為一個(gè)“標(biāo)準(zhǔn)” ，對(duì)上界（或下界）不可能達(dá)到（或大于）這個(gè)“標(biāo)準(zhǔn)”的分支，則不去進(jìn)行搜索，這樣剪枝的效率更高，能較好地縮小搜索范圍，從而提高搜索效率。其中優(yōu)先隊(duì)列分支限界法進(jìn)行算法設(shè)計(jì)的有一要點(diǎn)優(yōu)先隊(duì)列組織：結(jié)點(diǎn)優(yōu)先級(jí)確定后，按結(jié)點(diǎn)優(yōu)先級(jí)進(jìn)行排序，就生成了優(yōu)先隊(duì)列。算法1 則是利用了這一思想進(jìn)行算法設(shè)計(jì)的，也通過最大效益的分配方案為最佳解的限界來進(jìn)行篩選最優(yōu)解，算法1 也利用了廣度優(yōu)先的思想進(jìn)行了算法設(shè)計(jì)。分支算法的求解目標(biāo)是找出滿足約束條件的一個(gè)解，或是在滿足條件的解中找出使用某一目標(biāo)函數(shù)值達(dá)到極大或極小的解， 即在某種意義下的最優(yōu)解， 即

30、算法 1。 相對(duì)于回溯法而言，分支限界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。僅就限界剪枝的效率而言，優(yōu)先隊(duì)列的分支限界法顯然要更充分一些?；厮莘▌t因?yàn)閷哟蔚膭澐郑梢栽谏辖绾瘮?shù)值小于當(dāng)前最優(yōu)解時(shí)，剪去以該結(jié)點(diǎn)為根的子樹，也就是節(jié)省了搜索范圍；分支限界法在這方面除了可以做到回溯法能做到的之外，若采用優(yōu)先隊(duì)列的分支限界法，有上界函數(shù)作為活結(jié)點(diǎn)的優(yōu)先級(jí)，一旦有葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，就意味著該葉結(jié)點(diǎn)所對(duì)應(yīng)的解即為最優(yōu)解，可以立刻終止其余的過程。由以上例子可以說明優(yōu)先隊(duì)列的分支限界法更像是有選擇、有目的地進(jìn)行深度優(yōu)先搜索，時(shí)間效率、空間效率都是比較高的。參考文獻(xiàn)1

31、呂國(guó)英，任瑞征，錢宇華 . 算法設(shè)計(jì)與分析. 貪婪算法2 譚浩強(qiáng) .c 程序設(shè)計(jì)（第四版）附件#include <stdio.h>#include<stdlib.h>#define MAX 100struct Queuefloat lMAX;int head,tail;void InitialQ(Queue &q)q.head = q.tail = 0;void Add(Queue &q,float i)q.lq.tail = i;q.tail+;void Delete(Queue &q,float &i)if(q.head < q.tail)i = q.lq.head;q.head +;elseexit(1);bool Empty(Queue& q)if(q.head < q.tail)return false;elsereturn true;float bestw,w100;int n;Queue Q;int main()InitialQ(Q);float c1,c2,