啊哈算法之解救小哈 -开发者知识库

啊哈算法之解救小哈 -开发者知识库,第1张

簡述

本算法摘選自啊哈磊所著的《啊哈!算法》第四章第二節的題目——DFS算法解救小哈。文中代碼使用C語言編寫,博主通過閱讀和理解,重新由Java代碼實現了一遍,以此來加深對DFS算法的印象。

游戲設置

迷宮由n行m列的單元格組成(n和m小於等於50),每個單元格要么是空地要么是障礙物,障礙物是不能通行的,要求從迷宮起點開始找到一條通往迷宮中某個點的最短路徑。

解法思路

首先用一個二維數組來存儲迷宮,剛開始假設從迷宮入口(0, 0)開始,目標位置在(q, p),此行目的就是找到從(0, 0)到(q, p)的最短路徑。如果從入口的點,那么下一步只能是往右或者往下走,如果是到了迷宮中間的某個點,那么可能是往上下左右四個方向走,只能一個個去嘗試,索性我們這里就定義個順序,按照順時針(即右、下、左、上)的方向逐個嘗試

還有一個問題值得注意,就是已經路過的點,肯定是不需要計算在接下來嘗試的點上了,這里為了方便判斷,可以利用熟悉的桶來標記,已經經過的點都標記在桶里,使用完之后回來再清理桶標記位就行了。對於障礙物,遇到障礙物就換個方向重新開始,這里就是重新返回到下一次遞歸循環就行了。

注意,當我們遍歷之后找到了目標點位,但可能不是到達所使用的最短路徑,所以在找到目標點位之后,需要返回重新嘗試從其他的方向尋找,直到把所有的可能性都嘗試完了,最后才把最短的那條路徑輸出來。

現在我們使用深度優先搜索算法DFS來嘗試實現這個算法。先從dfs函數開始,思考當前步驟是什么樣的,下一步和當前步驟是一樣的,邊界條件是什么樣的。

我們給dfs函數定義三個參數x、y和step,分別表示下一步達到的坐標以及當前步數,如果判斷已經找到目標位置,即判斷(x, y)是否與目標位置相等即可,同時用當前所走的step數去判斷是否是最小步數,是則更新記錄到最小步數值。

在具體的代碼實現中,我們還應該關注到如何從順時針的四個方向上開始搜索目標,如何定位到下一個點位,同時判斷是否越界,或者是否是障礙物、或者該點位之前已經路過等等之類的問題。

代碼實現

 1 public class MazeDfs {
 2 
 3     /** 迷宮矩陣的大小:n行 m列 */
 4     private static final Integer n = 10, m = 10;
 5     /** 迷宮中的目標位置 */
 6     private static final Integer q = 6, p = 6;
 7     /** 從起點到目標位置所行的最小步數 */
 8     private static Integer minStep = 999;
 9     /** 迷宮地圖 */
10     private static int[][] maze = new int[50][50];
11     /** 桶,記錄步行經過的路徑位置 */
12     private static int[][] book = new int[50][50];
13 
14     /**
15      * 遞歸函數
16      * 往前走一步,查看當前位置是否目標位置,否則繼續往下一個方向前進
17      * @param x
18      * @param y
19      * @param step
20      */
21     public void dfs(int x, int y, int step) {
22         // 定義四個方向,依照順時針方向,依次向右、向下、向左、向上
23         int[][] next = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
24 
25         System.out.println("當前坐標點:"   x   " "   y);
26 
27         // 判斷是否到達目標位置
28         if(x == q && y == p) {
29             // 更新最小步數值
30             if(step < minStep) {
31                 minStep = step;
32             }
33             // 按照當前方式找到,則返回,換其他方式繼續找
34             return;
35         }
36 
37         // 枚舉四個方向的找法
38         int tx, ty, k;
39         for(k = 0; k < 4; k  ) {
40             // 計算出下一個步入的點的位置
41             tx = x   next[k][0];
42             ty = y   next[k][1];
43 
44             // 判斷這個方向的下一步是否越界
45             if(tx < 0 || tx >= n || ty < 0 || ty >= m) {
46                 continue;
47             }
48 
49             // 判斷該點是否為障礙物或者剛才已經路過
50             if(maze[tx][ty] == 0 && book[tx][ty] == 0) {
51                 // 標記這個點已經路過
52                 book[tx][ty] = 1;
53                 // 接着嘗試下一個點
54                 dfs(tx, ty, step   1);
55                 // 嘗試結束,取消這個點的標記
56                 book[tx][ty] = 0;
57             }
58         }
59         return;
60     }
61 
62     public static void main(String[] args) {
63         MazeDfs mazeDfs = new MazeDfs();
64        // 初始化,把迷宮矩陣用二維數組表示出來,空地用“0”表示,障礙物用“1”表示
65         // TODO
66 
67         // 從起點開始搜索,這里假設起點位置[0, 0],開始時步數為0
68         int startx = 0, starty = 0, step = 0;
69         // 在桶中標記起點已經歷
70         book[startx][starty] = 1;
71         // 從第一個位置開始
72         mazeDfs.dfs(startx, starty, step);
73 
74         // 輸出最少步數
75         System.out.println(String.format("從起點開始最少經過%d步可以到達目標位置。", minStep));
76     }
77 
78 }

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复