算法分析——5.ppt

1、算法設(shè)計與分析,分支限界法,分支限界法,分支限界法 與回溯法類似，都是在問題的解空間樹上搜索問題解的算法； 求解目標(biāo)：找出滿足約束條件的解 可行解或最優(yōu)解 搜索策略 根據(jù)限界函數(shù)值，剔除那些導(dǎo)致不可行解或非最優(yōu)解的子結(jié)點(diǎn)，使搜索過程僅限制在剩余的分支內(nèi)進(jìn)行；,提綱,分支限界法的基本思想 實(shí)例分析 本章小結(jié),提綱,分支限界法的基本思想 實(shí)例分析 本章小結(jié),分支限界法 Vs 回溯法,相同點(diǎn)： 兩者在進(jìn)行問題求解前，都需要完成解空間的定義和組織； 都是通過在解空間搜索來尋找問題的解；,分支限界法 Vs 回溯法,不同點(diǎn)： 搜索方式 回溯法：深度優(yōu)先； 分支限界法：廣度優(yōu)先； 搜索策略 回溯法：根據(jù)剪枝

2、函數(shù)，選擇下一個擴(kuò)展接點(diǎn)并按深度優(yōu)先方式進(jìn)行搜索； 分支限界法：在擴(kuò)展結(jié)點(diǎn)處，先產(chǎn)生其所有的子結(jié)點(diǎn)（分支），然后根據(jù)限界函數(shù)，確定哪些子結(jié)點(diǎn)將導(dǎo)致不可行解或非最優(yōu)解，將這些子結(jié)點(diǎn)剔除，用剩下的子結(jié)點(diǎn)構(gòu)造當(dāng)前的活結(jié)點(diǎn)表，然后從該表中取一個結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述過程；,分支限界法的主要分類,分支限界法的主要分類 根據(jù)從活結(jié)點(diǎn)表中選擇下一個擴(kuò)展結(jié)點(diǎn)的方式 隊列式FIFO分支限界法 優(yōu)先隊列式分支限界法,隊列式FIFO分支限界法,隊列式FIFO分支限界法 算法思想：將活結(jié)點(diǎn)表組織成一個隊列，并按隊列的先進(jìn)先出FIFO原則選取下一個結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)；,優(yōu)先隊列式分支限界法,優(yōu)先隊列式分支限

3、界法 算法思想：將活結(jié)點(diǎn)表組織成一個優(yōu)先隊列，并按優(yōu)先隊列中規(guī)定的結(jié)點(diǎn)優(yōu)先級，選取剩余隊列中優(yōu)先級最高的下一個結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)；,實(shí)例說明,實(shí)例說明 0-1背包問題 TSP問題,實(shí)例說明,實(shí)例說明 0-1背包問題 TSP問題,實(shí)例說明0-1背包問題,n=3的0-1背包問題 w=16,15,15 p=45,25,25 c=30,解空間為： (0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1),n=3的0-1背包問題的解空間樹,活結(jié)點(diǎn)&當(dāng)前擴(kuò)展結(jié)點(diǎn),A,1,0,1,1,1,1,1,1,0,0,0,0,0,0

4、,A,B,1,0,1,1,1,1,1,1,0,0,0,0,0,0,活結(jié)點(diǎn)隊列,A,B,C,1,0,1,1,1,1,1,1,0,0,0,0,0,0,活結(jié)點(diǎn)隊列,A,B,C,E,1,0,1,1,1,1,1,1,0,0,0,0,0,0,活結(jié)點(diǎn)隊列,A,B,C,E,F,1,0,1,1,1,1,1,1,0,0,0,0,0,0,活結(jié)點(diǎn)隊列,A,B,C,E,G,1,0,1,1,1,1,1,1,0,0,0,0,0,0,活結(jié)點(diǎn)隊列,最優(yōu)解為： (0,1,1),對應(yīng)的價值為50,A,1,0,1,1,1,1,1,1,0,0,0,0,0,0,A,B,1,0,1,1,1,1,1,1,0,0,0,0,0,0,極大堆,A,

5、B,C,E,1,0,1,1,1,1,1,1,0,0,0,0,0,0,極大堆,A,B,C,1,0,1,1,1,1,1,1,0,0,0,0,0,0,極大堆,A,B,C,F,1,0,1,1,1,1,1,1,0,0,0,0,0,0,極大堆,A,B,C,E,G,1,0,1,1,1,1,1,1,0,0,0,0,0,0,最優(yōu)解為： (0,1,1),對應(yīng)的價值為50,極大堆,實(shí)例說明,實(shí)例說明 0-1背包問題 TSP問題,實(shí)例說明TSP問題,20,30,10,6,5,4,4頂點(diǎn)的無向帶權(quán)圖,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,當(dāng)前擴(kuò)展結(jié)點(diǎn),1,3,4,2,3,4,3,2,4,2,3

6、,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,活結(jié)點(diǎn)隊列,1,3,4,2,3,4,3,2,4

7、,2,3,2,2,3,4,4,極小堆,當(dāng)前擴(kuò)展結(jié)點(diǎn),1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,極小堆,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,極小堆,1,3,4,2,3,4,3,2,4,2,3,2,2,3,4,4,極小堆,提綱,分支限界法的基本思想 實(shí)例分析 本章小結(jié),實(shí)例分析,單源最短路徑問題 裝載問題 布線問題 0-1背包問題 最大團(tuán)問題 TSP問題 電路板排列問題 批處理作業(yè)調(diào)度,單源最短路徑,算法思想,算法思想 采用優(yōu)先隊列式分支限界法 以當(dāng)前結(jié)點(diǎn)所對應(yīng)的路徑長度為參考標(biāo)準(zhǔn)(路徑長度越短，優(yōu)先級越高） 限界函數(shù)設(shè)計 利用已經(jīng)獲得的當(dāng)前最短路

8、徑長度Lmin為基準(zhǔn)，對那些結(jié)點(diǎn)所對應(yīng)路徑長度大于Lmin的情況，剪去以該結(jié)點(diǎn)為根的子樹； 利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝 對于通過不同路徑到達(dá)同一頂點(diǎn)的兩條路徑，路徑長度短的結(jié)點(diǎn)（控制結(jié)點(diǎn)）控制路徑長度長的結(jié)點(diǎn)（被控制結(jié)點(diǎn)） 將被控制結(jié)點(diǎn)所對應(yīng)的子樹剪去,實(shí)例分析,找從頂點(diǎn)“1”到頂點(diǎn)“5”的最短路徑,有向圖G的單源最短路徑問題的解空間樹,1,2,5,5,5,4,3,3,5,當(dāng)前擴(kuò)展結(jié)點(diǎn),A、B是兩個可行的子結(jié)點(diǎn)，被加入到極小堆中。由于A是當(dāng)前堆中具有最小路徑長度的結(jié)點(diǎn)（路徑長度為10），所以處于堆頂。 C為葉結(jié)點(diǎn)，表示得到一條從“1”到“5”的路徑，路徑長度為100,極小堆,極小堆,1,2,

9、5,5,5,4,3,3,5,當(dāng)前擴(kuò)展結(jié)點(diǎn),一個可行的子結(jié)點(diǎn)，被加入到極小堆中。由于D結(jié)點(diǎn)所對應(yīng)路徑長度為60，所以被加入到B結(jié)點(diǎn)之后，B是當(dāng)前堆中具有最小路徑長度的結(jié)點(diǎn)（路徑長度為30），處于堆頂,極小堆,極小堆,1,2,5,5,5,4,3,3,5,當(dāng)前擴(kuò)展結(jié)點(diǎn),E為可行的子結(jié)點(diǎn)，被加入到極小堆中。由于E結(jié)點(diǎn)所對應(yīng)路徑長度為50（小于D結(jié)點(diǎn)所對應(yīng)的路徑長度），而且D、E在圖G中對應(yīng)同一個頂點(diǎn)3 結(jié)點(diǎn)D被結(jié)點(diǎn)E控制，剪去以D結(jié)點(diǎn)為根的子樹； F結(jié)點(diǎn)為葉結(jié)點(diǎn)，且對應(yīng)的從”1“到”5“的路徑長度為90，小于已知的最短路徑長度 用該路徑最為當(dāng)前已知的最優(yōu)解 因此，當(dāng)前極小堆中只剩下E,極小堆,極小堆,

10、極小堆,1,2,5,5,5,4,3,3,5,當(dāng)前擴(kuò)展結(jié)點(diǎn),到達(dá)葉結(jié)點(diǎn)處，由于H結(jié)點(diǎn)所對應(yīng)路徑長度為60（小于F結(jié)點(diǎn)所對應(yīng)的路徑長度） 用該路徑取代已知的最短路徑，作為當(dāng)前已知的最優(yōu)解,極小堆,極小堆,100,10,50,10,30,60,20,一個帶權(quán)有向圖,有向圖G的單源最短路徑問題的解空間樹,最優(yōu)解,裝載問題,問題描述,求解出發(fā)點(diǎn),容易證明，如果一個給定的裝載問題有解，則采用以下策略可以得到最優(yōu)裝載方案： 首先將第一艘船盡可能裝滿； 等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近C1 將剩余的集裝箱裝上第二艘船；,算法思想,算法思想 解空間樹 子集樹 分支限界法 隊列式 優(yōu)

11、先隊列式,隊列式,隊列式 算法實(shí)現(xiàn)：檢查當(dāng)前結(jié)點(diǎn)的深度 i=n 表示當(dāng)前活結(jié)點(diǎn)為葉結(jié)點(diǎn)，不需要加入到活結(jié)點(diǎn)隊列中，只要檢查該結(jié)點(diǎn)表示的可行解是否優(yōu)于當(dāng)前最優(yōu)解，并適時更新當(dāng)前最優(yōu)解 in 表示當(dāng)前結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)，應(yīng)加入到活結(jié)點(diǎn)隊列中,限界函數(shù)設(shè)計,限界函數(shù) 是否超過船的負(fù)荷限制 根據(jù)當(dāng)前已知的最優(yōu)解bestw來進(jìn)行剪枝 當(dāng)前擴(kuò)展結(jié)點(diǎn)所對應(yīng)的重量ew； 剩余集裝箱的重量r； 如果ew+r=bestw，則進(jìn)行剪枝（剪去右子樹，因為右子樹為0，表示下一個集裝箱沒有被選中） 提早更新bestw（在每次進(jìn)入左子樹時更新）,優(yōu)先隊列式,優(yōu)先隊列式 思路：根據(jù)活結(jié)點(diǎn)X在優(yōu)先隊列中的優(yōu)先級 優(yōu)先級定義 從根結(jié)

12、點(diǎn)到結(jié)點(diǎn)X的路徑所對應(yīng)的載重量+剩余集裝箱的重量 優(yōu)先隊列中優(yōu)先級最大的活結(jié)點(diǎn)成為下一個擴(kuò)展結(jié)點(diǎn) 一旦有一個葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，則該葉結(jié)點(diǎn)所對應(yīng)的解就是最優(yōu)解,優(yōu)先級策略的實(shí)現(xiàn)方式,優(yōu)先級策略的實(shí)現(xiàn)方式 第一種，在結(jié)點(diǎn)優(yōu)先隊列的每一個活結(jié)點(diǎn)中保存從解空間樹的根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑； 在到達(dá)最優(yōu)值的葉結(jié)點(diǎn)時，在該結(jié)點(diǎn)處同時得到相應(yīng)的最優(yōu)解； 第二種，在算法的搜索過程中保存當(dāng)前已構(gòu)造出的部分解空間樹。 當(dāng)達(dá)到最優(yōu)值的葉結(jié)點(diǎn)時，可以在解空間樹中從該葉結(jié)點(diǎn)開始向根結(jié)點(diǎn)回溯，從而構(gòu)造出最優(yōu)解。 教材中所選用的方案,布線問題,布線問題,布線問題 問題描述：確定連接方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線路徑

13、。 布線時，電路只能沿直線或直角布線 其他線路不允許穿過已布線的方格,a,b,算法設(shè)計思想,算法設(shè)計思想 解空間：圖 搜索策略：隊列式分支限界法 從起始位置a開始，將其作為第一個擴(kuò)展結(jié)點(diǎn)。與該擴(kuò)展結(jié)點(diǎn)相鄰并且可達(dá)的方格（有相鄰邊且未被標(biāo)記）作為可行結(jié)點(diǎn)被加入到活動結(jié)點(diǎn)隊列中，并且將這些方格標(biāo)記為1（即從起始方格a到這些方格的距離為1）。 然后，算法從活結(jié)點(diǎn)隊列中取出隊首結(jié)點(diǎn)作為下一個擴(kuò)展結(jié)點(diǎn)，并將與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰且可達(dá)的方格標(biāo)記為2，并存入活結(jié)點(diǎn)隊列。 該過程一直持續(xù)，直到算法搜索到目標(biāo)方格b或活結(jié)點(diǎn)隊列為空時停止。,相鄰可達(dá)的概念,滿足相鄰可達(dá)條件,不滿足相鄰可達(dá)條件,5,6,算法實(shí)現(xiàn)&復(fù)

14、雜性分析,算法實(shí)現(xiàn) 參看教材page212-216 注意移動方向的設(shè)置以及布線長度的設(shè)置 算法復(fù)雜性分析 擴(kuò)展每個結(jié)點(diǎn)需O(1)時間，算法共需耗時O(mn)。 構(gòu)造相應(yīng)的最短距離需要O（L）時間 L是最短布線路徑長度,實(shí)際的電路布線問題,實(shí)際的電路布線問題 參看提供的參考文獻(xiàn) 從“/算法分析/參考資料”處下載,批處理作業(yè)調(diào)度,問題描述,對于批處理作業(yè)調(diào)度問題，可以證明存在最佳作業(yè)調(diào)度使得在機(jī)器1和機(jī)器2上作業(yè)以相同次序完成。,舉例,上述3個作業(yè)有6種不同的調(diào)度方案 1-2-3：19 1-3-2：18 2-1-3：20 2-3-1：21 3-1-2：19 3-2-1：21,最優(yōu),3+7+8=18,算法設(shè)計思想,算法設(shè)計思想 用優(yōu)先隊列式分支限界法 解空間樹：