算法設計與分析 課件 第六章 回溯法6.2.1 解空間樹_第1頁
算法設計與分析 課件 第六章 回溯法6.2.1 解空間樹_第2頁
算法設計與分析 課件 第六章 回溯法6.2.1 解空間樹_第3頁
算法設計與分析 課件 第六章 回溯法6.2.1 解空間樹_第4頁
算法設計與分析 課件 第六章 回溯法6.2.1 解空間樹_第5頁
已閱讀5頁，還剩3頁未讀， 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

計算機算法設計與分析第6章回溯法6.2.1解空間樹一個復雜問題的解決方案是由若干個小的決策步驟組成的決策序列，解決一個問題的所有可能的決策序列構成該問題的解空間。應用回溯法求解問題時，首先應該明確問題的解空間。解空間中滿足約束條件的決策序列稱為可行解。問題的解由一個不等長或等長的解向量X={x1,x2,…,xn}組成，其中分量xi表示第i步的操作。所有滿足約束條件的解向量組構成了問題的解向量空間。如3個物品的0-1背包問題，其解向量空間為：{（0,0,0），（0,0,1），（0,1,0），（0,1,1），

（1,0,0），（1,0,1），（1,1,0），（1,1,1）}。解向量的樹結構表示形式101010101010013個物品的0-1背包問題：x1=1或0x2=1或0x3=1或06.2.1解空間樹在回溯算法中，通常使用深度優(yōu)先搜索方式遍歷解空間樹。在搜索過程中，通過剪枝操作來減少搜索的路徑數(shù)量，提高算法的效率。回溯算法的關鍵是在搜索過程中正確地進行狀態(tài)更新和回溯操作。當搜索到某個結點時，如果發(fā)現(xiàn)當前結點不滿足問題的約束條件，就會進行回溯操作，返回到上一層結點，繼續(xù)搜索其他可能的解。通過遍歷解空間樹，回溯算法可以找到問題的所有解，或者找到滿足特定條件的解。（1）子集樹當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。例如3個物品的0-1背包問題，可以用一棵完全二叉樹表示其解空間。10101010101001x1=1或0x2=1或0x3=1或0（2）排列樹當所給的問題是確定n個元素滿足某種性質排列時，相應的解空間樹稱為排列樹。例如4個城市的旅行商問題，該旅行商問題的帶權圖和解空間排列樹。1065912814323423244232431243x1

起點x2有三個選擇x3有二個選擇x4有一個選擇6.2.1解空間樹定義解空間樹中幾個相關結點概念：（1）擴展結點:一個正在產生子結點的結點稱為擴展結點。（2）活結點:一個自身已生成但其子結點還沒有全部生成的結點稱為活結點。（3）死結點:一個所有子結點已經產生的結點稱做死結點。回溯s1sisi+1找其他路徑當從結點si搜索到結點si+1后，如果si+1變?yōu)樗澜Y點，則從結點si+1回退到si，再從si找其他可能的路徑，所以回溯法體現(xiàn)出走不通就退回上一步選擇其他路徑再走的思路。6.2.1解空間樹若用回溯法求問題的所有解時，需要回溯到根結點，且根結點的所有可行的子樹都要已被搜索完才結束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。以深度優(yōu)先方式搜索整個解向量空間樹效率比較低，通常以下

溫馨提示

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

評論

0/150

提交評論