迷宮問題

有一個迷宮：

S**.
....
***T

（其中字符S表示起點，字符T表示終點，字符*表示墻壁，字符.表示平地。你需要從S出發(fā)走到T，每次只能向上下左右相鄰的位置移動，不能走出地圖，也不能穿過墻壁，每個點只能通過一次。）

現(xiàn)在需要你求出是否可以走出這個迷宮

我們將這個走迷宮過程稱為dfs（深度優(yōu)先搜索）算法。

思路

當(dāng)我們搜索到了某一個點，有這樣3種情況：

1.當(dāng)前我們所在的格子就是終點。

2.如果不是終點，我們枚舉向上、向下、向左、向右四個方向，依次去判斷它旁邊的四個點是否可以作為下一步合法的目標(biāo)點，如果可以，那么我們就進(jìn)行這一步，走到目標(biāo)點，然后繼續(xù)進(jìn)行操作。

3.當(dāng)然也有可能我們走到了“死胡同”里（上方、下方、左方、右方四個點都不是合法的目標(biāo)點），那么我們就回退一步，然后從上一步所在的那個格子向其他未嘗試的方向繼續(xù)枚舉。

怎樣才能算“合法的目標(biāo)點”？

1.必須在所給定的迷宮范圍內(nèi)

2.不能是迷宮邊界或墻。

3.這個點在搜索過程中沒有被走過（這樣做是因為，如果一個點被允許多次訪問，那么肯定會出現(xiàn)死循環(huán)的情況——在兩個點之間來回走。）

實現(xiàn)代碼

#include <iostream>
using namespace std;
int n, m;
string maze[105];
int sx, sy;
bool vis[105][105];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};//四個方向的方向數(shù)組
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y) {
    vis[x][y] = 1;//點已走過標(biāo)記
    if (maze[x][y] == 'T') {//到達(dá)終點
        return 1;
    }
    for (int i = 0; i < 4; ++i) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
            /*
            1.in(tx, ty) : 即將要訪問的點在迷宮內(nèi)
            2.!vis[tx][ty] : 點沒有走過
            3.maze[tx][ty] != '*' : 不是墻
            */
            if (dfs(tx, ty)) {
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> maze[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (maze[i][j] == 'S') {
                //記錄起點的坐標(biāo)
                sx = i;
                sy = j;
            }
        }
    }
    if (dfs(sx, sy)) {
        puts("Yes");
    } else {
        puts("No");
    }
    return 0;
}

深搜的剪枝優(yōu)化

可行性剪枝

剪枝，顧名思義，就是通過一些判斷，砍掉搜索樹上不必要的子樹。有時候，在搜索過程中我們會發(fā)現(xiàn)某個結(jié)點對應(yīng)的子樹的狀態(tài)都不是我們要的結(jié)果，那么我們其實沒必要對這個分支進(jìn)行搜索，直接“砍掉”這棵子樹（直接 return退出），就是"剪枝"。

我們舉一個例子：

給定n個整數(shù)，要求選出K個數(shù)，使得選出來的K個數(shù)的和為sum。

如上圖，當(dāng)k=2的時候，如果已經(jīng)選了2個數(shù)，再往后選更多的數(shù)是沒有意義的。所以我們可以直接減去這個搜索分支，對應(yīng)上圖中的剪刀減去的那棵子樹。

又比如，如果所有的數(shù)都是正數(shù)，如果一旦發(fā)現(xiàn)當(dāng)前和的值都已經(jīng)大于sum了，那么之后不管怎么選，選擇數(shù)的和都不可能是sum了，就可以直接終止這個分支的搜索。

例：從1,2,3,?,30這30個數(shù)中選8個數(shù)，使得和為200。

我們可以加如下剪枝

if (數(shù)字個數(shù) > 8) return ;

if (總和 > 200) return ;

經(jīng)過嘗逝后發(fā)現(xiàn)：

沒有剪枝

加剪枝：

最優(yōu)性剪枝

我們再看一個問題：

有一個n×m大小的迷宮。其中字符S表示起點，字符T表示終點，字符*表示墻壁，字符.表示平地。你需要從S出發(fā)走到T，每次只能向上下左右相鄰的位置移動，并且不能走出地圖，也不能走進(jìn)墻壁。保證迷宮至少存在一種可行的路徑，輸出S走到T的最少步數(shù)。

對于求最優(yōu)解（從起點到終點的最小步數(shù)）這種問題，通?？梢杂米顑?yōu)性剪枝，比如在求解迷宮最短路的時候，如果發(fā)現(xiàn)當(dāng)前的步數(shù)已經(jīng)超過了當(dāng)前最優(yōu)解，那從當(dāng)前狀態(tài)開始的搜索都是多余的，因為這樣搜索下去永遠(yuǎn)都搜不到更優(yōu)的解。通過這樣的剪枝，可以省去大量冗余的計算。

此外，在搜索是否有可行解的過程中，一旦找到了一組可行解，后面所有的搜索都不必再進(jìn)行了，這算是最優(yōu)性剪枝的一個特例。

現(xiàn)在我們考慮用dfs來解決這個問題，第一個搜到的答案res并不一定是正解，但是正解一定小于等于res。于是如果當(dāng)前步數(shù)大于等于res就直接剪枝。

在dfs函數(shù)內(nèi)加入如下代碼

if (目前步數(shù) >= res) return ;

if (目前所處的位置字符 == 'T') {
    答案 = 目前步數(shù);//因為我們在剛才已經(jīng)進(jìn)行了一次剪枝，所以我們現(xiàn)在是可以保證目前答案大于之前答案的
    return ;
}

好啦，到這里就結(jié)束了捏~

到此這篇關(guān)于C語言中深度優(yōu)先搜索(DFS)算法的示例詳解的文章就介紹到這了,更多相關(guān)C語言深度優(yōu)先搜索算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論