递归法执行回溯.cpp

来自「算法分析中」· C++ 代码 · 共 27 行

void Backtrack(int t)
//t表示递归深度
{
	if(t>n)
	//n用来控制递归深度，即解空间树的高度
	//t>n表示已经搜索到一个叶结点。此时由函数Output(x)
	//对得到的可行解x进行记录或输出处理。
	{
		Output(x);
	}
	else
	{
		for(int i=f(n,t);i<=g(n,t);i++)
		/*
		f(n,t),g(n,t)分别表示在当前扩展结点处未搜索过的子树的其始编号和终止编号
		h(i)表示在当前扩展结点处x[t]的第i个可选值
		函数Constraint(t)和Bound(t)表示在当前扩展结点处的约束函数和限界函数
		*/
		{
			x[t]=h(i);
			if(Constraint(t)&&Bound(t))
			{
				Backtrack(t+1);
			}
		}
	}
}