用回溯解决迷宫

Question

我正在尝试使用回溯解决 scala 的迷宫问题。

我的问题是我不断收到 Whosebug 错误。

我已经尝试了很多东西，但我总是以 Whosebug 告终。

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 有两处错误：

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

让我们看一个例子，看看为什么第一点会导致 Whosebug。假设一个迷宫只包含一行三列：

[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。

一个（未经测试的）实现可能如下所示：

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

用回溯解决迷宫

Solving maze with Backtracking

scala

backtracking

maze