Branch-and-Bound

Branch-and-Bound 作用 特點 ‧用來改良回溯演算法。 ‧使用狀態空間樹來解決問題。 ‧不限制要怎麼走訪整棵樹。(回溯法有限制) ‧只用來解決最佳化問題。

使用 Branch-and-Bound 修剪法之最佳優先搜尋 ‧除了使用 bound 值來決定一個節點是不是 promising 之外， 　還必須加以比較每個子節點的 bound 值，然後挑選具有 　最佳 bound 值的子節點進行走訪。 ‧此方式通常會比事先決定的順序 (如 DFS) 更早到達代表 　最佳解的節點。這也是 BFS 的簡易修正版。

BFS (廣度優先搜尋)

BFS Algorithm void breadth_first_tree_search ( tree T ) { queue_of_node Q ; //宣告一個先進先出的佇列 node u , v ; initialize ( Q ) ; //初始時將佇列清空 v = root of T ; //走訪根節點 visit v ; enqueue( Q, v ) ; //將根節點存入佇列尾端 while ( ! empty ( Q ) ) { //當佇列中有節點時 dequeue ( Q, v ) ; //從佇列前端取出一個節點 v for ( each child u of v ) { visit u ; //走訪 v 的每個子節點 u enqueue ( Q , u ) ; //每走訪一個子節點 u 就將它 } //放到佇列中 }

BFS 演算法走訪樹的範例 放入 1 1 取出 1 2 3 4 取出 2 3 4 5 6 7 取出 3 4 5 6 7 8 9 取出 4 5 10 11 12 取出 5 6 7 8 9 10 11 12 取出 6 7 8 9 10 11 12 13 14 取出 7 8 9 10 11 12 13 14 取出 8~11 12 13 14 15 16 取出 12 13 14 15 16 取出 13~16

Branch-and-Bound 以 BFS 走訪法來解0-1背包問題 n=4，W=16 i Pi wi Pi/wi 1 $40 2 $20 $30 5 $6 3 $50 10 $5 4 $10 $2 將物品依照單位重量獲益比 (Pi / Wi )值由大到小排序。 狀態空間樹的每個節點內部有三個數字，由上而下為： 全部獲益 ( 即 profit ) 全部重量 ( 即 weight ) 獲益上限值 ( 即 bound )

nonpromising 策略 (1) 由樹的根節點往下走到第 i 層節點時，若已經沒空間 設 weight = 在第 i 層節點所累積的物品總重量 若 weight  W 則此節點一定是 nonpromising 。 背包載重限制

nonpromising 策略(續) (2) 從貪婪法則的觀點來找出一個較不明顯的判斷 promising 與否的方法。 總重量 第 i+1 層到 k-1 層節點為止的總重量。 因為到第 k 層就爆了。 第 1 到 i 層節點的總獲益值 可以分配給 第 k 個物品 的容量 第 i 層節點 的最大獲益 上限值。 第 k 個物品 單位重量的 獲益 前 k-1 個物品的 總獲益

branch-and-bound 以 BFS 走訪法產生的樹 profit weight bound 目前最佳值 maxprofit = 0 40 40 70 70 70 70 90 90 70 70 90 90 90 90 90 90

Breadth-first branch-and-bound Algorithm void breadth_first_branch_and_bound ( state_space_tree T , number& best ) { queue_of_node Q ; //宣告一個佇列用來擺放欲走訪的節點 node u , v ; initialize ( Q ) ; //啟始時將佇列清空 v = root of T ; enqueue ( Q , v ) ; //走訪 root 節點，並將它加入佇列尾端 best = value ( v ) ; //初始化目前最佳值 while ( ! empty ( Q ) ) { dequeue ( Q , v ) ; //從佇列前端取出一個節點 v for ( each child u of v ) { //走訪 v 的每個子節點 u if ( value ( u ) is better than best ) best = value ( u ) ; //若找到更好的結果就更新目前最佳值 if ( bound( u ) is better than best ) enqueue( Q , u ) ; //若一個節點是 promising 就把它加入佇列 } //尾端，以待下一層走訪時使用 }

演算法中的節點結構 struct node { int level ; //該節點在樹中的層級 int profit ; //目前累積的利益值 int weight ; //目前累積的物品重量值 }

使用Branch-and-bound之廣度優先搜尋法來解決0-1背包問題 問題：給定 n 個物件及其個別 weight 與 profit 值 (皆為正整數)。 給定 W 值。在總重量不超過 W 的條件下，找出一組物件 使其總獲益是最大的。 輸入：正整數 n 和 W。 陣列 w 與 p (索引均由 1 到 n，且根據p[i]/w[i]由大到小 排序過)。 輸出：正整數 maxprofit (即最大獲益)。 本演算法只找出最大獲益值，若想要輸出被挑選的物品編號，可 以自行修改。

Algorithm (續) void knapsack2 ( int n , const int p[] , const int w[] , int W , int& maxprofit ) { queue_of_node Q ; //宣告一個要存放欲走訪節點的佇列 node u , v ; initialize ( Q ) ; //初始時將佇列清空 v.level = 0 ; v.profit = 0 ; v.weight = 0 ; //將根節點初始化，並走訪它 maxprofit = 0 ; //初始化目前最佳值 enqueue ( Q , v ) ; //將根節點加入佇列尾端 while ( ! empty ( Q ) ) { //只要佇列中還有節點未走訪，就一直做下去 dequeue ( Q , v ) ; //從佇列前端取出欲走訪子節點的父節點 u.level = v.level + 1 ; //將 u 設成 v 的下一層子節點其中之一 u.weight = v.weight + w[ u.level ] ; //將 u 設成拿取下一層物品的子節點 u.profit = v.profit + p[ u.level ] ; if ( u.weight <= W && u.profit > maxprofit ) //若背包沒有爆掉，且獲 maxprofit = u.profit ; //得利益值大於最佳值，則更新它 if ( bound ( u ) > maxprofit ) enqueue ( Q , u ) ; //檢查 u 是否 promising u.weight = v.weight ; u.profit = v.profit ; //將 u 設成不拿取下一層物品 if ( bound ( u ) > maxprofit ) enqueue ( Q , u ) ; //的子節點，並檢查它 } //是否 promising }

Algorithm (續) float bound ( node u ) //回傳值就是 u 的 bound 值，呼叫者再把該值和目前最 { index j , k ; //佳值進行比較，以決定 u 是否為 promising int totweight ; float result ; if ( u.weight >= W ) return 0 ; //背包爆掉則傳回 bound = 0 else { result = u.profit ; //先把 bound 值初設為到 u 節點為止的總共獲益值 j = u.level + 1 ; totweight = u.weight ; while ( j <= n && totweight + w[j] <= W ) { totweight = totweight + w[j] ; //盡可能多拿取一些物品 result = result + p[j] ; //直到物品都拿光或是背包 j ++ ; //爆掉為止 } k = j ; if ( k <= n ) result = result + (W-totweight)*(p[k]/w[k]) ; //加上第 k 個 return result ; //物品的部份利益 下一頁

使用 Branch-and-bound 修剪法之最佳優先搜尋 profit weight bound 目前最佳值 maxprofit = 0 40 40 90 70 70 總共走訪了 11個節點， 最佳值=90 90 70 70 上一頁 90 90 下一頁

Best-first Branch-and-bound Algorithm void best_first_branch_and_bound ( state_space_tree T , number& best ) { priority_queue_of_node PQ ; //使用優先權佇列來存放欲走訪的節點 node u , v ; initialize ( PQ ) ; v = root of T ; //先走訪根節點，並初設目前最佳值 best best = value ( v ) ; insert ( PQ , v ) ; //將根節點插入優先權佇列中 while ( ! empty ( PQ ) ) { //只要優先權佇列中還有未走訪節點就繼續做 remove ( PQ , v ) ; //取出佇列中優先權 (即 bound) 最高的節點 if ( bound ( v ) is better than best ) //若它仍然還是 promising 則往 for ( each child u of v ) { //下層走訪它的每個子節點 if ( value ( u ) is better than best ) best = value ( u ) ; //更新最佳值 if ( bound ( u ) is better than best ) insert ( PQ , u ) ; //若 u 為 promising，則將 } // 它插入佇列中 }

使用 Branch-and-bound 並以最佳優先搜尋法來解決0-1背包問題 狀態空間樹中的節點結構 struct node { int level ; //節點在樹中的層級 int profit ; //到目前為止的總獲利值 int weight ; //到目前為止的總重量值 float bound ; //節點的最大獲利能力值 }

Algorithm (續) void knapsack3 ( int n , const int p[] , const int w[] , int W , int& maxprofit ) { priority_queue_of_node PQ ; node u , v ; initialize ( PQ ) ; v.level = 0 ; v.profit = 0 ; v.weight = 0 ; maxprofit = 0 ; v.bound = bound ( v ) ; //走訪根節點，並將它加入優先權佇列中 insert ( PQ , v ) ; while ( ! empty ( PQ , v ) ) { remove ( PQ , v ) ; //將 bound 值最高的節點取出來 if ( v.bound > maxprofit ) { //如果它仍然是 promising 就往下層展開 u.level = v.level + 1 ; u.weight = v.weight + w[ u.level ] ; u.profit = v.profit + p[ u.level ] ; //先走訪左子節點 if ( u.weight <= W && u.profit > maxprofit ) maxprofit = u.profit ; //更新最佳值

Algorithm (續) u.bound = bound ( u ) ; if ( u.bound > maxprofit ) //若左子節點 promising，則加 insert ( PQ , u ) ; //入優先權佇列中 u.weight = v.weight ; u.profit = v.profit ; //走訪右子節點 if ( u.bound > maxprofit ) //若右子節點 promising，則加 } bound 函式同 Algorithm 6.1，請自行參考。

優先權佇列變化圖 (0,0) (0,0) 115 (1,2) (1,1) (1,2) 115 82 40 40 (2,1) (2,1) (2,2) (1,2) 115 98 82 (2,2) (2,2) (1,2) (3,2) 70 70 98 82 80 (3,3) (3,3) (1,2) (3,2) 98 82 80 90 (1,2) : 82 < 90 nonpromising 70 90 70 (1,2) (3,2) 82 80 (3,2) : 80 < 90 nonpromising (3,2) 80 90 90

售貨員旅行問題 V1 V2 V4 V3 V3 V5 此相鄰矩陣代表了 所有頂點間皆有邊線 相連的圖 左圖的最佳旅程 10 7 V4 V3 V3 7 2 V5 此相鄰矩陣代表了 所有頂點間皆有邊線 相連的圖 左圖的最佳旅程 若城市數目很多，且是高度連結的，那麼使用回溯法會產 生太多旅行路線。因此改用branch-and-bound。

具有5個頂點的售貨員旅行問題的對應展開樹

計算狀態樹中每個節點的bound值 在這個問題中求的 bound 值是由該節點繼續往下層節點走訪 個節點才是 promising。 在任意旅程中，從每個頂點離開時，應採用其發出之最短邊 線： V1 minimum ( 14, 4, 10, 20 ) = 4 V2 minimum ( 14, 7, 8, 7 ) = 7 V3 minimum ( 4, 5, 7, 16 ) = 4 => 4+7+4+2+4=21 V4 minimum ( 11, 7, 9, 2 ) = 2 一個旅程的長度下限 V5 minimum ( 18, 7, 17, 4 ) = 4 就是這些最小值的總 和，但不代表真有這 條路徑，可能不存在

計算狀態樹中每個節點的bound值(續) V1 14 (已固定不能變動) V2 minimum ( 7 , 8 , 7 ) = 7 V3 minimum ( 4 , 7 , 16 ) = 4 V4 minimum ( 11 , 9 , 2 ) = 2 V5 minimum ( 18 , 7 , 17 , 4 ) = 4 bound 值 = 14+7+4+2+4 = 31

計算狀態樹中每個節點的bound值(續) V1 14 (已固定不能變動) V2 7 (已固定不能變動) V3 minimum ( 7 , 16 ) = 7 V4 minimum ( 11 , 2 ) = 2 V5 minimum ( 18 , 4 ) = 4 bound 值 = 14+7+7+2+4 = 34

狀態樹與 Bound 值 最佳解 = 無限大 37 31 31 31 31 30 30 31 31 5, 4

Algorithm 使用 Branch-and-bound 及最佳搜尋法來解決售貨員旅行問題 狀態樹中的節點結構 struct node { int level ; //節點在樹中的層級 ordered set path ; //到該節點為止的旅程路徑 number bound ; //該節點的旅程下限值 }

Algorithm (續) 問題：在一有向權重圖中找出一條最佳旅程。weight 必須為 非負整數。 由 1 到 n ，W[i][j] 代表由第 i 個頂點連到第 j 個頂點之 weight )。 該圖中的頂點數，n 。 輸出：變數 minlength，其值為一條最佳旅程的長度。 變數 opttour，其值為一條最佳旅程。

Algorithm (續) void travel2 ( int n , const number W[][] , ordered_set& opttour , number& minlength ) { priority_queue_of_node PQ ; node u , v ; initialize ( PQ ) ; v.level = 0 ; v.path = [1] ; // 令頂點 1 為起點 (即根節點) v.bound = bound( v ) ; //計算根節點的 bound 值 minlength = 無限大 ; //初始化最佳值 insert ( PQ , v ) ; while ( ! empty ( PQ ) ) { remove ( PQ , v ) ; //取出下一個要展開的節點 if ( v.bound < minlength ) { //如果它仍然是 promising u.level = v.level + 1 ; //開始計算它所有下一層節點 for ( all i such that 2 <= i <= n && i is not in v.path ) { u.path = v.path ; put i at the end of u.path ; //將 u 的路徑寫入

Algorithm (續) if ( u.level == n - 2 ) { //如果 u 在倒數兩層就直接處理 put index of only vertex not in u.path at the end of u.path ; //將最後一頂點加入路徑 put 1 at the end of u.path ; //把頂點 1 加入 if ( length ( u ) < minlength ) { minlength = length ( u ) ; //更新最佳值 opttour = u.path ; //更新最佳路徑 } else { //還不到旅程的終點 u.bound = bound ( u ) ; //計算 bound 值 if ( u.bound < minlength ) //若 promising insert ( PQ , u ) ; //放入優先權佇列中 } }