递归迷宫解决器在R中

Question

递归迷宫解决器在R中

5

我想在R中解决一个迷宫问题。我创建了一个函数，灵感来自于相应的Python代码：使用Python解决迷宫问题：简单递归和A*搜索。

我有一个迷宫（即矩阵），其中：0 = 空格，1 = 墙（不可到达的单元格），2 = 终点，3 = 已经访问过的。

设置迷宫：

data = c(rep(1, 20),
         c(4,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1),
         c(1,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,2),
         rep(1, 20))

maze = matrix(data, 4, 20, byrow = TRUE)

我的尝试：

search = function(x, y){
  if (maze[x,y] == 2){
    print(paste('i am in point', x, y))
    return(TRUE)
  } else if (maze[x,y]==1){
    print(paste('wall in point', x, y))
    return(FALSE)
  } else if (maze[x,y]==3){
    print(paste('visited point', x, y))
    return(FALSE)
  } 
    
  #set as marked
  print(paste('visited point', x, y))
  maze[x,y] = 3
    
  if((x < length(maze[,1])   & search(x+1, y))
       | (y > 1 & search(x,y-1))
       | (x > 1 & search(x-1,y))
       | (y < length(maze[1,]) & search(x,y+1))){
      return(TRUE)
  }
  
  return(FALSE)
}

search(x= 2, y = 1)

很遗憾，代码出现错误：

[1] "visited point 2 1"  
[1] "wall in point 3 1" 
   
Error in if (maze[x, y] == 2) { : argument is of length zero

我发现else语句存在问题，因为函数会停在一个空单元格上，即0。

- tararuj4

2个回答

2

我认为在R中可能需要一些东西来使其正常工作。首先，Python数组是从0开始的，而R是从1开始索引的。所以你的错误可能是在矩阵中访问了一个零索引元素。另外，在递归调用函数时，你可能需要将maze矩阵作为参数反馈回去。

我根据Python示例（6 x 6矩阵）改编了你的演示。这里的数字“2”表示终点位置。函数search将分别检查是否越界。要查看迷宫是如何解决的，你可以取消注释maze的print语句。

data <- c(
  0, 0, 0, 0, 0, 1,
  1, 1, 0, 0, 0, 1,
  0, 0, 0, 1, 0, 0,
  0, 1, 1, 0, 0, 1,
  0, 1, 0, 0, 1, 0,
  0, 1, 0, 0, 0, 2
)

maze <- matrix(data, 6, 6, byrow = TRUE)

search <- function(maze, x, y) {
  
  # Check if out of bounds
  if (x < 1 | x > length(maze[,1])) return (F)
  if (y < 1 | y > length(maze[1,])) return (F)
  
  # Check if at end, already visited, or hitting a wall
  if (maze[x, y] == 2){
    print(paste('i am at the end: ', x, y))
    return(TRUE)
  } else if (maze[x, y] == 3){
    print(paste('already visited point: ', x, y))
    return(FALSE)
  } else if (maze[x, y] == 1){
    print(paste('wall in point: ', x, y))
    return(FALSE)
  } 
  
  # Set point as visited
  maze[x,y] = 3
  print(paste('visiting point: ', x, y))
  
  # Optional show maze as solved
  # print(maze)
  
  # Check clockwise positions for next move
  if (search(maze, x + 1, y)) return (T)
  if (search(maze, x, y - 1)) return (T)
  if (search(maze, x - 1, y)) return (T)
  if (search(maze, x, y + 1)) return (T)
  
  # No other move found
  return(F)
}

search(maze, x = 1, y = 1)

输出

[1] "visiting point:  1 1"
[1] "wall in point:  2 1"
[1] "visiting point:  1 2"
[1] "wall in point:  2 2"
[1] "already visited point:  1 1"
[1] "visiting point:  1 3"
[1] "visiting point:  2 3"
[1] "visiting point:  3 3"
[1] "wall in point:  4 3"
[1] "visiting point:  3 2"
[1] "wall in point:  4 2"
[1] "visiting point:  3 1"
[1] "visiting point:  4 1"
[1] "visiting point:  5 1"
[1] "visiting point:  6 1"
[1] "already visited point:  5 1"
[1] "wall in point:  6 2"
[1] "already visited point:  4 1"
[1] "wall in point:  5 2"
[1] "already visited point:  3 1"
[1] "wall in point:  4 2"
[1] "wall in point:  2 1"
[1] "already visited point:  3 2"
[1] "wall in point:  2 2"
[1] "already visited point:  3 3"
[1] "already visited point:  2 3"
[1] "wall in point:  3 4"
[1] "wall in point:  2 2"
[1] "already visited point:  1 3"
[1] "visiting point:  2 4"
[1] "wall in point:  3 4"
[1] "already visited point:  2 3"
[1] "visiting point:  1 4"
[1] "already visited point:  2 4"
[1] "already visited point:  1 3"
[1] "visiting point:  1 5"
[1] "visiting point:  2 5"
[1] "visiting point:  3 5"
[1] "visiting point:  4 5"
[1] "wall in point:  5 5"
[1] "visiting point:  4 4"
[1] "visiting point:  5 4"
[1] "visiting point:  6 4"
[1] "visiting point:  6 3"
[1] "wall in point:  6 2"
[1] "visiting point:  5 3"
[1] "already visited point:  6 3"
[1] "wall in point:  5 2"
[1] "wall in point:  4 3"
[1] "already visited point:  5 4"
[1] "already visited point:  6 4"
[1] "already visited point:  5 4"
[1] "visiting point:  6 5"
[1] "already visited point:  6 4"
[1] "wall in point:  5 5"
[1] "i am at the end:  6 6"
[1] TRUE

迷宫解决方案

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    3    3    3    3    3    1
[2,]    1    1    3    3    3    1
[3,]    0    0    0    1    3    0
[4,]    0    1    1    3    3    1
[5,]    0    1    0    3    1    0
[6,]    0    1    0    3    3    2

- Ben

它可以工作，但我还需要返回这个新的迷宫，其中0被替换为3，作为迷宫的路径。在Python中，它自动工作，但在这里我尝试在某个地方放置return(maze)，但没有结果。 - tararuj4

@tararuj4 要查看最终迷宫，您可以在“print(paste('i am at then end: ', x, y))”后添加“print(maze)”-这对您是否起作用？否则可能需要进行一些重构...由于该函数是递归的，因此它只被设置为返回TRUE或FALSE，而不是另一个对象... - Ben

我需要在脚本运行后更新这个迷宫，因为我想打印出迷宫和选择的路径。在Python中，每走一步都会更新迷宫。；/ - tararuj4

另一个快速的方法是在设置结束位置的相同位置添加 maze <<- maze --- 这将把全局环境中 search 函数之外的 maze 赋值为填充有 3 的最终迷宫...这样会有效吗？ - Ben

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kat · Accepted Answer

我走了与 @Ben 不同的路线。

我想看到路线，所以我还添加了两个额外的函数。第一个是 colorPrint，它给矩阵中的“3”添加颜色。第二个是 directedPrint，它将“3”替换为指向行进方向的箭头。

这两个函数中的大部分代码都是用来重新构建矩阵的“外观”。(cat 会打印一个由数字组成的单个字符串的矩阵)

每次找到 '2' 时，这些函数都会在 search 中调用。

library(crayon)
library(tidyverse)

colorPrint <- function(mazish) {
  cols <- ncol(mazish)
  rows <- nrow(mazish)
  mazish <- gsub(", ", "    ",  # add color to values == 3
                 lapply(1:rows, 
                        function(k) {
                          toString(mazish[k, ])
                        }) %>% unlist()
  ) %>% gsub(pattern = "3", replacement = green("3"))
  rowing <- paste0("[", 1:rows, ",]") # rebuild matrix 'appearance' for cat
  coling <- paste0("[,", 1:cols, "]")
  # 4 spaces between each value 
  cat("     ", coling, "\n", paste0(rowing, "    ", mazish, "\n"))
}

directedPrint <- function(mazish, directed) {
  directed <- data.frame(matrix(unlist(directed), ncol = 2, 
                                nrow = length(directed), byrow = T)) %>% 
    setNames(c("x", "y")) %>% 
    mutate(direct = case_when( # determine the direction of travel
      lag(x) < x | lead(x) > x ~ '⬇', # first entry doesn't have any lags
      lag(y) < y | lead(y) > y ~ '⮕',
      lag(x) > x | lead(x) < x ~ '⬆',
      lag(y) > y | lead(y) < y ~ '⬅',
      TRUE ~ '·'))
  cols <- ncol(mazish)
  rows <- nrow(mazish)
  mazishD <- matrix(as.character(mazish), nrow = rows, ncol = cols) # char matrix
  lapply(1:nrow(directed),     # replace 3's with arrows
         function(j) {
           where <- 
             what <- directed[j, "direct"]
           mazishD[directed[j, "x"], directed[j, "y"]] <<- red(what)
         })
  rowing <- paste0("[", 1:rows, ",]") # build the 'appearance' of a matrix
  coling <- paste0("[,", 1:cols, "]")
  lmaz <- gsub(", ", "    ",          # prep for `cat` to appear as a matrix
               lapply(1:rows, 
                      function(k) {
                        toString(mazishD[k, ]) # 1 string per row for cat
                      }) %>% unlist()) %>% # arrows take more than 1 char space
    str_replace_all("    \033", paste0("   \U200A\U2006", "\033")) 
  rowSp <- ifelse(substr(lmaz, 1, 1) == "\033", "   \U200A\U2006", "    ")
  cat("     ", coling, "\n", paste0(rowing, rowSp, lmaz, "\n"))
}

这是我的搜索函数。

search = function(maze, x, y, directions = NULL){
  if(!exists("directions")) {
    directions <- list()
  }
  directions <- append(directions, c(x, y))
  if (x == 0 | y == 0) {       # outside of matrix limits
    return(FALSE)
  } else if (x > nrow(maze) | y > ncol(maze)) { # outside of matrix limits
    return(FALSE)
  } else if (maze[x, y] == 2){
    print(paste('I am in point', x, y))
    colorPrint(maze)                    # print with 3's colored
    directedPrint(maze, directions)     # print solution with arrows
    return(TRUE)
  } else if (maze[x, y] == 1){
    print(paste('wall in point', x, y))
    return(FALSE)
  } else if (maze[x, y] == 3){
    print(paste('visited point', x, y))
    return(FALSE)
  }  
  
  #set as marked
  print(paste('visited point', x, y))
  maze[x, y] <- 3                       # annotate path of travel
  
  if((x < nrow(maze) & search(maze, x + 1, y, directions)) 
     | (y > 1 & search(maze, x, y - 1, directions))
     | (x > 1 & search(maze, x - 1, y, directions))
     | (y < ncol(maze) & search(maze, x, y + 1, directions))) {
    return(TRUE)
  }
  return(FALSE)
}

您将使用与最初描述类似的方式。但是，我必须说，您提供的数据在前20个条目中有障碍物，这意味着迷宫搜索无处可去。

set.seed(253)
dt <- sample(c(
  sample(c(rep(0, 10), c(rep(1, 4))), 49, replace = T), # random 0s, 1s
  2), 50, replace = F) # only [1] 2

maze = matrix(dt, 5, 10, byrow = TRUE)

search(maze, 1, 1)

在控制台中，您将看到每个可能的路线。但是，我只展示了一条通向终点的路线。（我将其制作成图像，以便您可以看到颜色和间距。）

你可以添加收集器，这样你就可以看到循环了多少次，以及每个解决方案需要多少步骤。

这使用外部列表。以下是更新的“search”函数。如果“== 2”，则有一行新行。

search = function(maze, x, y, directions = NULL){
  if(!exists("directions")) {
    directions <- list()
  }
  directions <- append(directions, c(x, y))
  if (x == 0 | y == 0) {       # outside of matrix limits
    return(FALSE)
  } else if (x > nrow(maze) | y > ncol(maze)) { # outside of matrix limits
    return(FALSE)
  } else if (maze[x, y] == 2){
    print(paste('I am in point', x, y))
    colorPrint(maze)                    # print with 3's colored
    directedPrint(maze, directions)     # print solution with arrows
    d[[length(d) + 1]] <<- length(directions) # how many directions were taken?
    
    return(TRUE)
  } else if (maze[x, y] == 1){
    print(paste('wall in point', x, y))
    return(FALSE)
  } else if (maze[x, y] == 3){
    print(paste('visited point', x, y))
    return(FALSE)
  }  
  
  #set as marked
  print(paste('visited point', x, y))
  maze[x, y] <- 3                       # annotate path of travel
  
  if((x < nrow(maze) & search(maze, x + 1, y, directions)) 
     | (y > 1 & search(maze, x, y - 1, directions))
     | (x > 1 & search(maze, x - 1, y, directions))
     | (y < ncol(maze) & search(maze, x, y + 1, directions))) {
    return(TRUE)
  }
  return(FALSE)
}

要使用这个，你需要在全局环境中创建一个列表。

d = list()

dt2 <- matrix(data = c(rep(0, 5), 1, 
                       1, 1, 0, 0, 0, 1, 
                       0, 0, 0, 1, 0, 0, 
                       0, 1, 0, 0, 1, 0,
                       0, 1, 0, 0, 0, 2,
                       rep(0, 5), 1),
              nrow = 6, ncol = 6, byrow = F)
search(dt2, 1, 1)

这返回了43种解决方案，其中最短的序列为20步，最长的为48步。