子集樹與排列樹

1.當所給問題是從n個元素的集合S中找出S滿足某種性質的子集時，相應的解空間稱為子集樹。

例如：n個物品的0-1背包問題所相應的解空間是一棵子集樹，這類子集樹通常有2^n個葉結點，其結點總數為(2^(n+1))-1。

周遊子集樹的算法通常需要(2^n)計算時間。

回溯法搜尋子集樹的算法一般可以描述如下：

2.當所給問題的确定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。

排列樹通常有n!個葉結點，是以周遊排列樹需要奧秘加(n!)計算時間。

例如：全排列、貨郎擔問題...

回溯法搜尋排列樹的算法一般可以描述如下：