快捷導(dǎo)航

詳解Java利用深度優(yōu)先遍歷解決迷宮問題

更新時(shí)間：2022年02月01日 08:27:09 作者：炒雞辣雞123

深度優(yōu)先遍歷：深度優(yōu)先遍歷是圖論中的經(jīng)典算法。其利用了深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?，采用拓?fù)渑判虮砜梢越鉀Q很多相關(guān)的圖論問題，如最大路徑問題等等。本文將利用深度優(yōu)先遍歷解決迷宮問題，感興趣的可以了解一下

什么是深度優(yōu)先

什么是深度，即向下，深度優(yōu)先，即向下優(yōu)先，一口氣走到底，走到底發(fā)現(xiàn)沒路再往回走。

在算法實(shí)現(xiàn)上來講，深度優(yōu)先可以考慮是遞歸的代名詞，深度優(yōu)先搜索必然需要使用到遞歸的思路。

有的人可能會(huì)說了，我可以用棧來實(shí)現(xiàn)，以迭代的方式，那么問題來了，棧這種數(shù)據(jù)結(jié)構(gòu)，同學(xué)們認(rèn)為是否也囊括了遞歸呢？Java語言的方法區(qū)本身也是實(shí)現(xiàn)在一個(gè)?？臻g上的。

一個(gè)簡(jiǎn)單的例子

我們以一個(gè)簡(jiǎn)單的迷宮為例，以1代表墻，0代表路徑，我們構(gòu)造一個(gè)具有出入口的迷宮。

1 1 0 1 1 1 1 1 1

1 0 0 0 0 0 0 1 1

1 0 1 1 1 1 0 1 1

1 0 0 0 0 1 0 0 1

1 1 1 1 1 1 1 0 1

以上面這個(gè)0為入口，下面這個(gè)0為出口，那么深度優(yōu)先的算法遍歷順序，方向的遍歷順序?yàn)樽笙掠疑?，以dp[0][2]為入口，我把這個(gè)過程列在下面了：

第一步：

dp[0][2] -> dp[1][2]

第二步：

dp[1][2] -> dp[1][1]

第三步：

dp[1][1] -> dp[2][1]

第四步：

dp[2][1] -> dp[3][1]

第五步：

dp[3][1] -> dp[3][2]

第六步：

dp[3][2] -> dp[3][3]

第七步：

dp[3][3] -> dp[3][4]

第八步：

dp[3][4] -> dp[3][5] 由于 dp[3][5]是墻，所以深度優(yōu)先算法需要開始回退，最終會(huì)回退到dp[1][2]這個(gè)位置，然后向右走

第八步：

dp[1][2] -> dp[1][3]

第九步：

dp[1][3] -> dp[1][4]

第十步：

dp[1][4] -> dp[1][5]

第十一步：

dp[1][5] -> dp[1][6]

第十二步：

dp[1][6] -> dp[2][6]

第十三步：

dp[2][6] -> dp[3][6]

第十四步：

dp[3][6] -> dp[3][7]

第十五步：

dp[3][7] -> dp[4][7] 終點(diǎn)，程序退出

可以發(fā)現(xiàn)，深度優(yōu)先算法有點(diǎn)像我們的人生，需要不斷試錯(cuò)，錯(cuò)了就退，直到找到一條通往出口的路。

現(xiàn)在讓我們動(dòng)手用代碼實(shí)現(xiàn)一下上面的步驟吧。

程序?qū)崿F(xiàn)

以深度優(yōu)先的方式解決這個(gè)問題，主要考慮兩點(diǎn)，首先是如何擴(kuò)展節(jié)點(diǎn)，我們的順序是左，下，右，上，那么，應(yīng)該以什么樣的方式實(shí)現(xiàn)這個(gè)呢？第二點(diǎn)，就是如何實(shí)現(xiàn)深度優(yōu)先，雖然原理上肯定是遞歸，但是應(yīng)該如何遞歸呢？要解決這兩個(gè)問題，請(qǐng)看示例代碼，以Java為例：

package com.chaojilaji.book;

import com.chaojilaji.book.util.InputUtils;

import java.util.HashSet;
import java.util.Set;

import static com.chaojilaji.book.util.CheckUtils.canAdd;

public class Dfs {

    public static Integer dfs(String[][] a, int currentX, int currentY, int chux, int chuy, Set<Integer> cache) {
        System.out.println(currentY + " " + currentX);
        if (currentX == chux && currentY == chuy) {
            return 1;
        }
        // TODO: 2022/1/11 枚舉子節(jié)點(diǎn)，左 下 右 上
        int[] x = new int[]{-1, 0, 1, 0};
        int[] y = new int[]{0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
                Integer tmp = dfs(a, currentX + x[i], currentY + y[i], chux, chuy, cache);
                if (tmp != 0) {
                    System.out.println(currentY + " " + currentX + " 結(jié)果路徑");
                    return tmp + 1;
                }
            }
        }
        System.out.println(currentY + " " + currentX + " 回滾");
        return 0;
    }

    public static Integer getAns(String[][] a) {
        int m = a[0].length;
        int n = a.length;
        int rux = -1, ruy = 0;
        int chux = -1, chuy = n - 1;
        for (int i = 0; i < m; i++) {
            if (a[0][i].equals("0")) {
                // TODO: 2022/1/11 找到入口
                rux = i;
            }
            if (a[n - 1][i].equals("0")) {
                chux = i;
            }
        }
        Set<Integer> cache = new HashSet<>();
        cache.add(rux * 100000 + ruy);
        System.out.println("打印行走過程");
        return dfs(a, rux, ruy, chux, chuy, cache)-1;
    }

    public static void demo() {
        String x = "1  1  0  1  1  1  1  1  1\n" +
                "1  0  0  0  0  0  0  1  1\n" +
                "1  0  1  1  1  1  0  1  1\n" +
                "1  0  0  0  0  1  0  0  1\n" +
                "1  1  1  1  1  1  1  0  1";
        String[][] a = InputUtils.getInput(x);
        Integer ans = getAns(a);
        System.out.println(ans == -1 ? "不可達(dá)" : "可達(dá)，需要行走" + ans + "步");

    }

    public static void main(String[] args) {
        demo();
    }

}

這里的canAdd方法是臨界判斷函數(shù)，如下：

/**
     * 臨界判斷
     * @param a
     * @param x
     * @param y
     * @param cache
     * @return
     */
public static Boolean canAdd(String[][] a, Integer x, Integer y, Set<Integer> cache) {
    int m = a[0].length;
    int n = a.length;
    if (x < 0 || x >= m) {
        return false;
    }
    if (y < 0 || y >= n) {
        return false;
    }
    if (a[y][x].equals("0") && !cache.contains(x * 100000 + y)) {
        cache.add(x * 100000 + y);
        return true;
    }
    return false;
}

可以瞧見，這里面最核心的代碼在于dfs這個(gè)函數(shù)，讓我們來深入分析一波

public static Integer dfs(String[][] a, int currentX, int currentY, int chux, int chuy, Set<Integer> cache) {
    System.out.println(currentY + " " + currentX);
    if (currentX == chux && currentY == chuy) {
        return 1;
    }
    // TODO: 2022/1/11 枚舉子節(jié)點(diǎn)，左 下 右 上
    int[] x = new int[]{-1, 0, 1, 0};
    int[] y = new int[]{0, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
        if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
            Integer tmp = dfs(a, currentX + x[i], currentY + y[i], chux, chuy, cache);
            if (tmp != 0) {
                System.out.println(currentY + " " + currentX + " 結(jié)果路徑");
                return tmp + 1;
            }
        }
    }
    System.out.println(currentY + " " + currentX + " 回滾");
    return 0;
}

首先，dfs深度優(yōu)先，首先應(yīng)該寫的是判斷終止條件，這里的終止條件就是到達(dá)終點(diǎn)，即目前的橫縱坐標(biāo)等于出口的橫縱坐標(biāo)。

然后，我們利用兩個(gè)方向數(shù)組作為移動(dòng)方案，也就是

// TODO: 2022/1/11 枚舉子節(jié)點(diǎn)，左 下 右 上
    int[] x = new int[]{-1, 0, 1, 0};
    int[] y = new int[]{0, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
        if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
        }
    }

這種方法，是數(shù)組類型的移動(dòng)方式的兼容寫法，不管你的移動(dòng)方向有多少，都可以配在x和y兩個(gè)數(shù)組中。定義了四個(gè)方向，現(xiàn)在我們需要思考遞歸的過程。

既然我完成的時(shí)候是返回1，那么其實(shí)如果在這條路上的所有都應(yīng)該加1，所以，就有了下面的判斷

if (canAdd(a, currentX + x[i], currentY + y[i], cache)) {
    Integer tmp = dfs(a, currentX + x[i], currentY + y[i], chux, chuy, cache);
    if (tmp != 0) {
        System.out.println(currentY + " " + currentX + " 結(jié)果路徑");
        return tmp + 1;
    }
}

當(dāng)子dfs出來的結(jié)果不為0，說明該子dfs是可以到達(dá)出口的，那么直接把結(jié)果加1返回給上層即可。如果子dfs出來的結(jié)果為0，說明該子dfs是不能到達(dá)出口的，就直接返回0即可。

到此這篇關(guān)于詳解Java利用深度優(yōu)先遍歷解決迷宮問題的文章就介紹到這了,更多相關(guān)Java深度優(yōu)先遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: