解空間

解空間也就是一個集合。

如果是一般齊次線性方程組的s個解，則它們的任一線性組合 也是該齊次線性方程組的解向量。由此可知若齊次線性方程組有非零解，則其解有無窮多個，而齊次線性方程組所有解的集合構成一個向量空間，這個向量空間就稱為解空間.

解題步驟1. 針對所給問題，定義問題的解空間；2. 確定易於搜索的解空間結構；3. 以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。例如，n個物品的背包問題所對應的解空間樹是一棵子集樹，這類子集樹通常有個葉結點，遍歷子集樹的演演算法需要計算時間。當所給問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n！個葉結點。因此，排列樹需要計算時間。當問題的解空間確定后，便可用不同的剪枝函數和最優解表示方法來獲得最終結果。