用回溯解决迷宫

Question

我想用scala解决迷宫问题，使用回溯。

我的问题是，我一直在得到StackOverflow错误。

我已经尝试了很多事情，但我总是以StackOverflow结束。

findStart（）和getWay（）显示了我用过的两种方法。

我知道可以用Streams做到这一点，并在一次递归中计算所有可能的方式，但我想先用回溯来解决它。

这里是我的代码：

object MazeSolver { 

    case class Cell(free: Boolean, start: Boolean) 

    type Maze = Seq[Seq[Cell]] 

    def main(args: Array[String]) = { 

    val lab = lislab("laby1.rinth") 

    val entrance = findStart(lab, Position(0, 0)) 


    println(getWay(lab, entrance(0), entrance(0), Nil)) 

    } 

    def findStart(lab: Maze, pos: Position): List[Position] = { 
    try { 
     if (lab(pos.column)(pos.row).start) 
     List(pos) 
     else 
     findStart(lab, pos.south) ::: findStart(lab, pos.north) ::: findStart(lab, pos.west) ::: findStart(lab, pos.east) 
    } catch { 
     case _: java.lang.IndexOutOfBoundsException => Nil 
    } 

    } 

    def getWay(maze: Maze, pos: Position, lastPos: Position, way: List[Position]): List[Position] = { 
    try { 
     if (!maze(pos.column)(pos.row).free && !maze(pos.column)(pos.row).start) { 
     Nil 

     } else { 

     if (isExit(pos, maze)) { 
      pos :: way 
     } else { 

      val posList = List(pos.north, pos.south, pos.west, pos.east) 

      posList.foreach { x => 
      val tail = getWay(maze, x, pos, way) 
      if(tail != Nil) tail :: way 
      } 


      Nil 

     } 
     } 
    } catch { case _: java.lang.IndexOutOfBoundsException => way } 

    } 

    def lislab(fn: String): Maze = { 
    try { 
     (for (column <- io.Source.fromFile(fn, "UTF-8").getLines.toList) 
     yield for (c <- column) yield Cell(c == ' ', c == '?')).toIndexedSeq 
    } catch { case _: java.io.FileNotFoundException => Nil } 
    } 

    case class Position(column: Int, row: Int) { 
    override def toString = "(" + column + "." + row + ")" 
    def north = Position(column - 1, row) 
    def south = Position(column + 1, row) 
    def west = Position(column, row - 1) 
    def east = Position(column, row + 1) 
    } 

    def isExit(pos: Position, lab: Maze): Boolean = { 
    val cell = lab(pos.column)(pos.row) 
    cell.free && (pos.column == 0 
     || pos.column == lab.length - 1 
     || pos.row == 0 
     || pos.row == lab(0).length - 1) 

    } 
} 

我在做什么错？我如何使findStart（）和getWay（）函数正常工作？

Answer 1

我现在只想对findStart发表评论。

有两个错误findStart：

1. findStart递归调用上的每个相邻小区。不幸的是，任何邻居的相邻小区都是小区本身。
2. 该函数从不检查您是否可以实际在特定单元格上行走（我假设Cell.free意味着您可以在单元格上行走）。

让我们来看一个例子，看看为什么第一个点导致StackOverflow。假设只有一列三列的迷宫：

[A] <-> [B] <-> [C (start)] 

现在你的算法开始于A。由于A.start == false，它叫findStart(A.east)这是findStart(B)。现在从B.start == false它调用findStart(B.west)和findStart(B.east)。第一个与findStart(A)相同，导致无限递归。

要解决这个问题，你需要跟踪你已经访问过的单元格。达到此目的的一种方法是通过已经访问的职位列表。

关于第2点，您只需通过检查maze(position.column)(position.row).free来检查某个位置是否可行走。

A（未测试）的实现看上去如下：

def findStart2(maze: Maze, position: Position, visited: List[Position]): List[Position] = 
    if (maze(position.column)(position.row).start) 
    List(position) // we reached our goal 
    else { 
    val explorationArea: List[Position] = List(position.north, position.east, position.south, position.west) filter (x => !visited.contains(x) && canWalkOnCell(maze, x)) 
    // filter the adjacent positions that have already been visited or are not walkable 
    explorationArea flatMap { 
     notYetVisitedPosition => 
     findStart2(maze, notYetVisitedPosition, position :: visited) // don't forget to add the current position to the list of already visited positions 
    } 
    } 

private def canWalkOnCell(maze: Maze, position: Position): Boolean = 
    indexInBound(maze, position) && maze(position.column)(position.row).free 

private def indexInBound(maze: Maze, position: Position): Boolean = 
    position.column >= 0 && position.row >= 0 && position.column < maze.size && position.row < maze(position.column).size