算法設計與分析 課件 第七章 分支限界 7.2.1 分支限界方式_第1頁
算法設計與分析 課件 第七章 分支限界 7.2.1 分支限界方式_第2頁
算法設計與分析 課件 第七章 分支限界 7.2.1 分支限界方式_第3頁
算法設計與分析 課件 第七章 分支限界 7.2.1 分支限界方式_第4頁
算法設計與分析 課件 第七章 分支限界 7.2.1 分支限界方式_第5頁
已閱讀5頁，還剩2頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

計算機算法設計與分析第7章分支限界法7.2.1分支限界方式分支限界法根據從活結點表中選擇下一個擴展結點的方式，可分為隊列式分支限界和優先隊列式分支限界。（1）隊列式分支限界法隊列式（FIFO）式分支限界法的基本思想：（1）首先將初始狀態節點放入活結點隊列中。（2）若隊列非空，則重復下列步驟：①出隊，將出隊結點作為當前擴展結點。②判斷當前擴展結點是否為目標結點，若是目標結點，則搜索到一個可行解而結束。③對當前擴展結點進行擴展。在擴展節點時，一次性產生它的所有子結點，并利用剪枝函數檢測，把滿足約束和限界條件的的子結點依次加入活結點隊列。（3）重復（2），直到隊列為空，則搜索失敗結束。（2）優先隊列式分支限界法將活結點表組成一個優先隊列，按照優先隊列中指定的結點優先級，選取優先級最高的結點作為當前擴展結點，以優先隊列儲存活結點。結點的優先級常用一個與該結點相關的限界函數值來表示。也稱為最小耗費優先分支限界法(LC)該策略與隊列式分支限界法的主要區別是：優先隊列式分支限界法的活結點表組成一個優先隊列，每個活結點入隊時會計算其優先級，優先級最高的活結點位于隊首位置。（2）優先隊列式分支限界法優先隊列通常采用堆數據結構來組織，通過維護堆屬性，可以保證優先隊列的入隊操作時按結點元素優先級重新排序，也即隊列中優先級最高的結點元素始終位于隊列首部位置。每次出隊的隊首結點總是當前隊列中具有優先級最高（最有利）的結點成為當前擴展結點，使搜索朝著解空間樹有最優解的分支方向快速推進，以便快速找到問題的最優解。優先隊列式分支限界法基本思想（1）確定合理的限界函數，并根據限界函數確定問題的目標函數的上（下）界，又稱耗費函數值或代價值。（2）初始化一個空的優先隊列H，并將初始狀態加入隊列。初始化一個變量best_score用于保存當前找到的最優解（初值=無窮大）。（3）當隊列H不為空時，執行以下步驟：優先隊列式分支限界法基本思想

①出隊結點保存為node。

②ifnode結點對應更優的解then更新當前最優解best_score的值。③fornode的每一個子結點child：a.計算child結點的目標函數限界值。b.ifchild滿足解的約束條件且耗費函數值不超過

目標函數的當前限界thenc.將child加入

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論