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

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

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

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

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

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

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

7、 可能的路徑，不便于在搜索過程中對不同的解進行比較，只能在搜索到所有解的情 況下，才能通過比較確定哪個是最優(yōu)解。這類問題更適合用廣度優(yōu)先策略搜索，因 為在擴展結(jié)點時，可以在E-結(jié)點的各個子結(jié)點之間進行必要的比較， 有選擇地進行 下一步擴展。分支限界法就是一種比較好的解決最優(yōu)化問題的算法。分支限界法是 由“分支”策略和“限界”策略兩部分組成。“分支”策略體現(xiàn)在對問題空間是按廣度優(yōu)先的策略進行搜索；“限界”策略是為了加速搜索速度而采用啟發(fā)信息剪枝 的策略。第2章分支限界法的理論知識2.1 問題的解空間樹子集樹在FIFO分支搜索方法中，在搜索當前E-結(jié)點全部兒子后，其兒子成為活結(jié)點，目結(jié)點變?yōu)樗澜Y(jié)點

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

9、 ,x 為 E的兒子聞x)為結(jié)點x下界函數(shù)，當其值比u大時,不可能為最優(yōu)解,不斷續(xù)搜索此分 支 , 該結(jié)點不入隊; 當其值比 u 小時 , 可能達到最優(yōu)解, 斷續(xù)搜索此分支, 該結(jié)點入隊 ;cost(X) 當前葉結(jié)點所在分支的解.search(T) leaf =0;初始化隊 ;ADDQ(T); parent(E) =0; while ( 隊不空 ) DELETEQ(E) for (E 的每個兒子X)if (s(X) <u) ADD Q(X);parent(X) =E;if (X是解結(jié)點) 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)大致相同只是擴展結(jié)點的順序不同 , 因而存儲活結(jié)點的數(shù)據(jù)結(jié)構(gòu)不同 .FIFO 分支 - 限界算法用隊存儲活結(jié)點 ,LC 分支 - 限界算法用堆存儲活結(jié)點 , 以保證比較優(yōu)良的結(jié)點行被擴展且對于LC分支-限界算法，當擴展到葉結(jié)點就已經(jīng)找到最優(yōu)解，可以停止搜索.2.2 分支限界法的一般性描述分支限界有3種不同的搜索方式：FIFO、LIFO和優(yōu)先隊列。對于先進先出

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

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

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

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

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

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

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

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

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

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

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

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

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

24、如下 :#include <iostream.h>#include <stdlib.h>#include <stdio.h>int n; / 工人和任務(wù)的數(shù)目int c10001000;unsigned int mincost = 100000; / 設(shè)置的初始值, 大于可能的費用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(" 輸入每個工人完成各個工作的費用 :n");for(i=0;i<n;i+) / 設(shè)置每個任務(wù)由不同工人承擔時的費用及全局數(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(" 最小總費用 :%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) 時，找出 0 號工人分別執(zhí)行0， 1， 2， 3， 4 號任務(wù)時總花費最小/ 第二次 for(i=1) 時， 找出 1 號工人分別執(zhí)行除0號工人的任務(wù)以外任務(wù)時總花費最/ 小，并與 i=0 時的總花費最小比較/./ 第 5 次 for(i=4) 時， 找出總花費最小， 并與上次的總花費最小比較Plan(k+1,cost+cki);workeri = 0;- 11 -taskk = 0;算法2如附件：3.5 測試結(jié)果與分析實驗結(jié)果1截圖如下:作業(yè)分配實驗結(jié)果2截圖如下:載重問題第4章結(jié)論分支限界法

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

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

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

31、呂國英，任瑞征，錢宇華 . 算法設(shè)計與分析. 貪婪算法2 譚浩強 .c 程序設(shè)計（第四版）附件#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,