Решение лабиринта с возвратом

Я пытаюсь решить лабиринт с помощью 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() работать правильно?


scala backtracking maze
person b-m-f    schedule 15.06.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я пока прокомментирую только 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.

Реализация (не проверенная) может выглядеть следующим образом:

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
person Kulu Limpa    schedule 15.06.2015
comment
findStart должен найти вход в лабиринт. Он будет отмечен знаком ?. Так что не должно быть проверки, если поле свободно, я думаю. Но если я отфильтрую так: filter (x => !visited.contains(x) && indexInBound(maze, x)) я все равно попаду в бесконечную рекурсию. - person b-m-f; 16.06.2015
comment
Я только что использовал этот метод для поиска начала: def findStart2(maze: Maze, position: Position): Position = { for (a <- 0 until maze.length) { for (b <- 0 until maze(a).length) { if (maze(a)(b).start) return Position(a, b) } } Position(-1, -1) } Использование вашего ответа для функции getway () помогло мне решить эту проблему. Огромное спасибо - person b-m-f; 16.06.2015