Найти кратчайший путь в лабиринте с рекурсивным алгоритмом

Question

Я сделал небольшой рекурсивный алгоритм, чтобы найти решение лабиринта в следующем формате

###S### 
##___## 
##_#_## 
#__#_## 
#E___## 

Где «#» представляет собой стену, и «_» представляет открытое пространство (свободное передвижение). «S» представляет начальное местоположение, «E» обозначает конечное местоположение.

Мой алгоритм работает нормально, но мне интересно, как его изменить, чтобы работать для кратчайшего пути.

/** 
* findPath() 
* 
* @param location - Point to search 
* @return true when maze solution is found, false otherwise 
*/ 
private boolean findPath(Point location) { 
    // We have reached the end point, and solved the maze 
    if (location.equals(maze.getEndCoords())) { 
     System.out.println("Found path length: " + pathLength); 
     maze.setMazeArray(mazeArray); 
     return true; 
    } 

    ArrayList<Point> possibleMoves = new ArrayList<Point>(); 
    // Move Right 
    possibleMoves.add(new Point(location.x + 1, location.y)); 
    // Down Move 
    possibleMoves.add(new Point(location.x, location.y - 1)); 
    // Move Left 
    possibleMoves.add(new Point(location.x - 1, location.y)); 
    // Move Up 
    possibleMoves.add(new Point(location.x, location.y + 1)); 

    for (Point potentialMove : possibleMoves) { 
     if (spaceIsFree(potentialMove)) { 
      // Move to the free space 
      mazeArray[potentialMove.x][potentialMove.y] = currentPathChar; 
      // Increment path characters as alphabet 
      if (currentPathChar == 'z') 
       currentPathChar = 'a'; 
      else 
       currentPathChar++; 
      // Increment path length 
      pathLength++; 

      // Find the next path to traverse 
      if (findPath(potentialMove)) { 
       return true; 
      } 

      // Backtrack, this route doesn't lead to the end 
      mazeArray[potentialMove.x][potentialMove.y] = Maze.SPACE_CHAR; 
      if (currentPathChar == 'a') 
       currentPathChar = 'z'; 
      else 
       currentPathChar--; 
      // Decrease path length 
      pathLength--; 
     } 
    } 

    // Previous space needs to make another move 
    // We will also return false if the maze cannot be solved. 
    return false; 
} 

В первом квартале я нахожу путь и разбиваю его. Также задан массив char [] [] с указанным на нем способом, который впоследствии будет распечатан в качестве результата.

Это хорошо работает, но мне интересно, какой был бы лучший способ изменить его, чтобы не вырваться после того, как он найдет первый успешный путь, но продолжайте идти, пока не найдет самый короткий путь.

Я попытался сделать что-то подобное, изменив метод findPath() и добавив переменную shortestPath и hasFoundPath. Первая указывающая длина кратчайшего пути, найденного до сих пор, и переменная hasFoundPath, указывающая, найден ли мы какой-либо путь.

// We have reached the end point, and solved the maze 
    if (location.equals(maze.getEndCoords())) { 
     System.out.println("Found path length: " + pathLength); 
     // Is this path shorter than the previous? 
     if (hasFoundPath && pathLength < shortestPathLength) { 
      maze.setMazeArray(mazeArray); 
      shortestPathLength = pathLength; 
     } else if (!hasFoundPath) { 
      hasFoundPath = true; 
      maze.setMazeArray(mazeArray); 
      shortestPathLength = pathLength;    
     } 
     //return true; 
    } 

Но я не был в состоянии получить его, чтобы установить mazeArray правильные значения любого кратчайшего пути может найти.

Любое руководство будет оценено :) Спасибо

метод

spaceIsFree() просто убеждается вверх/влево/вниз/вправо координаты действительны, прежде чем перейти к ним. Таким образом, он гарантирует, что char является «_» или «E», и это не выходит за рамки.

Answer 1

Возможно, ваш код выполнит depth-first search (DFS). Чтобы найти кратчайший путь, вам нужно перейти на breadth-first search (BFS). Это не то, что вы можете сделать, добавив несколько переменных в существующий код. Это потребует переписывания вашего алгоритма.

Один из способов преобразования DFS в BFS - избавиться от рекурсии и переключиться на использование явного стека, чтобы отслеживать, какие узлы вы посещали до сих пор. Каждая итерация цикла поиска, вы (1) выталкиваете узел из стека; (2) проверить, является ли этот узел решением; и (3) выталкивать каждого из своих детей в стек. В псевдокоде, который выглядит следующим образом:

поиск в глубину

stack.push(startNode) 

while not stack.isEmpty: 
    node = stack.pop() 

    if node is solution: 
     return 
    else: 
     stack.pushAll(node.children) 

Если вы переключитесь в стек до очереди это будет неявно стать BFS и BFS естественно найти кратчайший путь (ы).

в ширину первого serarch

queue.add(startNode) 

while not queue.isEmpty: 
    node = queue.remove() 

    if node is solution: 
     return 
    else: 
     queue.addAll(node.children) 

Несколько дополнительных примечаний:

1. Приведенные выше алгоритмы подходят для деревьев: лабиринты, которые не имеют петель.Если ваши лабиринты имеют петли, вам нужно убедиться, что вы не пересматриваете узлы, которые вы уже видели. В этом случае вам нужно добавить логику, чтобы отслеживать все уже посещенные узлы и не добавлять их в стек/очередь второй раз.

2. Как указано, эти алгоритмы найдут целевой узел, но они не помнят путь, который их получил. Добавление этого упражнения для читателя.

Answer 2

Вот решение BFS-поиска, с которым я пришел. Он отмечает начальную точку как «1», а затем отмечает каждый соседний, который может перемещаться как «2», и каждый смежный с двумя, которые могут быть перемещены на «3» и так далее.

Затем он начинается в конце и идет назад, используя декрементирующие значения уровня, которые приводят к кратчайшему пути.

private LinkedList<Point> findShortestPath(Point startLocation) { 
    // This double array keeps track of the "level" of each node. 
    // The level increments, starting at the startLocation to represent the path 
    int[][] levelArray = new int[mazeArray.length][mazeArray[0].length]; 

    // Assign every free space as 0, every wall as -1 
    for (int i=0; i < mazeArray.length; i++) 
     for (int j=0; j< mazeArray[0].length; j++) { 
      if (mazeArray[i][j] == Maze.SPACE_CHAR || mazeArray[i][j] == Maze.END_CHAR) 
       levelArray[i][j] = 0; 
      else 
       levelArray[i][j] = -1; 
     } 

    // Keep track of the traversal in a queue 
    LinkedList<Point> queue = new LinkedList<Point>(); 
    queue.add(startLocation); 

    // Mark starting point as 1 
    levelArray[startLocation.x][startLocation.y] = 1; 

    // Mark every adjacent open node with a numerical level value 
    while (!queue.isEmpty()) { 
     Point point = queue.poll(); 
     // Reached the end 
     if (point.equals(maze.getEndCoords())) 
      break; 

     int level = levelArray[point.x][point.y]; 
     ArrayList<Point> possibleMoves = new ArrayList<Point>(); 
     // Move Up 
     possibleMoves.add(new Point(point.x, point.y + 1)); 
     // Move Left 
     possibleMoves.add(new Point(point.x - 1, point.y)); 
     // Down Move 
     possibleMoves.add(new Point(point.x, point.y - 1)); 
     // Move Right 
     possibleMoves.add(new Point(point.x + 1, point.y)); 

     for (Point potentialMove: possibleMoves) { 
      if (spaceIsValid(potentialMove)) { 
       // Able to move here if it is labeled as 0 
       if (levelArray[potentialMove.x][potentialMove.y] == 0) { 
        queue.add(potentialMove); 
        // Set this adjacent node as level + 1 
        levelArray[potentialMove.x][potentialMove.y] = level + 1; 
       } 
      } 
     } 
    } 
    // Couldn't find solution 
    if (levelArray[maze.getEndCoords().x][maze.getEndCoords().y] == 0) 
     return null; 

    LinkedList<Point> shortestPath = new LinkedList<Point>(); 
    Point pointToAdd = maze.getEndCoords(); 

    while (!pointToAdd.equals(startLocation)) { 
     shortestPath.push(pointToAdd); 
     int level = levelArray[pointToAdd.x][pointToAdd.y]; 
     ArrayList<Point> possibleMoves = new ArrayList<Point>(); 
     // Move Right 
     possibleMoves.add(new Point(pointToAdd.x + 1, pointToAdd.y)); 
     // Down Move 
     possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y - 1)); 
     // Move Left 
     possibleMoves.add(new Point(pointToAdd.x - 1, pointToAdd.y)); 
     // Move Up 
     possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y + 1)); 

     for (Point potentialMove: possibleMoves) { 
      if (spaceIsValid(potentialMove)) { 
       // The shortest level will always be level - 1, from this current node. 
       // Longer paths will have higher levels. 
       if (levelArray[potentialMove.x][potentialMove.y] == level - 1) { 
        pointToAdd = potentialMove; 
        break; 
       } 
      } 
     } 
    } 

    return shortestPath; 
} 

SpaceIsValid() просто гарантирует, что пространство не выходит за пределы.