//非递归迭代过程
void iterativeBacktrack(){
int t = 1;
while(t > 0){
if(f(n,t) <= g(n,t))
for(int i = f(n,t);i <= g(n,t);i++){
x[t] = h(i);
if(constraint(t) && bound(t)){
//solution(t)判断在当前扩展节点处是否已得到问题的可行解
//返回true,在当前扩展结点处x[1:t]是问题的可行解.
if(solution(t))
output(x);
else{
//在当前扩展结点处x[1:t]只是问题的部分解,还需向纵深方向继续搜索
t++;
}
}
}
else{
//当前扩展节点的子树都已经搜索过,返回上一层.
t--;
}
}
//while执行完之后,完成整个回溯搜索过程.
}
//子集树
void backtrack(int t){
if(t > n)
output(x);
else
for(int i = 0;i <= 1;i++){
x[t] = i;
if(constraint(t) && bound(t))
backtrack(t + 1);
}
}
//排列树
//在调用backtrack(1)执行回溯搜索之前,先将变量数组x初始化为单位排列(1,2,3,..,n)
void backtrack(int t){
if(t > n)
output(x);
else
for(int i = t;i <= n;i++){
swap(x[t],x[i]);
if(constraint(t) && bound(t))
backtrack(t + 1);
swap(x[t],x[i]);
}
}