Backtracking & Branch-and-Bound - Sharon Peng

文章推薦指數: 80 %
投票人數:10人

物品的重量(Weight) · 最大獲利(Maxprofit) · 背包可以承載的重量(W) · 界線(Bound,可以是上界或下界,看題目需求) · 尋訪樹(Tree)時,使用BFS. GetstartedOpeninappSharonPengSigninGetstarted106FollowersAboutGetstartedOpeninappBacktracking&Branch-and-BoundSharonPengJun24,2021·7minread這次提到的是BacktrackingAlgorithm和Branch-and-Bound,因為感覺很少人用中文去解釋,所以以下皆用英文來表示。

如果是第一次看到這個演算法,大概會很陌生,也不知道他在做什麼。

所以這次著重用例題來展現他們的精神!先說個輕鬆的東西,BacktrackingAlgorithm有時也會稱為TryandError,也就是:嘗試→失敗→再嘗試→失敗→再嘗試→直到成功。

早期的象棋遊戲,五子棋遊戲,大多都是用BacktrackingAlgorithm來實作的~~Outline:問題闡述(0–1knapsackproblem)Backtracking的特色Backtracking使用說明(搭配0–1knapsackproblem)Branch-and-Bound的特色Branch-and-Bound使用說明(搭配0–1knapsackproblem)問題闡述(0–1knapsackproblem)下方兩個例題都使用0–1背包問題,所以先說明一下問題的目的是甚麼0—1knapsack(0—1背包問題)小偷去別人家偷東西(有金塊、銀塊、銅塊),要怎麼樣可以偷到最多東西(以道德上來說,不是個太好的範例)在偷東西,有一些條件:背包有限重,這也代表,不可以全部都偷走,需要在裡面做選擇。

實際範例:注意:0–1knapsackproblem和Fractionalknapsackproblem的不同,0–1knapsackproblem中的「0–1」代表的是,「全不拿」或「全拿」;但是Fractionalknapsackproblem中fractional代表的是分數,也就是,我可以拿取「部分物品」。

結論:Fractionalknapsackproblem的獲利數≥0–1knapsackproblem允許「部分拿取」與「全拿或不拿」的差別。

Backtracking的特色—TryandError—使用DFS(Depth-FirstSearch),在程式方面以Stack來實作。

使用Backtracking解此題目時,所需的工具:物品的重量(Weight)最大獲利(Maxprofit)背包可以承載的重量(W)界線(Bound,可以是上界或下界,看題目需求)尋訪樹(Tree)時,使用DFS解題目時以「樹」的形式來呈現,其中每一個節點(Node),有幾個要素(作為比較依據)。

(如下圖👇)為什麼UpperBound(最多可以拿到)是115?注意:一開始計算的時候,先不用注意最後一欄pi/wi,等到裝不下之後,在看pi/wi會比較好,要不然剛開始的計算,可能會理解錯誤。

記得!!這邊的物品個數皆「只有」一個!「只有」一個!拿完就沒有了所以不會出現袋子16公斤,直接拿8個金塊的狀況產生。

要偷東西,從價值最高的開始!偷了一塊金塊後:目前獲利:$40背包剩下的重量:16–2=14(kg)偷了一塊銀塊後:目前獲利:$40+$30=$70背包剩下的重量:14–5=9(kg)要偷銅塊時,發現背包放不下了,所以拿出刀子,要切開一點帶走:這時候需要用到pi/wi的性質:剩下9(kg)可以裝,而銅塊均等切開後,一塊為$5。

可以「部分拿取獲得」$45目前獲利:$70+$45=$115背包剩下的重量:9–9=0(kg)Backtracking使用說明(搭配0–1knapsackproblem)畫「樹」時間~~為什麼做到某些節點就停止了,因為Node我們有一些限制:(請參考下圖)1.「物品的重量」≥「背包的重量」2.「最大獲利」≥「界線(Bound)」這邊「界線(Bound)」代表,如果我可以「拿刀切開這項物品來獲利的話」,所得到的最大值。

可以想成,拿刀來切算是一種作弊的方式。

而題目的原意:東西,只能選擇「偷」或「不偷」(怕會不小心忘記這點,才一直強調)以上面範例來說明:如果現在最大獲利是$80,如果偷偷作弊的最大值也是$80,那根本就沒有作弊的必要的,所以直接停止,往回走。

Branch-and-Bound的特色—使用BFS(Breadth-FirstSearch),在程式方面以Priority-Queue來實作。

用Branch-and-Bound解此題目時,所需的工具:物品的重量(Weight)最大獲利(Maxprofit)背包可以承載的重量(W)界線(Bound,可以是上界或下界,看題目需求)尋訪樹(Tree)時,使用BFS計算Node最大獲利和Backtracking相同,所以這邊就省略了~~和Backtracking最大的不同,莫過於是他們走訪Tree的方式:Backtracking:會往下走到不能在走,才回頭,再往下一個Node移動。

Branch-and-Bound:會一次考慮兩個小孩(child),如果有兄弟(sibling)也會一起考慮,然後再比較。

比較出哪一個「未來獲利空間比較大」後,再選「較有未來的那個Node」。

(這邊看不懂的話沒關係,看到圖應該就可以懂了)Branch-and-Bound使用說明(搭配0–1knapsackproblem)BFS在這邊使用PriorityQueue,如果有點不懂的話,可以先去了解一下,再回來看,會更加清楚。

簡單來說就是,在這個Queue中,會把值最大的放在最前面。

所以在執行中,再做比較時,會以整體的概念來看。

一開始,Root節點會直接產生兩個Child,並在這兩個Child間比較,哪一個「未來獲利會比較大」,並選則獲利大的那項。

得到,右邊節點的獲利會比較大(透過他們Bound的比較得到)相較一個未來最多可以獲得$115→選他。

另一個未來則是最多會獲得$82→沒有未來。

從紅色Node再產生兩個Child,再比較兩個child,外加自己的兄弟也要一併比較(Priority-Queue的特性),哪一個「未來獲利會比較大」。

得到,右邊節點(綠色)的獲利會比較大(透過他們Bound的比較得到)從紅色Node再產生兩個Child,比較兩個child,外加自己的兄弟,哪一個「未來獲利會比較大」。

得到,右邊節點(綠色)的獲利會比較大,但是這邊我們發現他不符合Node應該具備的條件。

所以考慮其他的Node(橘色部分),得到新的綠色Node之後的步驟皆以此類推,最後得到的圖如下👇主要是從老師上課內容,再自行做成筆記。

希望這篇也能幫助到有疑問的各位,如果有任何錯誤的部分,還請各位多多指教。

我們下次再見~~👋👋SharonPeng一起精進程式能力吧!!Follow77 7BranchAndBoundBacktrackingAlgorithmsMorefromSharonPengFollow一起精進程式能力吧!!



請為這篇文章評分?