C++分支限界法怎么應(yīng)用

這篇文章主要講解了“C++分支限界法怎么應(yīng)用”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C++分支限界法怎么應(yīng)用”吧！

分支限界1

實(shí)驗(yàn)題目： 填格子4

題目描述：

有一個由數(shù)字 0、1 組成的方陣中，存在一任意形狀的封閉區(qū)域，封閉區(qū)域由數(shù)字1 包圍構(gòu)成，每個節(jié)點(diǎn)只能走上下左右 4 個方向?，F(xiàn)要求把封閉區(qū)域內(nèi)的所有空間都填寫成2 .例如： 6×6 的方陣：

輸入要求：

每組測試數(shù)據(jù)第一行一個整數(shù) n(1≤n≤30)

接下來 n 行，由 0 和 1 組成的 n×n 的方陣。

封閉區(qū)域內(nèi)至少有一個0

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

#include<bits/stdc++.h>
using namespace std;
const int M = 31;
int Map[M][M]; // 記錄輸入格子的情況
bool vis[M][M] = { false }; // 標(biāo)記格子訪問情況，默認(rèn)未訪問
int n;
queue <int > q;

void bfs(int x, int y) {  //廣度優(yōu)先搜索格子
    int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 上下左右四個方向
    vis[x][y] = true; //標(biāo)記格子為訪問過
    q.push(x);q.push(y);
    while (!q.empty()) {
        int w = q.front();
        q.pop();
        int e = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {  //遍歷四個方向向外擴(kuò)展一圈
            int now_x = w + dir[i][0];
            int now_y = e + dir[i][1];
            //判斷新格子是否合法
            if (1 <= now_x && now_x <= n && 1 <= now_y && now_y <= n && Map[now_x][now_y] == 0 && !vis[now_x][now_y]) {
                vis[now_x][now_y] = true;//標(biāo)記格子為訪問過
                q.push(now_x);q.push(now_y);
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> Map[i][j];
            if (Map[i][j] == 1)
                vis[i][j] = true;
        }
    }
    for (int i = 1;i <= n;i = i + n - 1) {//從邊緣兩行開始遍歷
        for (int j = 1; j <= n;j++) {
            if (vis[i][j])
                continue;
            bfs(i, j);
        }
    }

    for (int i = 1;i <= n;i = i + n - 1) {//從邊緣兩列開始遍歷
        for (int j = 1;j <= n;j++) {
            if (vis[j][i])
                continue;
            bfs(j, i);
        }
    }

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (vis[i][j])  // 屬于非封閉區(qū)域
                cout << Map[i][j] << " ";
            else
                cout << 2 << " ";
        }
        cout << endl;
    }
    return 0;
}

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

本題的要求是找出給定方陣中的封閉區(qū)域并將區(qū)域內(nèi)的方格填為2。已知封閉區(qū)域是由一圈完整的1所圍成的，所以只需要遍歷找到1和邊界所圍成的0并加以標(biāo)記，最后只需要將方陣中未標(biāo)記的方格輸出為2就好了。

本題采用廣度優(yōu)先的搜索策略，每次以邊界上的一個0為廣度優(yōu)先搜索的的起點(diǎn)，可以得知當(dāng)遍歷完邊界上的0所有邊界和1所圍成的區(qū)域就都被標(biāo)記了。

實(shí)驗(yàn)題目： 不如走樓梯

題目描述：

有個電梯，每一層樓都可以停，只是算法混亂了，所以你得寫個補(bǔ)?。坏趇層樓(1<=i<=N)上有一個數(shù)字Ki(0<=Ki<=N)，表示上或下的層數(shù)（相對于當(dāng)前層），每層樓都可以上或下。當(dāng)然，如果不能滿足要求（沒有的層），相應(yīng)的按鈕就會失靈。例如：3 3 1 2 5代表了Ki（在第一層可以上或下3層；當(dāng)然下是不可能的，第三層可以上或下1層），從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因?yàn)闆]有-2樓。那么，從A樓到B樓至少要按幾次按鈕？

輸入要求：

共二行。

第一行為3個用空格隔開的正整數(shù)，表示 N,A,B（共基層，開始層，結(jié)束層）；(1&le;N&le;200, 1&le;A,B&le;N)N,A,B(1&le;N&le;200,1&le;A,B&le;N)。

第二行為N個用空格隔開的非負(fù)整數(shù)，表示每層按鈕的數(shù)值Ki。

輸出要求：

一行，即最少按鍵次數(shù)；若無法到達(dá)，則輸出&minus;1。

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

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

int n, a, b, k[210];
bool f[210] = { false }; // 標(biāo)記樓層是否訪問過，默認(rèn)沒有

void bfs() {
    queue<pair<int, int> > q; // 定義隊(duì)列
    pair<int, int> p, t; // <當(dāng)前第幾層，當(dāng)前按了幾次>
    p.first = a; p.second = 0;// 賦初值
    q.push(p);//進(jìn)入隊(duì)列
    while (!q.empty()) {//隊(duì)列非空
        p = q.front(); q.pop();
        if (f[p.first]) // 如果樓層訪問過
            continue;
        f[p.first] = true; // 標(biāo)記樓層訪問過
        if (p.first == b) { // 達(dá)到目標(biāo)樓層
            cout << p.second << endl;
            return;// 退出搜索
        }
        if (p.first - k[p.first] > 0) { // 向下按
            t.first = p.first - k[p.first];
            t.second = p.second + 1;
            q.push(t);
        }
        if (p.first + k[p.first] <= n) { // 向上按
            t.first = p.first + k[p.first];
            t.second = p.second + 1;
            q.push(t);
        }
    }
    cout << -1 << endl;
}

int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)
        cin >> k[i];
    bfs(); //廣度優(yōu)先搜索答案
    return 0;
}

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

本題要求在給定樓層和電梯按鈕分布的前提下給出從初始樓層到目標(biāo)樓層的最小按數(shù)。本題的路徑搜索采用廣度優(yōu)先的搜索策略，只要搜索到目標(biāo)樓層就停止搜索。最小的按電梯按鈕數(shù)為此時(shí)搜索的深度。

分支限界 堂練

實(shí)驗(yàn)題目： 再填格子

題目描述：

有一個由數(shù)字 0、1 組成的方陣中，存在一任意形狀的封閉區(qū)域，封閉區(qū)域由數(shù)字1 包圍構(gòu)成，每個節(jié)點(diǎn)只能走上下左右 4 個方向。現(xiàn)要求只把【最大封閉區(qū)域】內(nèi)的空間填寫成2 。

輸入要求：

每組測試數(shù)據(jù)第一行一個整數(shù) n(1&le;n&le;30)

接下來 n 行，由 0 和 1 組成的 n&times;n 的方陣。

封閉區(qū)域內(nèi)至少有一個0，測試數(shù)據(jù)保證最大區(qū)域只有一個。

輸出要求：

已經(jīng)填好數(shù)字 2 的完整方陣。(每個數(shù)字后面有一個空格?。?/p>

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

#include<bits/stdc++.h>
using namespace std;
int a[35][35] = { 0 };  // 記錄方陣初始情況
int n;
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; // 上下左右四個方向
int cnt = 0; //記錄某一封閉區(qū)域的面積
int cnt_max = 0; // 記錄最大封閉區(qū)域的面積
int id = 3; // 搜索標(biāo)記
int id_max = id; // 最大封閉區(qū)域?qū)?yīng)的搜索標(biāo)記
void prit() {  // 格式化輸出函數(shù)
	int i, j;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (a[i][j] == 1) {
				cout << a[i][j] << ' ';
			}
			else if (a[i][j] != id_max) {
				cout << '0' << ' ';
			}
			else {
				cout << '2' << ' ';
			}
		}
		cout << endl;
	}
}

void dfs(int x, int y)//將與其鄰接的0坐標(biāo)改為id
{
	int i;

	if (a[x][y] != 0 || x < 0 || x > n + 1 || y < 0 || y > n + 1) { //檢查是否符合條件
		return;
	}

	a[x][y] = id;
	cnt++;

	for (i = 0; i < 4; i++) { // 搜索四個方向
		dfs(x + dir[i][0], y + dir[i][1]);
	}
}
int main() {
	int i, j;
	cin >> n;

	for (i = 1; i <= n; i++) { //輸入方陣
		for (j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	//最外圍的0不形成封閉區(qū)域
	dfs(0, 0);
	id++;
	for (i = 2; i < n; i++) {//從第二層開始形成封閉區(qū)域
		for (j = 2; j < n; j++) {
			cnt = 0;
			dfs(i, j);
			if (cnt > cnt_max) { // 判斷是否為最大封閉區(qū)域
				cnt_max = cnt;
				id_max = id;
			}
			id++; // 搜索標(biāo)記+1
		}
	}
	prit();
	return 0;
}

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

首先在數(shù)組外面多圍上一圈0，通過深搜將外層的0及其連接塊染色染色后，剩下的0元素都為封閉區(qū)域，接下來找到最大的區(qū)域?qū)γ總€元素都進(jìn)行深搜，找到最大的區(qū)域，記錄其染色編號。

實(shí)驗(yàn)題目： 最短路徑

題目描述：

在下圖中，請使用廣度搜索求出a到b的最短路徑，有色區(qū)域?yàn)椴豢赏ㄟ^區(qū)域。

輸入要求：

第1行2個整數(shù)，表示區(qū)域的行數(shù)m和列數(shù)n。1<=m,n<=20

第2行4個整數(shù)，表示起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，坐標(biāo)計(jì)數(shù)從0開始。

第3行開始，m行n列的區(qū)域數(shù)據(jù)，0表示可通行，-1表示不可通行（圖中綠色部分）。

輸出要求：

如圖a的二維信息數(shù)據(jù)，數(shù)值表示步數(shù)。起點(diǎn)終點(diǎn)分別用字符a、b表示。

最后與b同層的點(diǎn)，除了b之外，其他點(diǎn)無需標(biāo)記。比如sample out只有b，沒有9。

每個數(shù)值靠右占3位輸出（含符號位），每行最后一個數(shù)值無空格換行。

詳見sample output。（如無路徑，按規(guī)則輸出即可。）

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

#include<bits/stdc++.h>
using namespace std;
int Map[21][21] = { 0 }; // 記錄區(qū)域可通行情況
int m, n;
queue <int > q; 
int num = 1; // 記錄當(dāng)前是第幾輪搜索
void bfs(int x, int y, int ex, int ey) {
	int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 上下左右四個方向
	q.push(x);q.push(y);
	while (!q.empty()) {
		int s = q.size() / 2; // 當(dāng)前搜索輪次有幾個點(diǎn)
		for (int k = 0;k < s;k++) {
			int cur_x = q.front();
			q.pop();
			int cur_y = q.front();
			q.pop();
			for (int i = 0;i < 4;i++) { // 遍歷搜索四個方向
				int now_x = cur_x + dir[i][0];
				int now_y = cur_y + dir[i][1];
				if (now_x == ex && now_y == ey)  // 判斷是否到終點(diǎn)
					return;

				if (0 <= now_x && now_x < n && 0 <= now_y && now_y < m && Map[now_x][now_y] == 0) { // 判斷當(dāng)前點(diǎn)是否符合條件
					q.push(now_x);q.push(now_y);
					Map[now_x][now_y] = num; // 標(biāo)記當(dāng)前點(diǎn)的搜索輪次
				}
			}
		}
		num++;
	}
}
int sx, sy, ex, ey;   // 起點(diǎn)終點(diǎn)坐標(biāo)
int main() {
	cin >> m >> n;
	cin >> sx >> sy >> ex >> ey;
	for (int i = 0;i < m;i++)
		for (int j = 0;j < n;j++)
			cin >> Map[i][j];
	bfs(sx, sy, ex, ey);//調(diào)用bfs函數(shù)求解
	for (int i = 0;i < m;i++) {
		for (int j = 0;j < n;j++) {
			if (i == sx && j == sy) // 起點(diǎn)
				cout << "  a";
			else if (i == ex && j == ey) //終點(diǎn)
				cout << "  b";
			else if (Map[i][j] == num) //與b同層的點(diǎn)
				cout << "  0";
			else {// 其余點(diǎn)
				if (Map[i][j] < num) 
					printf("%3d", Map[i][j]);
			}

			//cout << "(" << i << "," << j << ")" << endl;
		}
		cout << endl;
	}
	return 0;
}

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

這題的要求是在給定通行情況的地圖上找到從起點(diǎn)a到終點(diǎn)b的最短路徑，這題可采用廣度優(yōu)先的搜索策略來做，在向外拓展的時(shí)候?qū)⑿鹿?jié)點(diǎn)的標(biāo)記值設(shè)為上一節(jié)點(diǎn)的標(biāo)記值+1，只要終點(diǎn)b被搜索到就停止搜索，此時(shí)的搜索輪次就是從起點(diǎn)a到終點(diǎn)b的最短路徑。

或者可以直接采用層次遍歷的方法做，同樣是終點(diǎn)b被遍歷到就停止搜索。

感謝各位的閱讀，以上就是“C++分支限界法怎么應(yīng)用”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C++分支限界法怎么應(yīng)用這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！