您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“怎么用Java深度優(yōu)先遍歷解決迷宮問題”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“怎么用Java深度優(yōu)先遍歷解決迷宮問題”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識吧。
什么是深度,即向下,深度優(yōu)先,即向下優(yōu)先,一口氣走到底,走到底發(fā)現(xiàn)沒路再往回走。
在算法實(shí)現(xiàn)上來講,深度優(yōu)先可以考慮是遞歸的代名詞,深度優(yōu)先搜索必然需要使用到遞歸的思路。
有的人可能會說了,我可以用棧來實(shí)現(xiàn),以迭代的方式,那么問題來了,棧這種數(shù)據(jù)結(jié)構(gòu),同學(xué)們認(rèn)為是否也囊括了遞歸呢?Java語言的方法區(qū)本身也是實(shí)現(xiàn)在一個棧空間上的。
我們以一個簡單的迷宮為例,以1代表墻,0代表路徑,我們構(gòu)造一個具有出入口的迷宮。
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
以上面這個0為入口,下面這個0為出口,那么深度優(yōu)先的算法遍歷順序,方向的遍歷順序為左下右上,以dp[0][2]為入口,我把這個過程列在下面了:
第一步:
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)先算法需要開始回退,最終會回退到dp[1][2]這個位置,然后向右走
第八步:
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)像我們的人生,需要不斷試錯,錯了就退,直到找到一條通往出口的路。
現(xiàn)在讓我們動手用代碼實(shí)現(xiàn)一下上面的步驟吧。
以深度優(yōu)先的方式解決這個問題,主要考慮兩點(diǎn),首先是如何擴(kuò)展節(jié)點(diǎn),我們的順序是左,下,右,上,那么,應(yīng)該以什么樣的方式實(shí)現(xiàn)這個呢?第二點(diǎn),就是如何實(shí)現(xiàn)深度優(yōu)先,雖然原理上肯定是遞歸,但是應(yī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這個函數(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)。
然后,我們利用兩個方向數(shù)組作為移動方案,也就是
// 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ù)組類型的移動方式的兼容寫法,不管你的移動方向有多少,都可以配在x和y兩個數(shù)組中。定義了四個方向,現(xiàn)在我們需要思考遞歸的過程。
既然我完成的時候是返回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即可。
讀到這里,這篇“怎么用Java深度優(yōu)先遍歷解決迷宮問題”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識點(diǎn)還需要大家自己動手實(shí)踐使用過才能領(lǐng)會,如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。