子集樹

子集樹是一個數學學科辭彙，屬於函式類，當所給問題是從n個元素的集合S中找出S滿足某種性質的子集時，相應的解空間稱為子集樹。

基本介紹

• 中文名：子集樹
• 定義：一個數學學科辭彙
• 屬於：函式類
• 定義：當所給問題是從n個元素的集合S中

內容介紹

當所給問題是從n個元素的集合S中找出S滿足某種性質的子集時，相應的解空間稱為子集樹。例如：n個物品的0-1背包問題所相應的解空間是一棵子集樹，這類子集樹通常有2^n個葉結點，其結點總數為(2^(n+1))-1。遍歷子集樹的算法通常需O(2^n)計算時間。

元素區別

當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹。
當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉節點。

套用

子集樹一個重要的例子就是0-1背包問題。

例如當n=3時的0-1背包問題，考慮下面的具體實例：w=[16,15,15],p=[45,25,25],c=30。從圖中的根節點開始搜尋其解空間。

遍歷子集樹需O(2n)計算時間

void backtrack (int t)

{

if (t>n) output(x);

else

for (int i=0;i<=1;i++) {

x[t]=i;

if (legal(t)) backtrack(t+1);

}

}