java - 深度优先搜索的递归算法

Question

假设我有以下迷宫:(格式不正确)

#########################################
S... #... # # #... #
###.# ##### #.#.### # ### # ###.#.# #####
#...# #...# #.#...# # # #.#.# #...#
#.#####.#.###.###.##### ##### #.#.###.#.#
#.....#.#..... #...# #.#.....#.#
# ###.#.####### ###.###########.#######.#
# #.#.# # #...#......... # #.#
### #.#.# ### #######.#.########### # #.#
# # #.#.# # # # #...# # # .#
# # #.#.# # ### # # ##### ### # #######.#
# #...# # # # #                        .E
#########################################

S 代表迷宫的起点，E 代表迷宫的终点。我有两个给定的类(class)； 迷宫 和 细胞 。我必须构建以下递归辅助方法来找到迷宫的解决方案:

  -findPath(currentMaze:Maze, current:Cell, path:ArrayList<Cell>):ArrayList<Cell

This method recursively finds a path from the start of the currentMaze to its end that goes through the current Cell. The path is an ArrayList of the sequence of cells that was followed to get from the start of the maze to the current cell (i.e., the path explored so far). In order to avoid paths that are longer than needed, the algorithm should avoid revisiting cells already in this path. The algorithm should return null if there is no path from current to the end that only goes through each Cell at most once. Otherwise, it should return the complete path from the start of the maze to the end as a sequence of Cells in an ArrayList. You must implement this as a recursive algorithm. In order to explore all paths through neighbors that have not yet been visited, you will want to make use of Maze’s getNeighbors.

为了构建这个递归方法，我得到了以下方法:

+getStartCell():Cell Returns the start Cell of the maze
+getEndCell():Cell Returns the end Cell of the maze


 +getNeighbors(currentCell:Cell):
ArrayList<Cell>
Returns a list of all the cells that are connected to
currentCell. If there is a wall between
currentCell and its neighbor, it is not added to this
collection. 

到目前为止，这是我所做的:

 private static ArrayList <Cell> findPath(Maze currentMaze,Cell current,ArrayList <Cell> path){
   // Base Case
   if (current == currentMaze.getEndCell()) {
    return path;
   }
 if(currentMaze.getNeighbors(current).size()!=0)
currentMaze.getStartCell();
currentMaze.getNeighbors(current);
currentMaze.getEndCell();
}
}

我真的很难构建这个方法。

Answer 1

好的，就在这里。您不仅需要 DFS，还需要一种存储找到的路径的方法。

您为 findPath 建议的方法签名将不起作用。它的 path 参数是一个列表，它将在遍历时存储所有节点，因为即使它是一个递归算法，我们也不会在将它传递给下一个 findPath< 之前完全复制该列表 调用，坦率地说，我们不应该这样做来提高性能和减少内存消耗。

我能想到的最简单的方法是让每个单元格都指向它的父单元格。父单元格是发现单元格作为邻居的单元格。

我们必须为 findPath

使用以下签名

List<Cell> findPath(Maze currentMaze, Cell current)

当我们到达结束节点时，我们需要返回所有递归，因此状态必须存储在findPath之外。

剩下的很简单，我们可以使用下面的算法(伪代码)

path = null
findPath(maze, startCell)
printPath(maze, path)

findPath(currentMaze, current)
  if curent = endCell
    list = []
    while(current != null)
        list.add(0, current)
        current = current.parent
    path = list
  else if path != null
    current.visitStatus = IN_PROGRESS
    neighbours = getUnVisitedNeighbours(current)
    for each neibhbour in neighbours
        neighbour.parent = current
    findPath(currentMaze, neighbour)

    current.visitStatus = VISITED

printPath(currentMaze, path)
    for each cell in path
        cell.ch = 'O' //since path references are same as maze it will update maze as well

    print maze

注意:该算法不产生最短路径，只要找到任何路径就返回。

这是一个实际的 Java 实现。它从文本文件中读取迷宫。

以下是示例迷宫文本文件的 Github 链接。

https://github.com/ConsciousObserver/stackoverflow/tree/master/TestMaze

package com.example;

import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Stream;

import com.example.TestMaze.Cell.VisitStatus;

public class TestMaze {
    static List<Cell> resultPath = null;

    public static void main(String[] args) {
        String filePath = "maze2.txt";
        Maze currentMaze = new Maze(filePath);

        findPath(currentMaze, currentMaze.startCell);

        if(resultPath == null) {
            System.out.println("\nNo path exists for the Maze");
        } else {
            System.out.println("\nPath size : " + resultPath.size());
            printPathOnMaze(currentMaze, resultPath);
        }
    }

    private static void printPathOnMaze(Maze maze, List<Cell> path) {
        path.stream()
            .filter(cell-> !maze.isStartCell(cell) && !maze.isEndCell(cell))
            .forEach(cell-> cell.setCh('O'));

        maze.printCells();
    }

    private static List<Cell> findPath(Maze currentMaze, Cell current) {
        if(currentMaze.isEndCell(current)) {
            resultPath = new ArrayList<>();
            Cell traversalCell = current;

            while(traversalCell != null) {
                resultPath.add(0, traversalCell);
                traversalCell = traversalCell.getParentCell();
            }
            return resultPath;
        }

        if(resultPath == null) {

            if(Maze.isWall(current)) {
                current.setVisitStatus(VisitStatus.VISITED);
            } else {
                current.setVisitStatus(VisitStatus.IN_PROGRESS);
                List<Cell> neighbourList = currentMaze.getNeighbours(current);

                neighbourList.stream()
                    .filter(cell -> cell.getVisitStatus() == VisitStatus.UNVISITED)
                    .filter(cell -> cell.getVisitStatus() == VisitStatus.UNVISITED)
                    .forEach(neighbour -> {
                        neighbour.setParentCell(current);
                        findPath(currentMaze, neighbour);   
                    });

                current.setVisitStatus(VisitStatus.VISITED);
            }
        }

        return null;
    }

    public static boolean isCellInPath(Cell cell, List<Cell> path) {
        return path.stream().anyMatch(c -> c.getI() == cell.getI() && c.getJ() == c.getJ());
    }

    public static class Cell {
        private int i, j;
        private char ch;

        private Cell parentCell;

        public enum VisitStatus {VISITED, IN_PROGRESS, UNVISITED};

        private VisitStatus visitStatus = VisitStatus.UNVISITED;

        public Cell(int i, int j, char ch) {
            super();
            this.i = i;
            this.j = j;
            this.ch = ch;
        }

        public int getI() {
            return i;
        }

        public int getJ() {
            return j;
        }

        public char getCh() {
            return ch;
        }

        public void setCh(char ch) {
            this.ch = ch;
        }

        public VisitStatus getVisitStatus() {
            return visitStatus;
        }

        public void setVisitStatus(VisitStatus visitStatus) {
            this.visitStatus = visitStatus;
        }

        public Cell getParentCell() {
            return parentCell;
        }

        public void setParentCell(Cell parentCell) {
            this.parentCell = parentCell;
        }
    }

    public static class Maze {
        private Cell[][] grid;
        private Cell startCell;
        private Cell endCell;

        private static final char START_CELL_CHAR = 'S';
        private static final char END_CELL_CHAR = 'E';
        private static final char WALL_CHAR = '#';
        private static final char EMPTY_SPACE_CHAR = '.';

        public Maze(String filePath) {
            grid = createFromFile(filePath);
            printCells();
        }

        public Cell[][] getGrid() {
            return grid;
        }

        public Cell getStartCell() {
            return startCell;
        }

        public Cell getEndCell() {
            return endCell;
        }

        public boolean isStartCell(Cell cell) {
            return startCell.getI() == cell.getI() && startCell.getJ() == cell.getJ();
        }

        public boolean isEndCell(Cell cell) {
            return endCell.getI() == cell.getI() && endCell.getJ() == cell.getJ();
        }

        List<Cell> getNeighbours(Cell cell) {
            List<Cell> neighboursList = new ArrayList<>();
            int mazeHeight = grid.length;
            int mazeWidth = grid[0].length;

            if(cell.getI() - 1 > 0) {
                neighboursList.add(grid[cell.getI() - 1][cell.getJ()]);
            }
            if(cell.getI() + 1 < mazeHeight) {
                neighboursList.add(grid[cell.getI() + 1][cell.getJ()]);
            }
            if(cell.getJ() - 1 > 0) {
                neighboursList.add(grid[cell.getI()][cell.getJ() - 1]);
            }
            if(cell.getJ() + 1 < mazeWidth) {
                neighboursList.add(grid[cell.getI()][cell.getJ() + 1]);
            }
            return neighboursList;
        }

        public static boolean isWall(Cell cell) {
            return cell.getCh() == WALL_CHAR;
        }

        public static boolean isEmptySpace(Cell cell) {
            return cell.getCh() == EMPTY_SPACE_CHAR;
        }

        public void printCells() {
            Stream.of(grid).forEach(row-> {
                Stream.of(row).forEach(cell -> System.out.print(cell.getCh()) );
                System.out.println();
            });

        }

        private Cell[][] createFromFile(String filePath) {
            Cell[][] maze = null;
            try(Scanner scan = new Scanner(Paths.get(filePath)) ) {
                List<Cell[]> list = new ArrayList<>();

                for(int i = 0; scan.hasNext(); i++) {
                    String line = scan.nextLine();
                    char[] chArr = line.toCharArray();
                    Cell[] row = new Cell[chArr.length];

                    for(int j = 0; j < chArr.length; j++) {
                        char ch = chArr[j];
                        Cell cell = new Cell(i, j, ch);
                        row[j] = cell;
                        if(ch == START_CELL_CHAR) {
                            startCell = cell;
                        } else if (ch == END_CELL_CHAR) {
                            endCell = cell;
                        }
                    }

                    list.add(row);
                }

                if(startCell == null || endCell == null) {
                    throw new RuntimeException("Start cell or End cell not present");
                }
                maze = list.toArray(new Cell[][]{});
            } catch(Exception ex) {
                ex.printStackTrace();
            }


            return maze;
        }
    }
}

注意:您的样本没有解。

样本输入有解

#########################################
S....#....#.#.#....#.........#..........E
###.#.#####.#.#.###.#.#.#.#.###.#.#.#####
#...#.#...#.#.#...#.#.#.#.#.#.#...#......
#.#####.#.###.###.#####..####.#.#.###.#.#
#.....#.#......#...#.#.#.....#.#.........
#.###.#.#######.###.########.##.#######.#
#.#.#.#.#.#...#..........#.#.#...........
###.#.#.#.###.#######.#.####.######.#.#.#
#.#.#.#.#.#.#.#.#...#.#.#..#.............
#.#.#.#.#.#.###.#.#.#####.###.#.#######.#
#.#.....................................#
#########################################

输出

Path size : 89
#########################################
SOOO.#....#.#.#....#.........#...OOOOOOOE
###O#.#####.#.#.###.#.#.#.#.###.#O#.#####
#OOO#.#...#.#.#...#.#.#.#.#.#.#..O#..OOO.
#O#####.#.###.###.#####..####.#.#O###O#O#
#OOOOO#.#......#...#.#.#.....#.#.OOOOO.O.
#.###O#.#######.###.########.##.#######O#
#.#.#O#.#.#...#..........#.#.#.........O.
###.#O#.#.###.#######.#.####.######.#.#O#
#.#.#O#.#.#.#.#.#OOO#.#.#..#.OOO.......O.
#.#.#O#.#.#.###.#O#O#####.###O#O#######O#
#.#..OOOOOOOOOOOOO.OOOOOOOOOOO.OOOOOOOOO#
#########################################

注意:广度优先搜索可能会给出更好的结果。