为定义搜索范围，应明确以下几个方面： 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--; } } } ```