資源簡介

(共21張PPT)
第13課
算法的設計
01
02
03
04
分支限界算法基本思想
常見的兩種分支限界算法
分支限界法與回溯法的不同
分支限界算法解空間樹的動態搜索
CONTENTS
目錄
分支限界算法應用
05
06
分支限界算法的設計思路
分支限界算法基本思想
01
Part One
【分支限界算法】
基本思想1 ：
分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有子結點。
【分支限界法】
基本思想2 ：
在這些子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余子結點被加入活結點表中。 此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止。
常見的兩種分支限界算法
02
常見的兩種分支限界算法：
01
隊列式(FIFO)分支限界法
按照隊列先進先（FIFO）原則選取下一個節點為擴展節點。
02
優先隊列式分支限界法
按照優先隊列中規定的優先級選取優先級最高的節點成為當前擴展節點。
分支限界法與回溯法的不同:
03
（1）求解目標：
回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解。
（2）搜索方式的不同：
回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹。
分支限界法與回溯法的不同:
分支限界算法解空間樹的動態搜索
04
解空間樹的動態搜索
（1）回溯求解0/1背包問題，雖剪枝減少了搜索空間，但整個搜索按深度優先機械進行，是盲目搜索（不可預測本結點以下的結點進行的如何）。
（2）回溯求解TSP也是盲目的（雖有目標函數，也只有找到一個可行解后才有意義）。
（3）分支限界法首先確定一個合理的限界函數，并根據限界函數確定目標函數的界[down, up]；然后按照廣度優先策略遍歷問題的解空間樹，在某一分支上，依次搜索該結點的所有孩子結點，分別估算這些孩子結點的目標函數的可能取值（對最小化問題，估算結點的down，對最大化問題，估算結點的up）。如果某孩子結點的目標函數值超出目標函數的界，則將其丟棄（從此結點生成的解不會比目前已得的更好），否則入待處理表。
分支限界算法的設計思路
05
分支限界法的設計思路
設求解最大化問題，解向量為X=(x1,…,xn)，xi的取值范圍為Si，|Si|=ri。在使用分支限界搜索問題的解空間樹時，先根據限界函數估算目標函數的界[down, up]，然后從根結點出發，擴展根結點的r1個孩子結點，從而構成分量x1的r1種可能的取值方式。
對這r1個孩子結點分別估算可能的目標函數bound(x1)，其含義：以該結點為根的子樹所有可能的取值不大于bound(x1)，即：\nbound(x1)≥bound(x1,x2)≥…≥ bound(x1,…,xn)若某孩子結點的目標函數值超出目標函數的下界，則將該孩子結點丟棄；否則，將該孩子結點保存在待處理結點表PT中。再取PT表中目標函數極大值結點作為擴展的根結點，重復上述。直到一個葉子結點時的可行解X=(x1,…,xn)，及目標函數值bound(x1,…,xn)。
分支限界算法應用
06
分支限界算法應用：
分支限界法之裝載問題
01
分支限界法之布線問題
02
分支限界法之0 1背包問題
03
分支限界法之旅行售貨員問題
04
練習1
針對機器人畫正六邊形的問題,設計一個算法。
練習2
練習3
感謝聆聽

展開更多......

收起↑