回溯1

實(shí)驗(yàn)題目：n皇后

題目描述：

N皇后的排列，每行一個(gè)不沖突；N<=13。

輸入要求：

一個(gè)數(shù)字N (6 <= N <= 13) 表示棋盤(pán)是N x N大小的

輸出要求：

前三行為前三個(gè)解，每個(gè)解的兩個(gè)數(shù)字之間用一個(gè)空格隔開(kāi)。第四行只有一個(gè)數(shù)字，表示解的總數(shù)。

解的輸出順序?yàn)閺纳系较聫淖蟮接遥〉膬?yōu)先輸出

實(shí)驗(yàn)代碼及注釋:

#include<bits/stdc++.h>
using namespace std;

int q[15] = { 0 }; //記錄n個(gè)皇后的擺放位置
// 下標(biāo)為行，數(shù)組元素為列
int sum = 0;
int n;

void queen(int i)
{
	int j;
	int col, flag; 

	if (i == n + 1)//所有的行全部走完，即成功找到一種解法
	{
		sum++;
		if (sum <= 3) // 輸出前三行結(jié)果
		{
			for (j = 1;j <= n;j++)
			{
				if (j == n)
					cout << q[j] << endl;
				else
					cout << q[j] << " ";
			}
		}
		return;
	}
	else
	{
		for (col = 1;col <= n;col++)//遍歷i行的每一列
		{
			flag = 1; // 假定棋子可放在i行col列
			for (j = 1;j < i;j++)//n遍歷前i行是否符合
			{
				if (col == q[j] || i - col == j - q[j] || i + col == j + q[j])
				{
					flag = 0; //與前面棋子發(fā)生沖突
					break;
				}
			}
			if (flag == 1)//未與前面棋子發(fā)生沖突
			{
				q[i] = col;
				queen(i + 1);//遍歷下一行
			}
		}
	}
}
int main(void)
{
	cin >> n;
	memset(q, -1, sizeof(q)); //初始化棋子，-1表示未放上棋盤(pán)
	queen(1); //從第一行開(kāi)始遍歷
	cout << sum << endl;
	return 0;
}

算法分析與知識(shí)點(diǎn)：

本題采用回溯算法思想來(lái)解決N皇后問(wèn)題，這里用一個(gè)q[N]數(shù)組來(lái)記錄棋子擺放情況：

1.算法開(kāi)始, 清空棋盤(pán)，當(dāng)前行設(shè)為第一行，當(dāng)前列設(shè)為第一列

2.在當(dāng)前行，當(dāng)前列的位置上判斷是否滿(mǎn)足條件(即保證經(jīng)過(guò)這一點(diǎn)的行,列與斜線(xiàn)上都沒(méi)有兩個(gè)皇后)，若不滿(mǎn)足，跳到第4步

3.在當(dāng)前位置上滿(mǎn)足條件的情形：

• 在當(dāng)前位置放一個(gè)皇后，若當(dāng)前行是最后一行，記錄一個(gè)解；
• 若當(dāng)前行不是最后一行，當(dāng)前行設(shè)為下一行, 當(dāng)前列設(shè)為當(dāng)前行的第一個(gè)待測(cè)位置；
• 若當(dāng)前行是最后一行，當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列；
• 若當(dāng)前行是最后一行，當(dāng)前列是最后一列，回溯，即清空當(dāng)前行及以下各行的棋盤(pán)，然后，當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個(gè)待測(cè)位置；
• 以上返回到第2步

4.在當(dāng)前位置上不滿(mǎn)足條件的情形：

若當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列，返回到第2步；

若當(dāng)前列是最后一列了，回溯，即，若當(dāng)前行已經(jīng)是第一行了，算法退出，否則，清空當(dāng)前行及以下各行的棋盤(pán)，然后，當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的

下一個(gè)待測(cè)位置，返回到第2步;

實(shí)驗(yàn)題目：符號(hào)三角形

題目描述：

符號(hào)三角形的 第1行有n個(gè)由“+”和“-”組成的符號(hào) ，以后每行符號(hào)比上行少1個(gè)，2個(gè)同號(hào)下面是“+”，2個(gè)異號(hào)下面是“-” 。計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含“+” 和“-” 的個(gè)數(shù)相同。

輸入要求：

整數(shù)n(n<=20)。

輸出要求：

符合要求的符號(hào)三角形的個(gè)數(shù)。

實(shí)驗(yàn)代碼及注釋:

#include<bits/stdc++.h> 
using namespace std;
int a[30][30] = { 0 };
int n, sum = 0, sum1 = 0;


void check() {
	int t = n, sum2 = 0;
	while (t--) {
		for (int i = 1;i <= t;i++) {
			a[t][i] = 1 - (a[t + 1][i] + a[t + 1][i + 1]) % 2;  // 遞推第t層i列的符號(hào)
			if (a[t][i])//若為＋
				sum2++;
		}
	}
	if (2 * (sum1 + sum2) == (n * (n + 1) / 2)) //記錄+總數(shù)是否為符號(hào)總數(shù)的一半
		sum++;
}
void dfs(int x) {  // x表示考慮頂層第x個(gè)位置的符號(hào)
	for (int i = 0;i < 2;i++) {
		//0=>-;1=>+
		if (i)
			sum1++; // 記錄頂層+的數(shù)量
		a[n][x] = i;
		if (x == n)//考慮完頂層的一種符號(hào)擺放，進(jìn)行檢查
			check();
		else
			dfs(x + 1);
		if (i)
			sum1--; // 若上擺放為+，則+數(shù)量回退1
	}
}
int main()
{
	cin >> n;
	if ((n * (n + 1) / 2) % 2 == 1) //判斷符號(hào)總數(shù)奇偶性
		cout << 0 << endl;
	else {
		dfs(1);
		cout << sum << endl;
	}
	return 0;
}

算法分析與知識(shí)點(diǎn)：

本題主要運(yùn)用回溯的思想，這題的特點(diǎn)是不能輸入元素，而且只要確定的頂層的n的符號(hào)的排列情況，就可以得到整個(gè)符號(hào)三角形的排列情況，因此只需要對(duì)符號(hào)三角形的頂層進(jìn)行遍歷就好了。題目中有要求+和-的數(shù)量要一樣，所以符號(hào)三角形的符號(hào)總數(shù)要是偶數(shù)，否則解決方案數(shù)為0。

令0和1分別代表-和+，其他層在頂層確定后即確定了，不需要枚舉。采用dfs對(duì)第一層的符號(hào)排列情況進(jìn)行遍歷，遍歷完n后就可得到答案。

回溯 堂練

實(shí)驗(yàn)題目：森林迷宮

題目描述：

一天Luna在森林里探險(xiǎn)的時(shí)候不小心走入了一個(gè)迷宮，迷宮可以看成是由n * n的格點(diǎn)組成，每個(gè)格點(diǎn)只有2種狀態(tài)：^ 和 # ；前者表示可以通行后者表示不能通行。當(dāng)Luna處在某個(gè)格點(diǎn)時(shí)，她只能移動(dòng)到東南西北(或者說(shuō)上下左右)四個(gè)方向之一的相鄰格點(diǎn)上，Luna想要從起點(diǎn)A走到終點(diǎn)B（中途不能走出迷宮）。如果起點(diǎn)或者終點(diǎn)有一個(gè)不能通行(為#)，則當(dāng)做無(wú)法通行。

輸入要求：

第1行是測(cè)試數(shù)據(jù)的組數(shù)k，后面跟著k組輸入。

每組測(cè)試數(shù)據(jù)的第1行是一個(gè)正整數(shù)n (1 <= n <= 100)，表示迷宮的規(guī)模是n * n的。

接下來(lái)是一個(gè)n * n的矩陣，矩陣中的元素為 . 或者 #。

再接下來(lái)一行是4個(gè)整數(shù)ar,ac,br,bc。表示A處在第ar行，第ac列，B處在第br行, 第bc列。注意坐標(biāo)ar，ac，br，bc全部是從0開(kāi)始計(jì)數(shù)的類(lèi)似[1,4][5,6]被認(rèn)為是覆蓋了[1,6]。

輸出要求：

YES或NO

實(shí)驗(yàn)代碼及注釋:

#include<bits/stdc++.h> 
using namespace std;
char s[105][105]; // 記錄地圖
int n, ha, la, hb, lb, dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} }, flag;//flag標(biāo)記搜索完畢后是否能到達(dá)終點(diǎn)
void dfs(int ha, int la)
{
	if (ha == hb && la == lb) // 判斷是否達(dá)到終點(diǎn)
	{
		flag = 1;
	}
	if (flag) {
		cout << "YES" << endl;
		return;
	}
	for (int i = 0;i < 4;i++)
	{
		int dx = ha + dir[i][0];
		int dy = la + dir[i][1];
		if (dx >= 0 && dx < n && dy >= 0 && dy < n && s[dx][dy] == '^')
		{
			s[dx][dy] = '#';//只走一次，每個(gè)方都要走一遍，只要連通，肯定能到終點(diǎn)
			dfs(dx, dy);
		}
	}
}
int main()
{
	int k;
	cin >> k;
	while (k--)
	{
		cin >> n;
		for (int i = 0;i < n;i++) for (int j = 0;j < n;j++) cin >> s[i][j];
		cin >> ha >> la >> hb >> lb;
		if (s[ha][la] == '#' || s[hb][lb] == '#') cout << "NO" << endl;//提前判斷始點(diǎn)和終點(diǎn)是否符合要求
		else
		{
			flag = 0;
			dfs(ha, la); //dfs搜索路徑
			if (flag == 0) cout << "NO" << endl;
		}
		
	}
	return 0;
}

算法分析與知識(shí)點(diǎn)：

本采用深度優(yōu)先的搜索方式來(lái)搜索全部路徑，大致思路為：從當(dāng)前點(diǎn)出發(fā)，往四個(gè)方位探尋找出所有與之相鄰的且尚未被訪(fǎng)問(wèn)過(guò)的點(diǎn)，從中暫時(shí)先選取一個(gè)點(diǎn)作為當(dāng)前點(diǎn)繼續(xù)上述過(guò)程，直到到達(dá)目的地或者再也無(wú)法探尋到能前進(jìn)的點(diǎn)，再返回。如果當(dāng)前搜索的點(diǎn)到達(dá)了目標(biāo)點(diǎn)，flag標(biāo)記為true，返回即可。若所有能到達(dá)的點(diǎn)都搜索完了，flag仍為false，則無(wú)法到達(dá)。

實(shí)驗(yàn)題目：地圖著色

題目描述：

給定圖G=(V, E)，需要為圖G的各頂點(diǎn)著色，是否有一種著色法使G中相鄰的兩個(gè)頂點(diǎn)有不同的顏色?

輸入要求：

第一行是頂點(diǎn)的個(gè)數(shù)n（2≤n≤10），顏色數(shù)m（1≤m≤n）。

接下來(lái)是頂點(diǎn)之間的連接關(guān)系：a b；表示a和b相鄰。頂點(diǎn)從1開(kāi)始計(jì)。

當(dāng)a，b同時(shí)為0時(shí)表示輸入結(jié)束。

輸出要求：

輸出著色方案總數(shù)和最少顏色數(shù)。如果無(wú)可行方案，顏色數(shù)為0。

實(shí)驗(yàn)代碼及注釋:

#include<bits/stdc++.h> 
using namespace std;
#define N 10
int n, sum = 0, m;
int x[N + 1]; //記錄可行解
int g[N + 1][N + 1];//鄰接矩陣
int ans = N;
int ok(int t)  // 判斷當(dāng)前層節(jié)點(diǎn)是否可行
{
    for (int j = 1; j <= n; j++)
        if (g[t][j] == 1 && x[t] == x[j])
            return 0;
    return 1;
}

int num_m() {  //計(jì)算可行解中的顏色種類(lèi)數(shù)
    int ans = 0;
    int temp[101] = { 0 };
    for (int i = 1;i <= n;i++) {
        temp[x[i]] = 1;
    }
    for (int i = 1;i <= 100;i++)
        ans += temp[i];
    return ans;
}
void back_track(int t)
{
    int i;
    if (t > n)
    {
        sum++; //找到可行解，總數(shù)+1
        //for (i = 1; i <= n; i++)
        //    printf("%d ", x[i]);
        // printf("\n");
        int xx = num_m();
        if (xx < ans)
            ans = xx;
    }
    else
    {
        for (int i = 1; i <= m; i++)// 遍歷節(jié)點(diǎn)的每種顏色取值
        {
            x[t] = i;
            if (ok(t))
                back_track(t + 1);
            x[t] = 0;
        }
    }
}

int main()
{
    cin >> n >> m; //n個(gè)頂點(diǎn)，m種顏色

    int a, b;
    cin >> a >> b;
    while (!(a == 0 && b == 0)) { //構(gòu)造鄰接矩陣
        g[a][b] = 1;
        g[b][a] = 1;
        cin >> a >> b;

    }
    back_track(1);
    if (sum)
        cout << sum << " " << ans << endl;
    else
        cout << 0 << " " << 0 << endl;
    return 0;
}

算法分析與知識(shí)點(diǎn)：

這個(gè)問(wèn)題和八皇后還有求子集和等問(wèn)題都具有類(lèi)似之處，其核心在通過(guò)遍歷找到所有的問(wèn)題子集 ，但是在遞歸遍歷的時(shí)候，都在加一個(gè)判斷，將那些明顯不滿(mǎn)足條件的情況給直接排出，減少問(wèn)題的規(guī)模，其實(shí)這類(lèi)問(wèn)題，在遞歸遍歷的時(shí)候都是類(lèi)似與對(duì)一顆樹(shù)的便利每個(gè)節(jié)點(diǎn)相當(dāng)走到此時(shí)的狀態(tài)，然后再判斷此時(shí)的狀態(tài)是否能繼續(xù)走下去，如果不能就將其回溯到上一個(gè)節(jié)點(diǎn)，避免浪費(fèi)時(shí)間。

給定圖g（v，e）和m種顏色，如果這個(gè)圖不是m可著色，給出否定回答，是的話(huà)找出所有不同著色法。

分析：

用鄰接矩陣表示圖g，如果頂點(diǎn)i跟j之間有邊，則g[i][j] = 1,否則g[i][j] = 0.用整數(shù)1，2，…，m表示m種顏色，頂點(diǎn)i的顏色用x[i]表示，所以x[1：n]是一種著色方案。

在算法traceback中，當(dāng)i>n時(shí)，就是所有頂點(diǎn)都上了色，得到新的m著色方案，當(dāng)前m著色方案總數(shù)sum增一，輸出方案。

當(dāng)i<n時(shí)，就是未著色完所有頂點(diǎn)，當(dāng)前頂點(diǎn)i有x[i] = 1, 2…m種顏色可圖，對(duì)于每種顏色由函數(shù)ok判斷可行性，并用dfs對(duì)可行顏色搜索，或減去不可行方案。

以上就是C++算法學(xué)習(xí)之回溯法的應(yīng)用的詳細(xì)內(nèi)容，更多關(guān)于C++回溯法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論