1.1 解空間
有 n 個部件
每個部件可從 m 個供應商購買
每個供應商提供的部件有重量和成本
要在總成本不超過預算 C 的條件下使總重量最小

解是一個長度為 n 的序列 x1 x2 ... xn
每個 xi 取值 1 到 m 表示第 i 個部件選擇的供應商編號
所有可能解構成解空間 大小為 m 的 n 次方

1.2 解空間樹
這是一棵 m 叉樹
樹根在第 0 層表示尚未選擇任何部件
第 i 層結點表示已經為前 i 個部件選好了供應商
每個結點有 m 個孩子分別對應為下一個部件選擇不同供應商
葉子在第 n 層代表一個完整選擇方案
整棵樹有 mⁿ 個葉子對應所有可能解

1.3 遍歷時結點狀態值
每個結點維護以下狀態
當前已選部件的總重量
當前已選部件的總成本
當前路徑記錄每個部件已選的供應商編號
當前正在決策的部件下標

2 對回溯算法的理解
回溯法是深度優先搜索加剪枝
用於求解組合優化問題
它系統地遍歷解空間樹
每次擴展一個分支
如果發現當前部分解已經不可能達到最優或違反約束
就剪掉這個分支返回上層
繼續嘗試其他選擇
這樣可以避免搜索整個解空間
但最壞情況仍然是指數時間複雜度
關鍵在於設計有效的剪枝條件
提前排除無效分支