為定義搜索范圍，應明確以下幾個方面： 1. 問題解的形式：表示成一個n元組的形式`(x[0],x[1],...,x[n-1])` 2. 顯約束：對分量`x[i]`的取值范圍限定。 3. 隱約束：為滿足問題的解而對不同分量之間施加的約束。 4. 解空間：對于問題的一個實例，解向量滿足顯約束的所有n元組構成了該實例的一個解空間。 ---- 在搜索的過程中，應了解幾個名詞： 1. 擴展結點：一個正在生成孩子的結點。 2. 活結點：一個自身已生成但其孩子還沒有全部生成的結點。 3. 死結點：一個所有孩子已生成的結點。 ---- 求解過程： 1. 定義問題的解空間。 2. 確定空間的組織結構。 3. 搜索解空間： - 確定約束條件 - 確定限界條件 - 搜索過程 ---- 算法描述： > (1)遞歸形式 ```c++ // t為擴展節點在樹中所處的層次 void Backtrack(int t){ if(t > n){ //搜索層次大于解空間的樹的深度，說明找到了葉子結點，即找到了問題的一個解 output(x); } else { for (int i = s(n, t); i <= e(n, t); i++){ x[t] = d(i); if(constraint(t) && bound(t)){ Backtrack(t + 1); } } } } ``` > (2)非遞歸形式 ```c++ void NBacktrack(){ int t = 1; while(t > 0){ if(s(n,t) <= e(n, t)){ for(int i = s(n, t); i <= e(n,t); i++){ x[t] = d(i); if(constraint(t) && bound(t)){ if(t > n){ output(x); } else { t++; } } } } else { t--; } } } ```