我遇到了這個迷宮求解演算法：
public class Maze {
public static void main(String[] args) {
char[][] maze = {
{'.', '.', '.', '0', '0', '0', '0', '0', '0', '0'},
{'0', '0', '.', '.', '.', '0', '.', '.', '.', '0'},
{'0', '0', '.', '0', '.', '0', '.', '0', '.', '0'},
{'.', '.', '.', '0', '.', '0', '.', '0', '.', '0'},
{'.', '0', '0', '0', '.', '.', '.', '0', '.', '0'},
{'.', '.', '.', '.', '0', '0', '0', '.', '.', '0'},
{'.', '0', '0', '.', '.', '.', '0', '.', '.', '0'},
{'.', '.', '.', '0', '0', '.', '0', '0', '.', '.'},
{'0', '0', '.', '0', '0', '.', '.', '.', '0', '0'},
{'0', '0', '0', '0', '0', '0', '0', '.', '.', '.'},
};
print(maze);
if(traverse(maze, 0, 0)) {
System.out.println("SOLVED maze");
} else {
System.out.println("could NOT SOLVE maze");
}
print(maze);
}
private static void print(char[][] maze) {
System.out.println("-----------------------");
for(int x = 0; x < 10; x ) {
System.out.print("| ");
for(int y = 0; y < 10; y ) {
System.out.print(maze[x][y] " ");
}
System.out.println("|");
}
System.out.println("-----------------------");
}
public static boolean isValidSpot(char[][] maze, int r, int c) {
if(r >= 0 && r < 10 && c >= 0 && c < 10) {
return maze[r][c] == '.';
}
return false;
}
public static boolean traverse(char[][] maze, int r, int c) {
if(isValidSpot(maze, r, c)) {
//it is a valid spot
if(r == 9 && c == 9) {
return true;
}
maze[r][c] = '*';
//up
boolean returnValue = traverse(maze, r - 1, c);
//right
if(!returnValue) {
returnValue = traverse(maze, r, c 1);
}
//down
if(!returnValue) {
returnValue = traverse(maze, r 1, c);
}
//left
if(!returnValue) {
returnValue = traverse(maze, r, c - 1);
}
if(returnValue) {
System.out.println(r ", " c);
maze[r][c] = ' ';
}
return returnValue;
}
return false;
}
}
但我無法解決我腦海中的遞回。即使演算法在搜索出口點時遇到了死胡同，并且它將它通過的路徑標記為無效，它也會以某種方式回傳到最后一個檢查點，同時不列印死胡同路徑。這是最讓我困惑的部分。這個演算法中如何沒有列印死路？
我嘗試在每一步都列印迷宮，但仍然無法弄清楚如何不列印無效路徑。
uj5u.com熱心網友回復：
該函式實作了深度優先搜索，也稱為DFS查找路徑。您可以在此處閱讀有關 DFS 和 BFS的更多資訊。發生的情況基本上如下：
檢查當前坐標是否為結束坐標，如果是則回傳
True否則，請檢查您是否可以通過前進到達終點
2.1 如果你可以通過前進到達終點，列印這個坐標并回傳
True否則，檢查您是否可以通過向右前進到達終點
3.1 如果你可以通過前進到達終點，列印這個坐標并回傳
True否則，請檢查您是否可以通過向下推進到達終點
4.1 如果你可以通過前進到達終點，列印這個坐標并回傳
True否則，請檢查您是否可以通過向左前進到達終點
5.1 如果你可以通過前進到達終點，列印這個坐標并回傳
True否則， return
False，意味著從這個坐標你不能到達終點。
不是保留要訪問的狀態串列，而是將資訊存盤在遞回中。
可以在此處找到與迷宮中路徑的 DFS 搜索類似的問題，用Python 實作，并且可能更容易理解這個概念，因為它不是用遞回實作的，而是用串列實作的。
請注意，所寫的演算法不是找到最短路徑，而是找到了一條路徑。要找到最短路徑，您應該使用 BFS，因為它x在檢查帶步驟的路徑之前覆寫了所有帶步驟的路徑x 1。
uj5u.com熱心網友回復：
深度優先搜索并不是尋找最短路徑的最佳選擇。廣度優先搜索可確保您在找到解決方案（路徑）時處于最短路徑。
BFS 需要標記已搜索的位置（如代碼中的“*”），當前路徑長度。并保存剛剛到達的位置串列：邊界。
下一步從邊界看新的鄰居，這將形成新的邊界。鄰居是否應該是目標（(r == 9 && c == 9)此處）。
邊界最初是開始：{(0, 0)}。邊界點的數量最初會增加，然后隨著死胡同的消失再次減少。固定大小的陣列很復雜，因此 a SetorList更合適。
真正的遞回BFS 更容易，但您可能會遍歷邊界，并通過留下“面包屑”來重建最短路徑。
對于一個位置，record類是最簡單的。從 Java 16 開始。
record Location (int row, int column) {
List<Location> getNeighbors() {
List<Location> nbs = new ArrayList<>();
if (row > 0) {
nbs.add(new Location(row - 1, column));
}
if (row < 10-1) {
nbs.add(new Location(row 1, column));
}
if (column > 0) {
nbs.add(new Location(row, column - 1));
}
if (column < 10-1) {
nbs.add(new Location(row, column 1));
}
return nbs;
}
}
對于邊界，Set 更適合，因為從兩個舊邊界位置可以到達相同的新邊界位置。
Set<Location> border = new HashSet<>();
border.add(new Location(0, 0));
int pathLength = 0;
void moveToNextBorder(Set<Location> border) {
char breadCrumb = 'a' pathLength;
pathLength;
Set<Location> result = new HashSet<>();
for (Location oldLoc: border) {
maze[oldLoc.row][oldLoc.column] = breadCrumb;
}
for (Location oldLoc: border) {
for (Location loc: oldLoc.getNeighbors()) {
if (maze[loc.row][loc.column] == '.') {
result.add(loc); // Could already have been added.
}
}
}
border.clear();
border.addAll(result);
}
查看新邊框是否到達目標：
moveToNextBorder(border);
if (border.contains(new Location(9, 9))) {
// Take a shortest path, using breadCrumbs downto 'a'.
Location[] shortestPath = new Location[pathLength];
...
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/455068.html
上一篇：滿足條件時如何退出遞回？
下一篇：如何創建自定義排序