




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 心識(shí)與主宰心的關(guān)系再探討
- 人工智能在計(jì)算機(jī)應(yīng)用中的前沿進(jìn)展與未來挑戰(zhàn)探索
- 變電站電氣系統(tǒng)運(yùn)行與維護(hù)指南
- 精神穩(wěn)定性探討
- 橋式起重機(jī)控制系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)
- 安全生產(chǎn)座談會(huì)模板
- 小學(xué)語文必背古詩(shī)集與相關(guān)文學(xué)理論導(dǎo)讀
- 醫(yī)院違反發(fā)票管理辦法
- 運(yùn)動(dòng)營(yíng)養(yǎng)學(xué)教學(xué)中處方單設(shè)計(jì)的實(shí)踐與改進(jìn)
- 數(shù)字支付與金融科技監(jiān)管的實(shí)證研究-洞察及研究
- 成都某污水處理廠施工組織設(shè)計(jì)
- 廣告制作交貨進(jìn)度計(jì)劃及保障措施
- 2025年中職基礎(chǔ)會(huì)計(jì)試題
- 2025年江蘇省南京市中考道德與法治試卷(含解析)
- 2025至2030中國(guó)生物反饋儀行業(yè)產(chǎn)業(yè)運(yùn)行態(tài)勢(shì)及投資規(guī)劃深度研究報(bào)告
- 【公開課】牛頓第二定律+課件+-2024-2025學(xué)年高一上學(xué)期物理人教版(2019)必修第一冊(cè)+
- 預(yù)防錯(cuò)混料培訓(xùn)
- 2025年云南省中考地理試卷真題(含答案)
- 粵港澳大灣區(qū)青少年國(guó)情教育實(shí)踐基地(虎門渡口西岸物業(yè)提升改造項(xiàng)目)可行性研究報(bào)告
- DB62T 4415-2021 當(dāng)歸栽培技術(shù)規(guī)程
- 合同公司變更協(xié)議書范本
評(píng)論
0/150
提交評(píng)論