一、知識(shí)鋪墊

• 約束條件
  分為顯式約束和隱式約束
  顯式：規(guī)定了問題的解的分量的取值范圍。如求n的全排列每個(gè)位置只能取1~n
  隱式：用于判定候選解是否為可行解。如全排列的每個(gè)數(shù)字不允許重復(fù)。
• 問題狀態(tài)和狀態(tài)空間樹
  ????????狀態(tài)空間樹是描述問題解空間的樹形結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)稱為一個(gè)問題狀態(tài)。樹的每條分支代表一次決策，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑就代表了一個(gè)候選解，稱該葉結(jié)點(diǎn)所代表的狀態(tài)為解狀態(tài)。如果候選解是可行解則稱之為答案狀態(tài)。
• 剪枝函數(shù)
  ????剪枝函數(shù)分為約束函數(shù)和限界函數(shù)
  ????約束函數(shù)：避免無所謂的搜索那些已知不含答案狀態(tài)的子樹。
  ????限界函數(shù)：用于最優(yōu)化問題，剪去那些不可能含有最優(yōu)答案結(jié)點(diǎn)的子樹。
  ????二者的區(qū)別在于：約束函數(shù)是對約束條件的實(shí)現(xiàn)，剪去不帶答案結(jié)點(diǎn)的子樹。而限界函數(shù)常用于求解最優(yōu)化問題，它剪去的子樹可能帶答案結(jié)點(diǎn)，但不會(huì)是最優(yōu)答案結(jié)點(diǎn)。

二、什么是回溯法

回溯法是一種更為一般的解題方法?；厮莘ㄊ峭ㄟ^搜索狀態(tài)空間樹來求問題的可行解或最優(yōu)解的方法。本質(zhì)就是dfs + 剪枝。

三、回溯法的使用場景

如果問題的解可表示成一個(gè)n元組$(x_1,x_2,...,x_n)$，我們就可以通過枚舉所有的可能排列來搜索答案。比如求全排列、迷宮問題、n皇后、子集和數(shù)、圖的著色問題等。文章來源地址http://www.zghlxwxcb.cn/news/detail-479232.html

四、回溯法的解題步驟

void BackTrack(int k){
	if k == n { 輸出答案 }
	else{
			for 所有可能的x[k]取值
				if x[k] 滿足約束條件
					BackTrack(k+1)
	}
}

五、典例

• n皇后問題

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 15;
int g[N], ans[N];
int n;
LL cnt;
bool vis[N];
bool check(int k, int j){
	for(int i = 1; i < k; i ++){
		if(ans[i] == j || abs(i - k) == abs(ans[i] - j))
			return false; 
	}
	return true;
}
void nQueens(int d){
	if(d == n + 1){
		for(int i = 1; i <= n; i ++) 
			cout << ans[i] << ' ';
		cout << endl; 
		cnt ++;
		return; 
	}
	for(int i = 1; i <= n; i ++){	// 顯式約束
		if(!vis[i] && check(d,i)){	// 隱式約束
			ans[d] = i;
			vis[i] = 1;
			nQueens(d + 1);
			vis[i] = 0;
		} 
	}
}
int main(){
	cin >> n;
	nQueens(1);
	cout << cnt;
	return 0;
}

• 子集和數(shù)問題

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[N], x[N], tmp[N];
int idx[100*N];
int n, m;
bool f;
void dfs(int s, int k, int r){
	x[k] = 1;
	if(s + w[k] == m){
		for(int i = k + 1; i < n; i ++)
			x[i] = 0;
		for(int i = 0; i < n; i ++)
			cout << x[idx[tmp[i]]] << ' ';
		cout << endl;
		f = 1;
	}
	else if(s + w[k] + w[k + 1] <= m){	//選 k可以 
			dfs(s + w[k], k + 1, r - w[k]);
	}
	if(s + r - w[k] >= m && s + w[k+1] <= m){	//不選 k 
		x[k] = 0;
		dfs(s, k + 1, r - w[k]);
	}
}
int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i ++)
		cin >> w[i], tmp[i] = w[i];	// tmp copy w for print 
	int r = 0, s = 0;
	for(int i = 0; i < n; i ++)
		r += w[i];
	sort(w, w + n);
	for(int i = 0; i < n; i ++)
		idx[w[i]] = i;
	if(r >= m && w[0] <= m)
		dfs(s,0,r);
	if(!f) cout << "no solution!" << endl;
	return 0;
}

到了這里，關(guān)于【算法分析與設(shè)計(jì)】第八章-回溯法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！