簡介
解空間如果ξ1,ξ2,...ξs是一般齊次線性方程組的s個解,則它們的任一線性組合c1ξ1+c2ξ2+...+csξs 也是該齊次線性方程組的解向量.由此可知若齊次線性方程組有非零解,則其解有無窮多個,而齊次線性方程組所有解的集合構成一個向量空間,這個向量空間就稱為解空間.
解題步驟
1.針對所給問題，定義問題的解空間；2.確定易於搜尋的解空間結構；
3.以深度優先方式搜尋解空間，並在搜尋過程中用剪枝函式避免無效搜尋。
對於問題的解空間結構通常以樹或圖的形式表示，常用的兩類典型的解空間樹是子集樹和排列樹。當所給的問題是從n個元素的集合S中找到S滿足某種性質的子集時，相應的解空間樹稱為子集樹。例如，n個物品的0-1背包問題所對應的解空間樹是一棵子集樹，這類子集樹通常有2**n個葉結點，遍歷子集樹的算法需要O(2**n)計算時間。當所給問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n！個葉結點。因此，排列樹需要O(n!)計算時間。當問題的解空間確定後，便可用不同的剪枝函式和最優解表示方法來獲得最終結果。
