1

我做了一个简单的迷宫搜索算法，盲目地跑到一个单元格的每个方向来检查是否找到了目标。它可以找到目标，但解决方案仍然很糟糕，因为它不会在找到目标时终止其他递归调用，并且它会绘制它已经走过的所有路径，而不仅仅是一条通往目标的可能路径。我该如何改进呢？

伪代码中的基本算法是这样的：

function searchMaze(start_point, end_point, maze) {

 // If current point is goal I would like to abort other recursive calls
 if(start_point.equals(end_point)) {
   pathFound = true;
   drawPathInArray(); 
    return;
  }
 else {
    // if current point is not inside the array
   if(start_point_not_within_array)
   return
   else {
     // if current point is a wall or a cell that has already been visited
     if(cell_is_wall || cell_is_visited)
       return;
      else {
           // mark cell as possible path
           markCellInPathArray("#");
           setCellVisited();
           searchMaze(left_from_start_point, end_point, maze);
           searchMaze(right_from_start_point, end_point, maze);
           searchMaze(above_start_point, end_point, maze);
           searchMaze(below_start_point, end_point, maze); 
      }
   }
  }
}
4

3 回答 3

1

让函数返回一个布尔值。每当您找到通往目标的路径时，返回 true，否则返回 false。从其中一个递归调用中获得返回值 true 后返回。

所涉及的更改将是适当的返回语句并将您的 4 个递归调用更改为：

if (searchMaze(left_from_start_point, end_point, maze))
  return true;
if (searchMaze(right_from_start_point, end_point, maze))
  return true;
if (searchMaze(above_start_point, end_point, maze))
  return true;
if (searchMaze(below_start_point, end_point, maze))
  return true;

另外，你不应该setCellNotVisited()在最后有一个吗？

注意：我看到你已经有一个pathFound变量（大概是一个类变量）。在这种情况下，可能首选 Marco 的解决方案，但最好将其更改为返回值。

于 2013-04-19T10:21:41.630 回答
1

您应该将标志添加到每个递归调用中：

pathFound = pathFound || searchMaze(left_from_start_point, end_point, maze);
pathFound = pathFound || searchMaze(right_from_start_point, end_point, maze);
pathFound = pathFound || searchMaze(above_start_point, end_point, maze);
pathFound = pathFound || searchMaze(below_start_point, end_point, maze);

如果 pathFound 为真，则忽略调用。

于 2013-04-19T10:22:09.403 回答
1

在 else 块中，如果你为

1) cell_is_wall when wall is visited 
2) set start_point_not_within_arrary when it is not in the array

然后你的代码应该可以工作。您已经拥有的这些条件检查将处理其他递归调用。

于 2013-04-19T10:23:18.647 回答