的Java學習迷宮求解

Question

我一直在工作的一些代碼通過多個死角和1條正確的路徑目標這樣的迷宮指導「機器人」堆疊以記錄機器人第一次到達具有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);} 

} 

的最佳方法，顯示了我的企圖解決它，但是它的作用是使機器人在每個路口

例如這個迷宮直奔，

會離開我與堆棧：EAST，華東，中南，華南，華東，中南，華南，華東，東，南，南，東，EAST，EAST，SOUTH，EAST，SOUTH

Answer 1

確實，這個問題可以通過使用堆棧和對迷宮的詳盡搜索來解決。有更有效的方法，但這個將工作。

知道代碼是如何工作的相當困難，因爲你只給了它的一部分。然而，通常這些徹底的搜索會大量使用遞歸 - 這是堆棧的一個非常常見的用例。我假設你做的是一樣的，雖然我看不到你提供的示例中的代碼。

以下是一些詳盡的「深度優先」搜索示例代碼。此代碼將以所有可能的解決方案結束，而不僅僅是一個。你的代碼中應該有一個像這樣的方法。

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堆棧中的任何位置或您將結束與無限遞歸。

因爲這找到了所有可能的解決方案，那麼您需要找到最短路徑作爲最優路徑。在你的情況下，迷宮似乎只有一條路徑，所以你一旦找到路徑就可以退出。

最後一點：您已經嘗試將設置機器人需要轉向的任務與在迷宮中尋找路徑的任務混合起來。我建議保持這些分開。使用上述算法查找路徑（或更高效的路徑（如*）），然後一旦有路徑遍歷它，以確定機器人的路線列表。