首页 文章

Java学习迷宫求解器

提问于
浏览 次
2

我一直在研究一些代码来指导一个“机器人”通过一个有多个死角的迷宫和一条正确的目标路径，如下所示：

我已经使用了一个堆栈来记录机器人第一次到达一个有3或4个可能出口的正方形时所面对的方向，如果所有相邻的正方形都已被访问过，则使用pop（）使机器人从第一个方向返回来自（到达方向对面） . 在运行结束时，堆栈包含到达目标路径上的所有方块的方向 . 沿着堆叠的相反方向将机器人从目标返回到起点 . 我正在努力找出如何使用这个堆栈，以便在下一次运行时机器人将采取最佳路径来达到目标 .

我的一些代码：

private int pollRun = 0; // Incremented after each pass
private int explorerMode; // 1 = explore, 0 = backtrack

public void exploreControl(IRobot robot) {

  byte exits = nonwallExits(robot);
  int direction;

  switch (exits) { //passes control to respective method
    case 1: direction = deadEnd(robot);   break;
    case 2: direction = corridor(robot); break;
    case 3: direction = junction(robot); break;
    default: direction = crossroads(robot); break;
  }

  if (exits == 1) {explorerMode = 0;}

  robot.face(direction); 

  pollRun++;

}

public void backtrackControl(IRobot robot) {

  byte exits = nonwallExits(robot);
  int direction = IRobot.CENTRE;

  switch (exits) { //passes control to respective method
    case 1: direction = deadEnd(robot);   break;
    case 2: direction = corridor(robot); break;
    default: direction = junction(robot); break; // do nothing
  }

  if (exits > 2) {
    if (passageExits(robot) > 0){
      exploreControl(robot);
      explorerMode = 1;
      pollRun++;
      return;
    } else {
      robot.setHeading(st.pop());
      robot.face(IRobot.BEHIND);
      pollRun++;
      return;
    }

  }

    robot.face(direction); 

  pollRun++;

}

public void optimal(IRobot robot) {

  byte exits = nonwallExits(robot);
  int direction;
  int heading;

  for(int i = 0; i < st.size(); i++) {
    stNew.push(st.pop());
  }

  if (exits < 3) {

    switch (exits) { //passes control to respective method
      case 1: direction = deadEnd(robot);   break;
      default: direction = corridor(robot); break;
    }

    robot.face(direction);

  } else {
    robot.setHeading(stNew.pop());
  }

}

public void controlRobot(IRobot robot) {

  if ((robot.getRuns() == 0) && (pollRun == 0)) {
    robotData = new RobotData(); //reset the data store
    explorerMode = 1;
  }

  if (robot.getRuns() = 1) {
    optimal(robot);
    return;
  }

  if (robot.getRuns() <= 0 && (nonwallExits(robot) >= 3)
      && (beenbeforeExits(robot) <= 0)) {
    st.push(robot.getHeading());
  }

  if (explorerMode == 1) {
    exploreControl(robot);
  } else {backtrackControl(robot);}

}

最佳方法显示了我尝试解决它，但它所做的只是让机器人在每个交叉点直线前进

比如这个迷宫，

enter image description here

会留下我的堆栈：EAST，EAST，SOUTH，SOUTH，EAST，SOUTH，SOUTH，EAST，EAST，SOUTH，SOUTH，EAST，EAST，EAST，SOUTH，EAST，SOUTH

java stack maze prims-algorithm

1 回答

  • 0

    确实，使用堆栈和穷举的穷举搜索可以解决这个问题 . 有更有效的方法，但这个方法将起作用 .

    很难知道你的代码是如何运行的，因为你只给出了它的一部分 . 然而，通常这些穷举搜索会大量使用递归 - 这是堆栈的一个非常常见的用例 . 我假设你的相同，虽然我在你提供的样本中看不到代码 .

    下面是一些用于详尽“深度优先”搜索的伪代码示例 . 此代码最终将提供所有可能的解决方案，而不仅仅是一个 . 您应该在代码中使用类似于此的方法 .

    void findPath(Stack currentPath) {
    if (currentPath.peek() == goal) {
        solutions.add(currentPath);
    } else {
        for (Position next: currentPath.openPositions()) {
            currentPath.push(next);
            findPath(currentPath);
            currentPath.pop();
        }
    }
}

    'openPositions'方法需要通过查看当前路径显式地停止任何加倍 - 换句话说，它不应该返回已经在currentPath堆栈中的任何位置，否则您将最终得到无限递归 .

    因为这会找到所有可能的解决方案，然后您需要找到最短长度的解决方案作为最佳路径 . 在你的情况下，似乎迷宫只有一条路径，所以你可以在找到路径后立即退出 .

    最后一点：您已经尝试将设置机器人需要转向的任务与完成迷宫中的路径任务相结合 . 我建议保持这些分开 . 使用上面的算法查找路径（或更有效的路径，如*），然后一旦有路径遍历它，就可以确定机器人的路线列表 .

    回复于

相关问题