迭代法执行回溯.cpp

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

/*
回溯法解题的一个显著特征是问题的解空间是在搜索过程中动态产生的
在任何时刻，算法只保存从根结点到当前扩展结点的路径
*/
void IterativeBacktrack(void)
{
	int t = l;
	while(t>0)
	{
		if(f(n,t)<=g(n,t))
		//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))
				{
					if(Solution(t))
					{
						Output(x);
					}
					else
					{
						t++;
					}
				}
				else
				{
					t--;
				}
			}
		}
	}
}