深度优先搜索递归算法

Question

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

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

S 表示迷宫的起点，E 表示迷宫的终点。我有两个给定的课程;迷宫和细胞 .我必须构建以下递归助手方法来找到迷宫的解决方案：

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

此方法递归地找到一条从当前迷宫的开始到结束的路径，该路径通过当前Cell。该路径是从迷宫的开始到当前单元格的单元格序列的ArrayList（即到目前为止探索的路径）。为了避免超过所需的路径，算法应避免重新访问已在此路径中的单元格。如果没有从当前到结束的路径最多只通过每个Cell一次，则算法应返回null。否则，它应返回从迷宫开始到结束的完整路径，作为ArrayList中的单元格序列。您必须将其实现为递归算法。为了探索尚未访问的邻居的所有路径，您需要使用Maze的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

问问你自己，你怎样才能找到这条路。在每一步考虑你到达一些细胞。

1. 如果我已通过此单元格，例如此单元格已在我的路径中，请返回（避免循环）
2. 此单元格看起来不错，因此将其添加到路径中。
3. 如果该单元格是我的目标，请将当前路径存储到解决方案路径，保存解决方案，从路径中删除单元格，然后返回
4. 对于每个邻居，递归地重新启动邻居上的过程。
5. 从当前路径中删除当前单元格以保持当前路径不变

像这样的东西：

private static ArrayList <Cell> findPath(Maze currentMaze,Cell current,ArrayList <Cell> currentPath, ArrayList< ArrayList <Cell> > solutionsFound){
    // step 1
    if (currentPath.exists(current)) {
      return;
    }

    // step 2
    currentPath.add(current);

    // step 3
    if(current == currentMaze.getStartCell()){
      solutionsFound.add(currentPath.clone());
      currentPath.remove(current);
      return;
    }

    // step 4
    ArrayList<Cell> neighbors = currentMaze.getNeighbors(current);
    for(int i=0;i<neighbors.size();i++){
        findPath(currentMaze, neighbors[i], currentPath, solutionsFound);
    }

    // step 5
    currentPath.remove(current);
}

开头为 ：

ArrayList< ArrayList <Cell> > solutionsFound = new ArrayList< ArrayList <Cell> >();
ArrayList <Cell> currentPath= new ArrayList <Cell> ();
findPath(currentMaze, currentMaze.getStartCell(), new ArrayList <Cell>, solutionsFound);

最后，solutionsFound 包含解决方案，currentPath 应为空。

Answer 2

好的，这是。你不仅需要 DFS，还需要一种存储找到的路径的方法。

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

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

我们必须使用以下签名来查找路径

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

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

Rest很简单，我们可以使用以下算法（这是伪代码）

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#
#########################################

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