計算機算法設計與分析——回溯法

回溯法的算法架構

1.非遞歸回溯架構

int x[n];//x存放解向量，全局變量
void backtrack(int n)//非遞歸架構
{
	int i = 1;//根結點層次為1
	while (i >= 1)//尚未回溯到頭
	{
		if (ExistSubNode(t))//目前結點存在子結點
		{
			for (j = 下界; j <= 上界; j++)//對于子集樹，j=0到1循環
			{
				x[i]取一個可能的值;
				if (constraint(i) && bound(i))//x[i]滿足限制條件或界限函數
				{
					if (x是一個可行解）
						輸出x;
					else i++;//進入下一層次
				}
			}
		}
		else i--;//回溯：不存在子結點，傳回上一層
	}
}
           

2.遞歸的算法架構

（1）解空間為子集樹

int x[n];//x存放解向量，全局變量
void backtrack(int i)//求解子集樹的遞歸架構
{
	if (i > n)//搜尋到葉子結點，輸出一個可行解
		輸出結果;
	else
	{
		for (j = 下界; j <= 上界; j++)//用j枚舉i所有可能的路徑
		{
			x[i] = j;//産生一個可能的解分量
			-//其他操作
				if (constrint(i) && bound(i))
					backtrack(i + 1);//滿足限制條件和限界函數，繼續下一層
		}
	}
}
           

（2）解空間為排列數

int x[n];//x存放解向量，并初始化
void backtrack(int i)//求解排列樹的遞歸架構
{
	if (i > n)//搜尋到葉子結點，輸出一個可行解
		輸出結果;
	else
	{
		for (j = i; j <= n; j++)//用j枚舉i所有可能的路徑
		{	...//第i層的結點選擇x[j]的操作
			swap(x[i],x[j];//為保證排列中每個元素不同，通過交換來實作
			if (constrint(i) && bound(i))
					backtrack(i + 1);//滿足限制條件和限界函數，繼續下一層
			swap(x[i], x[j]);//恢複狀态
			...//第i層的結點選擇x[j]的恢複操作
		}
	}
}