算法設計與分析 課件 第六章 回溯法6.2.1 解空間樹

計算機算法設計與分析第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ù)量，提高算法的效率?；厮菟惴ǖ年P鍵是在搜索過程中正確地進行狀態(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）擴展結點:一個正在產(chǎn)生子結點的結點稱為擴展結點。（2）活結點:一個自身已生成但其子結點還沒有全部生成的結點稱為活結點。（3）死結點:一個所有子結點已經(jīng)產(chǎn)生的結點稱做死結點?；厮輘1sisi+1找其他路徑當從結點si搜索到結點si+1后，如果si+1變?yōu)樗澜Y點，則從結點si+1回退到si，再從si找其他可能的路徑，所以回溯法體現(xiàn)出走不通就退回上一步選擇其他路徑再走的思路。6.2.1解空間樹若用回溯法求問題的所有解時，需要回溯到根結點，且根結點的所有可行的子樹都要已被搜索完才結束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。以深度優(yōu)先方式搜索整個解向量空間樹效率比較低，通常以下