算法設(shè)計(jì)與分析 課件 第五章 分支限界

算法設(shè)計(jì)與分析分支限界的思想分支限界法是一種用于解決優(yōu)化問題的算法，通過分支來生成解的候選，并使用界限來排除不可能的解，從而有效搜索地找到最優(yōu)解。簡單0/1背包問題的示例：有一個(gè)容量為10的背包，和三個(gè)物品：物品1：重量6，價(jià)值30物品2：重量5，價(jià)值14物品3：重量4，價(jià)值16求：先擇合適物品，轉(zhuǎn)入背包，價(jià)值最大的組合。分支限界的簡單示例-回溯法圖每個(gè)節(jié)點(diǎn)顯示了當(dāng)前的剩余容量(W)和累計(jì)價(jià)值(V)。樹節(jié)點(diǎn)按層從字母A開始編號(hào)。節(jié)點(diǎn)A：起始點(diǎn)節(jié)點(diǎn)N：最優(yōu)解節(jié)點(diǎn)H：無效解灰色節(jié)點(diǎn)：搜索節(jié)點(diǎn)分支限界的簡單示例-分支限界圖W:剩余重量V:當(dāng)前價(jià)值UB:上界（當(dāng)前價(jià)值+剩余物品的價(jià)值上界），采用分?jǐn)?shù)背包法計(jì)算上界。節(jié)點(diǎn)A：起始點(diǎn)；節(jié)點(diǎn)F：最優(yōu)解；節(jié)點(diǎn)D：超重節(jié)點(diǎn)；灰白色節(jié)點(diǎn)(C，G)：被剪枝的分支。簡單示例-分支限界與回溯法比較W:剩余重量V:當(dāng)前價(jià)值UB:上界（當(dāng)前價(jià)值+剩余物品的價(jià)值上界）粉色節(jié)點(diǎn)A：起始點(diǎn)；紅色節(jié)點(diǎn)D：超重節(jié)點(diǎn)；綠色節(jié)點(diǎn)：最優(yōu)解；灰色節(jié)點(diǎn)(C，G)：被剪枝的分支。這是因?yàn)樗鼈兊纳辖绲陀谝阎淖罴呀猓?6），所以不需要進(jìn)一步探索。通過使用準(zhǔn)確的上界，算法能更有效地剪枝，減少需要搜索的節(jié)點(diǎn)數(shù)量。每個(gè)節(jié)點(diǎn)顯示了當(dāng)前的剩余容量(W)和累計(jì)價(jià)值(V)。粉色節(jié)點(diǎn)(A)：起始點(diǎn)紅色節(jié)點(diǎn)(H)：超重節(jié)點(diǎn)綠色節(jié)點(diǎn)(N)：最優(yōu)解灰色節(jié)點(diǎn)：搜索節(jié)點(diǎn)除了超重條件觸發(fā)剪枝之外，其他節(jié)點(diǎn)都要搜索到。示例中的兩個(gè)算法采用的可能解樹相同（選擇或不選擇產(chǎn)生的完全二叉樹），搜索方法（DFS）一樣。加上一個(gè)限界條件后，搜索效率提高了很多。求解問題的核心除了構(gòu)造可能解樹，還有設(shè)計(jì)好的限界條件！物流派送問題-限界條件的設(shè)計(jì)最小出邊限界法：對(duì)于當(dāng)前訪問的城市，可以預(yù)先計(jì)算其到其他所有未訪問城市的最短距離，然后用這個(gè)距離加上當(dāng)前路徑長度，如果結(jié)果已經(jīng)超過當(dāng)前最優(yōu)路徑長度，那么可以剪枝。這種剪枝策略利用了圖的局部信息，可以有效減少搜索空間。物流派送問題-限界條件的設(shè)計(jì)未訪問城市最小出邊之和限界法：對(duì)于當(dāng)前訪問的城市，可以預(yù)先計(jì)算當(dāng)前城市的最小出邊、所有未訪問城市的最小出邊，然后用這些最小出邊的累加和再加上當(dāng)前路徑長度，如果結(jié)果已經(jīng)超過當(dāng)前最優(yōu)路徑長度，那么可以剪枝。剪枝條件為：從當(dāng)前城市出發(fā)，再走一遍未訪問的城市的可行路線所經(jīng)過的邊長之和一定是大于當(dāng)前城市的最小出邊再加上所有未訪問城市的最小出邊。這種剪枝策略利用了圖的部分信息，也可以有效減少搜索空間。由于未訪問城市最小出邊之和比未訪問城市最小出邊數(shù)值更大，直觀上認(rèn)為可以更早的提前剪枝，提高算法的效率。物流派送問題-限界條件的設(shè)計(jì)未訪問城市最小出邊之和限界法：物流派送問題-限界條件的設(shè)計(jì)BFS（廣度優(yōu)先搜索）方法和未訪問城市最小出邊之和的限界法：

當(dāng)前路徑長度加所有未訪問城市最小出邊之和作為搜索的選擇條件和剪枝的下限界。

代碼中使用了一個(gè)優(yōu)先隊(duì)列（使用最小堆實(shí)現(xiàn)），以實(shí)現(xiàn)廣度優(yōu)先搜索的貪心選擇。隊(duì)列中的元素按照預(yù)估的代價(jià)

(estimatedCost)

排序，使得具有較小預(yù)估代價(jià)的狀態(tài)被優(yōu)先探索。搜索中某節(jié)點(diǎn)的下限界大于當(dāng)前最佳路徑長度，則剪除以此節(jié)點(diǎn)為父節(jié)點(diǎn)的子樹。這有助于減少搜索空間并提高效率。物流派送問題-限界條件的設(shè)計(jì)BFS（廣度優(yōu)先搜索）方法和未訪問城市最小出邊之和的限界法：

分支限界算法總結(jié)

0/1背包問題的處理：上界條件：在處理0-1背包問題時(shí)，使用了上界條件來進(jìn)行剪枝。上界是指在當(dāng)前節(jié)點(diǎn)下，理論上可能獲得的最高價(jià)值。如果某個(gè)節(jié)點(diǎn)的上界已經(jīng)低于已知的最優(yōu)解，那么這個(gè)節(jié)點(diǎn)及其所有子節(jié)點(diǎn)都不會(huì)產(chǎn)生更高的價(jià)值，因此可以被剪枝。物流派送問題的處理：下界條件：在處理物流派送問題時(shí)，使用了下界條件來實(shí)施剪枝。下界是指在當(dāng)前決策樹節(jié)點(diǎn)下，可能獲得的最低成本或最小代價(jià)。如果某個(gè)節(jié)點(diǎn)的下界已經(jīng)高于已知的最優(yōu)解，那么這個(gè)節(jié)點(diǎn)及其所有子節(jié)點(diǎn)