溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“C++回溯法怎么應用”，內(nèi)容詳細，步驟清晰，細節(jié)處理妥當，希望這篇“C++回溯法怎么應用”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
題目描述：
N皇后的排列，每行一個不沖突；N<=13。
輸入要求：
一個數(shù)字N (6 <= N <= 13) 表示棋盤是N x N大小的
輸出要求：
前三行為前三個解，每個解的兩個數(shù)字之間用一個空格隔開。第四行只有一個數(shù)字，表示解的總數(shù)。
解的輸出順序為從上到下從左到右，小的優(yōu)先輸出
實驗代碼及注釋:
#include<bits/stdc++.h>
using namespace std;
int q[15] = { 0 }; //記錄n個皇后的擺放位置
// 下標為行，數(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表示未放上棋盤
queen(1); //從第一行開始遍歷
cout << sum << endl;
return 0;
}算法分析與知識點：
本題采用回溯算法思想來解決N皇后問題，這里用一個q[N]數(shù)組來記錄棋子擺放情況：
1.算法開始, 清空棋盤，當前行設為第一行，當前列設為第一列
2.在當前行，當前列的位置上判斷是否滿足條件(即保證經(jīng)過這一點的行,列與斜線上都沒有兩個皇后)，若不滿足，跳到第4步
3.在當前位置上滿足條件的情形：
在當前位置放一個皇后，若當前行是最后一行，記錄一個解；
若當前行不是最后一行，當前行設為下一行, 當前列設為當前行的第一個待測位置；
若當前行是最后一行，當前列不是最后一列，當前列設為下一列；
若當前行是最后一行，當前列是最后一列，回溯，即清空當前行及以下各行的棋盤，然后，當前行設為上一行，當前列設為當前行的下一個待測位置；
以上返回到第2步
4.在當前位置上不滿足條件的情形：
若當前列不是最后一列，當前列設為下一列，返回到第2步；
若當前列是最后一列了，回溯，即，若當前行已經(jīng)是第一行了，算法退出，否則，清空當前行及以下各行的棋盤，然后，當前行設為上一行，當前列設為當前行的
下一個待測位置，返回到第2步;
題目描述：
符號三角形的 第1行有n個由“+”和“-”組成的符號 ，以后每行符號比上行少1個，2個同號下面是“+”，2個異號下面是“-” 。計算有多少個不同的符號三角形，使其所含“+” 和“-” 的個數(shù)相同。
輸入要求：
整數(shù)n(n<=20)。
輸出要求：
符合要求的符號三角形的個數(shù)。
實驗代碼及注釋:
#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列的符號
if (a[t][i])//若為＋
sum2++;
}
}
if (2 * (sum1 + sum2) == (n * (n + 1) / 2)) //記錄+總數(shù)是否為符號總數(shù)的一半
sum++;
}
void dfs(int x) { // x表示考慮頂層第x個位置的符號
for (int i = 0;i < 2;i++) {
//0=>-;1=>+
if (i)
sum1++; // 記錄頂層+的數(shù)量
a[n][x] = i;
if (x == n)//考慮完頂層的一種符號擺放，進行檢查
check();
else
dfs(x + 1);
if (i)
sum1--; // 若上擺放為+，則+數(shù)量回退1
}
}
int main()
{
cin >> n;
if ((n * (n + 1) / 2) % 2 == 1) //判斷符號總數(shù)奇偶性
cout << 0 << endl;
else {
dfs(1);
cout << sum << endl;
}
return 0;
}算法分析與知識點：
本題主要運用回溯的思想，這題的特點是不能輸入元素，而且只要確定的頂層的n的符號的排列情況，就可以得到整個符號三角形的排列情況，因此只需要對符號三角形的頂層進行遍歷就好了。題目中有要求+和-的數(shù)量要一樣，所以符號三角形的符號總數(shù)要是偶數(shù)，否則解決方案數(shù)為0。
令0和1分別代表-和+，其他層在頂層確定后即確定了，不需要枚舉。采用dfs對第一層的符號排列情況進行遍歷，遍歷完n后就可得到答案。
題目描述：
一天Luna在森林里探險的時候不小心走入了一個迷宮，迷宮可以看成是由n * n的格點組成，每個格點只有2種狀態(tài)：^ 和 # ；前者表示可以通行后者表示不能通行。當Luna處在某個格點時，她只能移動到東南西北(或者說上下左右)四個方向之一的相鄰格點上，Luna想要從起點A走到終點B（中途不能走出迷宮）。如果起點或者終點有一個不能通行(為#)，則當做無法通行。
輸入要求：
第1行是測試數(shù)據(jù)的組數(shù)k，后面跟著k組輸入。
每組測試數(shù)據(jù)的第1行是一個正整數(shù)n (1 <= n <= 100)，表示迷宮的規(guī)模是n * n的。
接下來是一個n * n的矩陣，矩陣中的元素為 . 或者 #。
再接下來一行是4個整數(shù)ar,ac,br,bc。表示A處在第ar行，第ac列，B處在第br行, 第bc列。注意坐標ar，ac，br，bc全部是從0開始計數(shù)的類似[1,4][5,6]被認為是覆蓋了[1,6]。
輸出要求：
YES或NO
實驗代碼及注釋:
#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標記搜索完畢后是否能到達終點
void dfs(int ha, int la)
{
if (ha == hb && la == lb) // 判斷是否達到終點
{
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] = '#';//只走一次，每個方都要走一遍，只要連通，肯定能到終點
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;//提前判斷始點和終點是否符合要求
else
{
flag = 0;
dfs(ha, la); //dfs搜索路徑
if (flag == 0) cout << "NO" << endl;
}
}
return 0;
}算法分析與知識點：
本采用深度優(yōu)先的搜索方式來搜索全部路徑，大致思路為：從當前點出發(fā)，往四個方位探尋找出所有與之相鄰的且尚未被訪問過的點，從中暫時先選取一個點作為當前點繼續(xù)上述過程，直到到達目的地或者再也無法探尋到能前進的點，再返回。如果當前搜索的點到達了目標點，flag標記為true，返回即可。若所有能到達的點都搜索完了，flag仍為false，則無法到達。
題目描述：
給定圖G=(V, E)，需要為圖G的各頂點著色，是否有一種著色法使G中相鄰的兩個頂點有不同的顏色?
輸入要求：
第一行是頂點的個數(shù)n（2≤n≤10），顏色數(shù)m（1≤m≤n）。
接下來是頂點之間的連接關系：a b；表示a和b相鄰。頂點從1開始計。
當a，b同時為0時表示輸入結(jié)束。
輸出要求：
輸出著色方案總數(shù)和最少顏色數(shù)。如果無可行方案，顏色數(shù)為0。
實驗代碼及注釋:
#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) // 判斷當前層節(jié)點是否可行
{
for (int j = 1; j <= n; j++)
if (g[t][j] == 1 && x[t] == x[j])
return 0;
return 1;
}
int num_m() { //計算可行解中的顏色種類數(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é)點的每種顏色取值
{
x[t] = i;
if (ok(t))
back_track(t + 1);
x[t] = 0;
}
}
}
int main()
{
cin >> n >> m; //n個頂點，m種顏色
int a, b;
cin >> a >> b;
while (!(a == 0 && b == 0)) { //構造鄰接矩陣
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;
}算法分析與知識點：
這個問題和八皇后還有求子集和等問題都具有類似之處，其核心在通過遍歷找到所有的問題子集 ，但是在遞歸遍歷的時候，都在加一個判斷，將那些明顯不滿足條件的情況給直接排出，減少問題的規(guī)模，其實這類問題，在遞歸遍歷的時候都是類似與對一顆樹的便利每個節(jié)點相當走到此時的狀態(tài)，然后再判斷此時的狀態(tài)是否能繼續(xù)走下去，如果不能就將其回溯到上一個節(jié)點，避免浪費時間。
給定圖g（v，e）和m種顏色，如果這個圖不是m可著色，給出否定回答，是的話找出所有不同著色法。
分析：
用鄰接矩陣表示圖g，如果頂點i跟j之間有邊，則g[i][j] = 1,否則g[i][j] = 0.用整數(shù)1，2，…，m表示m種顏色，頂點i的顏色用x[i]表示，所以x[1：n]是一種著色方案。
在算法traceback中，當i>n時，就是所有頂點都上了色，得到新的m著色方案，當前m著色方案總數(shù)sum增一，輸出方案。
當i<n時，就是未著色完所有頂點，當前頂點i有x[i] = 1, 2…m種顏色可圖，對于每種顏色由函數(shù)ok判斷可行性，并用dfs對可行顏色搜索，或減去不可行方案。
讀到這里，這篇“C++回溯法怎么應用”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內(nèi)容的文章，歡迎關注億速云行業(yè)資訊頻道。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
