計算機算法設(shè)計與分析第6章回溯法6.2.1解空間樹一個復(fù)雜問題的解決方案是由若干個小的決策步驟組成的決策序列，解決一個問題的所有可能的決策序列構(gòu)成該問題的解空間。應(yīng)用回溯法求解問題時，首先應(yīng)該明確問題的解空間。解空間中滿足約束條件的決策序列稱為可行解。問題的解由一個不等長或等長的解向量X={x1,x2,…,xn}組成，其中分量xi表示第i步的操作。所有滿足約束條件的解向量組構(gòu)成了問題的解向量空間。如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）}。解向量的樹結(jié)構(gòu)表示形式101010101010013個物品的0-1背包問題：x1=1或0x2=1或0x3=1或06.2.1解空間樹在回溯算法中，通常使用深度優(yōu)先搜索方式遍歷解空間樹。在搜索過程中，通過剪枝操作來減少搜索的路徑數(shù)量，提高算法的效率?；厮菟惴ǖ年P(guān)鍵是在搜索過程中正確地進行狀態(tài)更新和回溯操作。當搜索到某個結(jié)點時，如果發(fā)現(xiàn)當前結(jié)點不滿足問題的約束條件，就會進行回溯操作，返回到上一層結(jié)點，繼續(xù)搜索其他可能的解。通過遍歷解空間樹，回溯算法可以找到問題的所有解，或者找到滿足特定條件的解。（1）子集樹當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。例如3個物品的0-1背包問題，可以用一棵完全二叉樹表示其解空間。10101010101001x1=1或0x2=1或0x3=1或0（2）排列樹當所給的問題是確定n個元素滿足某種性質(zhì)排列時，相應(yīng)的解空間樹稱為排列樹。例如4個城市的旅行商問題，該旅行商問題的帶權(quán)圖和解空間排列樹。1065912814323423244232431243x1

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