1. 首页
  2. 问答
  3. 调试/修复BFS算法

调试/修复BFS算法

2011-05-05 80 views
1

我正在解决这个BFS作业问题，我相信我遵循的逻辑是正确的，但是我陷入了一个执行错误，我无法查明。我正在寻找帮助调试此解决方案，而不是提出一个新的解决方案。调试/修复BFS算法

问题陈述：

甲孩子具有他远程控制两个机器人，无论机器人是上NxN的棋盘和应放置在棋盘的位置A和B。

两个机器人都受到遥控器的同时影响，同一命令会影响两个机器人的状态。

遥控器只能让两台机器人一次旋转90度或顺时针旋转90度，或者让两台机器人向前移动。

示例： 最左侧的图像显示初始设置。向右的箭头是一个面向东方的机器人，而向上的箭头是一个面向北方的机器人。位置A和B是机器人的命运。

中心图像显示两个机器人向前移动一步的结果。

右图显示了使机器人逆时针旋转的结果。

Figure 1

的孩子想要计算必要采取从它们的初始位置的机器人自己的命运运动的最小数目。

如果命令机器人跑过墙壁，它将保持在同一地点。

如果两个机器人被命令移动到同一个位置，它们将保持原位。

图2显示了这种特殊情况。

enter image description here

两个机器人应该有不同的命运同时到达。

输入： 输入由各种测试情况下，第一线与该inputMatrix（棋盘）的大小为N的整数开始，用2 < = N < = 25。

以下N行描述了棋盘，每个字符都有N个字符。

A'。'表示空位。

N，E，S或O（西班牙语为Oeste = West）表示机器人的原始位置和方向。

D表示棋盘上机器人的命运，'*'表示障碍物。

输入以N = 0的情况结束。

输入。TXT

5 
D.... 
N...S 
..... 
*...* 
....D 
5 
..... 
S..S. 
..... 
..... 
D..D. 
3 
SN. 
*** 
.DD 
0

正确输出input.txt中：

8 
3 
-1

input2.txt：（？）

5 
..... 
..D.S 
.D... 
..... 
..N.. 
6 
...... 
..S... 
...... 
.ED... 
...... 
.D.... 
11 
....E...... 
....D...... 
........... 
..S...D.... 
........... 
........... 
........... 
........... 
........... 
........... 
........... 
13 
............. 
............. 
............. 
............. 
.....N....... 
............. 
.........D... 
..D.......... 
............. 
...E......... 
............. 
............. 
............. 
25 
...*.......*.*........... 
........*..D...*.**....*. 
*..*.*.........*..*..*..D 
...*.**.*........*...*... 
......**..*..***.***...** 
.............*........... 
....*...***.....*.**..... 
......**.......**.*.*...* 
.........*..*...*.*...... 
....**.*.*....**.*.*.*.*. 
.......*............**... 
..........*.*.....*...... 
...........**....*.**.... 
.....E.*.*..........**.*. 
.........*.*.*.*..*..*... 
*........**...*.......... 
................***..*... 
........*....*....*...*.. 
......*...*.*...*.....**. 
...*..........*.**....... 
.**............*.*..*.*.. 
........*........*...*... 
*......*..........*...... 
*...*......N*......*..*.* 
. .....*..*.*..*...*...... 
0

“正确” 输出input2.txt：

-1 
-1 
9 
-1 
46

我的解决方案：

个 
import java.io.BufferedReader; 
import java.io.File; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.Queue; 




class Position { 

    int i; 
    int j; 
    char orientation; 

     Position() { 

    } 


    void setIJ(int i, int j){ 
     this.i=i; 
     this.j=j; 
    } 

    void setOrientation(char c){ 

     orientation = c; 
    } 

    public boolean equals(Object o){ 

     if(o instanceof Position){ 

      Position p = (Position)o; 
      if((p.i==this.i)&&(p.j==this.j)&&(p.orientation==this.orientation)) 
      { 
       return true; 
      } 
       else return false; 
      } 

      return false; 
    } 

} //end class Position 


class TransitionState { 

    Position positionA; 
    Position positionB; 

    int counter; 

    public boolean equals (Object o){ 

     if (o instanceof TransitionState){ 

      TransitionState transitionState= (TransitionState)o; 

      if ((this.positionA.equals(transitionState.positionA)) 
        &&(this.positionB.equals(transitionState.positionB))) 
      { 
       return true; 
      } 
     } 
    return false; 

    } 

} 


public class Robots { 

static Position moveForward(Position oldPosition, int matrixSize, char orientation, char [][] inputMatrix){ 

    // add possible new Position 
    Position newPosition= new Position(); 

    //first return oldPosition in border positions in which the robot shouldn't move 

    if ((orientation=='O')&&(oldPosition.j==0)) 
      return oldPosition; 

    if ((orientation=='E')&&(oldPosition.j==(matrixSize-1))) 
      return oldPosition; 

    if ((orientation=='N')&&(oldPosition.i==0)) 
      return oldPosition; 

    if ((orientation=='S')&&(oldPosition.i==(matrixSize-1))) 
      return oldPosition; 


    if ((orientation=='O')) 
     newPosition.setIJ(oldPosition.i, oldPosition.j-1); 
    if ((orientation=='E')) 
     newPosition.setIJ(oldPosition.i, oldPosition.j+1); 
    if ((orientation=='S')) 
     newPosition.setIJ(oldPosition.i-1, oldPosition.j); 
    if ((orientation=='N')) 
     newPosition.setIJ(oldPosition.i+1, oldPosition.j); 


    //return oldPosition for positions in which the robot is blocked by * 
    if (inputMatrix[newPosition.i][newPosition.j]=='*'){ 
     return oldPosition; 
    } 

    return newPosition; // if it got here, all ok 

} 


static char turnCounter (char orientation){ 

    if(orientation=='N') 
     return 'O'; 
    if(orientation=='O') 
     return 'S'; 
    if (orientation=='S') 
     return 'E'; 
    else 
     return 'N'; 

} 

static char turnClock(char orientation){ 

     if(orientation=='N') 
     return 'E'; 
    if(orientation=='E') 
     return 'S'; 
     if (orientation=='S') 
     return 'O'; 
    else 
     return 'N'; 

} 

static Position[] robotInitialPositions(char [][]inputMatrix){ 

    Position [] helperArray = new Position[2]; 

    int aux=0; 

    for (int i=0; i<(inputMatrix[0].length); i++) 
     for (int j=0; j<(inputMatrix[0].length); j++) 
     { 
      if((inputMatrix[i][j]=='N')||(inputMatrix[i][j]=='S')||(inputMatrix[i][j]=='O')||(inputMatrix[i][j]=='E')) 
      { 
        helperArray[aux]= new Position(); 
        helperArray[aux].setIJ(i, j); 
        if (inputMatrix[i][j]=='N'){helperArray[aux].orientation='N'; } 
        if (inputMatrix[i][j]=='S'){helperArray[aux].orientation='S'; } 
        if (inputMatrix[i][j]=='E'){helperArray[aux].orientation='E'; } 
        if (inputMatrix[i][j]=='O'){helperArray[aux].orientation='O'; } 
        aux= aux+1; 
      } 

     } 

    return helperArray; 

} 


static Position[] getDestinies(char [][]inputMatrix){ 

    Position [] helperArray = new Position[2]; 

    int aux=0; 

    for (int i=0; i<(inputMatrix[0].length); i++) 
     for (int j=0; j<(inputMatrix[0].length); j++) 
     { 
      if((inputMatrix[i][j]=='D')) 
      { 
        helperArray[aux]= new Position(); 
        helperArray[aux].i=i; helperArray[aux].j=j; 
        helperArray[aux].orientation='D'; 
        aux=aux+1; 

      } 

     } 

    return helperArray; 

} 



static boolean [][]getUnvisitedMatrix(int matrixLength){ 


    boolean[][] unvisitedMatrix = new boolean [matrixLength][matrixLength]; 

    for (int i=0; i<matrixLength;i++) 
     for (int j=0; j<matrixLength; j++) 
      unvisitedMatrix[i][j]=false; 

    return unvisitedMatrix; 

} 





static Position[]getNewRobotPositions (Position oldR1Pos,Position oldR2Pos, String movement, char [][]inputMatrix){ 

    Position[]newPositions = new Position[2]; 

    Position newR1Pos = new Position(); 
     Position newR2Pos = new Position(); 

    if(movement.equals("counter")){ 

     if (oldR1Pos.orientation=='N'){ 

      newR1Pos.orientation='O'; 

     } 

     if (oldR1Pos.orientation=='S'){ 

      newR1Pos.orientation='E'; 

     } 

     if (oldR1Pos.orientation=='E'){ 

      newR1Pos.orientation='N'; 

     } 

     if (oldR1Pos.orientation=='O'){ 

      newR1Pos.orientation='S'; 
     } 


     if (oldR2Pos.orientation=='N'){ 

      newR2Pos.orientation='O'; 
     } 

     if (oldR2Pos.orientation=='S'){ 

      newR2Pos.orientation='E'; 

     } 

     if (oldR2Pos.orientation=='E'){ 

      newR2Pos.orientation='N'; 

     } 

     if (oldR2Pos.orientation=='O'){ 

      newR2Pos.orientation='S'; 

     } 

     newR1Pos.i=oldR1Pos.i; 
     newR1Pos.j=oldR1Pos.j; 

     newR2Pos.i=oldR2Pos.i; 
     newR2Pos.j=oldR2Pos.j; 

     newPositions[0]=newR1Pos; 
     newPositions[1]=newR2Pos; 

//  System.out.println("MOVED COUNTERCLOCKWISE"); 
//  System.out.println("previous Robot 1 position was "+oldR1Pos.i + ","+oldR1Pos.j + " orientation was " + oldR1Pos.orientation + 
//  " new Robot 1 position is " + newR1Pos.i + "," + newR1Pos.j+ " orientation is "+newR1Pos.orientation); 
// 
//  System.out.println("previous Robot 2 position was "+oldR2Pos.i + ","+oldR2Pos.j + " orientation was " + oldR2Pos.orientation + 
//  " new Robot 2 position is " + newR2Pos.i + "," + newR2Pos.j+ " orientation is "+newR2Pos.orientation); 

     return newPositions; 


    } 

    if(movement.equals("clock")){ 

     newR1Pos.i = oldR1Pos.i; 
     newR1Pos.j = oldR1Pos.j; 

     newR2Pos.i = oldR2Pos.i; 
     newR2Pos.j = oldR2Pos.j; 


     if (oldR1Pos.orientation=='N'){ 

      newR1Pos.orientation= 'E'; 
     } 

     if (oldR1Pos.orientation=='S'){ 

      newR1Pos.orientation= 'O'; 
     } 

     if (oldR1Pos.orientation=='E'){ 

      newR1Pos.orientation= 'S'; 
     } 

     if (oldR1Pos.orientation=='O'){ 

      newR1Pos.orientation= 'N'; 

     } 



     if (oldR2Pos.orientation=='N'){ 

      newR2Pos.orientation= 'E'; 
     } 

     if (oldR2Pos.orientation=='S'){ 

      newR2Pos.orientation= 'O'; 

     } 

     if (oldR2Pos.orientation=='E'){ 

      newR2Pos.orientation= 'O'; 

     } 

     if (oldR2Pos.orientation=='O'){ 

      newR2Pos.orientation= 'N'; 

     } 
//  System.out.println("MOVED CLOCKWISE"); 
//  System.out.println("previous Robot 1 position was "+oldR1Pos.i + ","+oldR1Pos.j + " orientation was " + oldR1Pos.orientation + 
//  " new Robot 1 position is " + newR1Pos.i + "," + newR1Pos.j+ " orientation is "+newR1Pos.orientation); 
//
//  System.out.println("previous Robot 2 position was "+oldR2Pos.i + ","+oldR2Pos.j + " orientation was " + oldR2Pos.orientation + 
//  " new Robot 2 position is " + newR2Pos.i + "," + newR2Pos.j+ " orientation is "+newR2Pos.orientation); 


     newPositions[0]=newR1Pos; 
     newPositions[1]=newR2Pos; 

     return newPositions; 

    } 

    if(movement.equals("forward")){ 

     //default case, if conditions not satisfied 
     newR1Pos.i=oldR1Pos.i; 
     newR1Pos.j=oldR1Pos.j; 
      newR1Pos.orientation = oldR1Pos.orientation; 

     newR2Pos.i=oldR2Pos.i; 
     newR2Pos.j=oldR2Pos.j; 
     newR2Pos.orientation = oldR2Pos.orientation; 


     if(oldR1Pos.orientation=='N'){ 

      if(oldR1Pos.i-1>=0){ //doesn't exceed the upper border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i-1][oldR1Pos.j]!='*'){ 
         newR1Pos.i=oldR1Pos.i-1; 
         newR1Pos.j=oldR1Pos.j; 
         newR1Pos.orientation = oldR1Pos.orientation; 
       } 

      } 

     } 

     if(oldR1Pos.orientation=='S'){ 

      if(oldR1Pos.i+1<inputMatrix.length){ //doesn't exceed the lower border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i+1][oldR1Pos.j]!='*'){ 
         newR1Pos.i=oldR1Pos.i+1; 
         newR1Pos.j=oldR1Pos.j; 
         newR1Pos.orientation = oldR1Pos.orientation; 

       } 
      } 
     } 

     if(oldR1Pos.orientation=='E'){ 

      if(oldR1Pos.j+1<inputMatrix.length){ //doesn't exceed the right border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i][oldR1Pos.j+1]!='*'){ 
         newR1Pos.i=oldR1Pos.i; 
         newR1Pos.j=oldR1Pos.j+1; 
         newR1Pos.orientation = oldR1Pos.orientation; 
       } 
      } 

     } 

     if(oldR1Pos.orientation=='O'){ 

      if(oldR1Pos.j-1>=0){ //doesn't exceed the left border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR1Pos.i][oldR1Pos.j-1]!='*'){ 
         newR1Pos.i=oldR1Pos.i; 
         newR1Pos.j=oldR1Pos.j-1; 
         newR1Pos.orientation = oldR1Pos.orientation; 
       } 

      } 

     } 

     //same for robot 2 

     if(oldR2Pos.orientation=='N'){ 

      if(oldR2Pos.i-1>=0){ //doesn't exceed the upper border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i-1][oldR2Pos.j]!='*'){ 
         newR2Pos.i=oldR2Pos.i-1; 
         newR2Pos.j=oldR2Pos.j; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 

      } 

     } 

     if(oldR2Pos.orientation=='S'){ 

      if(oldR2Pos.i+1<inputMatrix.length){ //doesn't exceed the lower border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i+1][oldR2Pos.j]!='*'){ 
         newR2Pos.i=oldR2Pos.i+1; 
         newR2Pos.j=oldR2Pos.j; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 
      } 
     } 

     if(oldR2Pos.orientation=='E'){ 

      if(oldR2Pos.j+1<inputMatrix.length){ //doesn't exceed the right border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i][oldR2Pos.j+1]!='*'){ 
         newR2Pos.i=oldR2Pos.i; 
         newR2Pos.j=oldR2Pos.j+1; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 
      } 

     } 

     if(oldR2Pos.orientation=='O'){ 

      if(oldR2Pos.j-1>=0){ //doesn't exceed the left border 

       //doesn't collide with '*' 
       if (inputMatrix[oldR2Pos.i][oldR2Pos.j-1]!='*'){ 
         newR2Pos.i=oldR2Pos.i; 
         newR2Pos.j=oldR2Pos.j-1; 
         newR2Pos.orientation=oldR2Pos.orientation; 
       } 

      } 

     } 


     //if robots collide in new positions, revert to their original positions 
     if ((newR1Pos.i==newR2Pos.i) && (newR1Pos.j==newR2Pos.j)){ 

      //revert robot 1 position 
      newR1Pos.i=oldR1Pos.i; 
      newR1Pos.j=oldR1Pos.j; 
      newR1Pos.orientation = oldR1Pos.orientation; 

      //revert robot 2 position 
      newR2Pos.i=oldR2Pos.i; 
      newR2Pos.j=oldR2Pos.j; 
      newR2Pos.orientation = oldR2Pos.orientation; 
     } 

     newPositions[0] = newR1Pos; 
     newPositions[1] = newR2Pos; 

//  System.out.println("MOVED FORWARD"); 
//   System.out.println("previous Robot 1 position was "+oldR1Pos.i + ","+oldR1Pos.j + " orientation was " + oldR1Pos.orientation + 
//  " new Robot 1 position is " + newR1Pos.i + "," + newR1Pos.j+ " orientation is "+newR1Pos.orientation); 
// 
//  System.out.println("previous Robot 2 position was "+oldR2Pos.i + ","+oldR2Pos.j + " orientation was " + oldR2Pos.orientation + 
//  " new Robot 2 position is " + newR2Pos.i + "," + newR2Pos.j+ " orientation is "+newR2Pos.orientation); 

    } //end movement.equals("forward") 


    return newPositions; 

} 


//1 procedure BFS(Graph,source): 
//2  create a queue Q 
//3  enqueue source onto Q 
//4  mark source 
//5  while Q is not empty: 
//6   dequeue an item from Q into v 
//7   for each edge e incident on v in Graph: 
//8    let w be the other end of e 
//9    if w is not marked: 
//10     mark w 
//11     enqueue w onto Q 



static void BFS (char [][] inputMatrix){ 

    ArrayList<TransitionState> transitionStatesArray = new ArrayList<TransitionState>(); 

    int moveCounter=0; //turns and forward movements add here 

    int tempMoveCounterRobot1=0; int tempMoveCounterRobot2=0; 
    int maxMoveCounter=0; 

    PositionsAndCounter positionsAndCounter= new PositionsAndCounter(); 

    Queue <PositionsAndCounter>queue = new LinkedList<PositionsAndCounter>(); 

    Position robotInitial[] = robotInitialPositions(inputMatrix); //get source 
    positionsAndCounter.positionPair=robotInitial; //used to encapsulate the positions with a counter to output 
    positionsAndCounter.counter=0;//first initialize to 0 

    Position destinies[] = getDestinies(inputMatrix); //get destinies 


    TransitionState firstTransitionState = new TransitionState(); 
    firstTransitionState.positionA=robotInitial[0]; 
    firstTransitionState.positionB=robotInitial[1]; 

    transitionStatesArray.add(firstTransitionState); 

    //mark transition used , if the transition is new, it should be queued 

    queue.add(positionsAndCounter); 

    String [] movement = {"forward", "counter", "clock"}; 
    //possible movements inside inputMatrix 


    outer: while (!queue.isEmpty()){ //while queue is not empty 

     PositionsAndCounter v= queue.poll(); //dequeue an item from Q into V 

     for(int k = 0; k<3; k++){ //for each edge e incident on v in Graph: 

      Position[] newRobotPositions = getNewRobotPositions(v.positionPair[0], v.positionPair[1], movement[k], inputMatrix); 

      TransitionState newTransitionState = new TransitionState(); 
      newTransitionState.positionA=newRobotPositions[0]; 
      newTransitionState.positionB=newRobotPositions[1]; 

      if(!transitionStatesArray.contains(newTransitionState)){ //if the transition state is new add and enqueue new robot positions 

       transitionStatesArray.add(newTransitionState); 

        //if transition is new then queue 
       PositionsAndCounter newPositionsAndCounter = new PositionsAndCounter(); 
       newPositionsAndCounter.positionPair=newRobotPositions; 
       newPositionsAndCounter.counter = v.counter +1; 


        queue.add(newPositionsAndCounter); 


      } 


      inputMatrix[v.positionPair[0].i][v.positionPair[1].j]='.'; 
      inputMatrix[v.positionPair[1].i][v.positionPair[1].j]='.'; 

      //inputMatrix[v[0].i][v[0].j]='.'; // mark old position of robot 1 with . 
      //inputMatrix[v[1].i][v[1].j]='.'; // mark old position of robot 2 with . 

      //update new robot positions 
      inputMatrix[newRobotPositions[0].i][newRobotPositions[0].j]= newRobotPositions[0].orientation; 
      inputMatrix[newRobotPositions[1].i][newRobotPositions[1].j]= newRobotPositions[1].orientation; 


      //check if solution has been found 
        if 
        (
        ((destinies[0].i==newRobotPositions[0].i)&&(destinies[0].j==newRobotPositions[0].j) //robot in 0 arrived to destiny 
        || (destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j))// in 0 or 1 
         &&                          //and 
        ((destinies[0].i==newRobotPositions[1].i)&&(destinies[0].j==newRobotPositions[1].j) //robot in 1 arrived to destiny 
        || (destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j))//in 0 or 1 

        ) //end if 
        { 

         System.out.println("robots arrived at destinies"); 
         System.out.println("robot 1, starting at " + robotInitial[0].i + "," + robotInitial[0].j 
           + " is in " + newRobotPositions[0].i + ","+ newRobotPositions[0].j); 
         System.out.println("robot 2, starting at " + robotInitial[1].i + "," + robotInitial[1].j 
           + " is in " + newRobotPositions[1].i + ","+ newRobotPositions[1].j); 

        System.out.println("movements: " + (v.counter)); 

        return; 
        //break outer; 

        } 


       } 

      } 

      System.out.println("robots can never arrive at their destinies"); 
      System.out.println(-1); 


    } 


static void printInputMatrix(char [][] inputMatrix){ 


    for (int i=0; i<inputMatrix[0].length;i++) 
     for(int j=0; j<inputMatrix[0].length;j++) 
     { 

      System.out.print(" "+inputMatrix[i][j]+" "); 
      if(j==inputMatrix[0].length-1){System.out.println("");} 

     } 


} 





    public static void main(String[] args) throws IOException { 

//  System.out.println("Test transition checker"); 
//  Position p1 = new Position(); 
//  p1.i=1; 
//  p1.j=1; 
//  p1.orientation='N'; 
//  Position p2 = new Position(); 
//  p2.i=1; 
//  p2.j=2; 
//  p2.orientation='N'; 
//  Position p3 = new Position(); 
//  p3.i=1; 
//  p3.j=1; 
//  p3.orientation='N'; 
//  Position p4 = new Position(); 
//  p4.i=1; 
//  p4.j=1; 
//  p4.orientation='N'; 
// 
//  TransitionState transitionChecker1 = new TransitionState(); 
//  transitionChecker1.positionA=p1; 
//  transitionChecker1.positionB=p2; 
// 
//  TransitionState transitionChecker2 = new TransitionState(); 
//  transitionChecker2.positionA=p1; 
//  transitionChecker2.positionB=p2; 
// 
// 
//  ArrayList<TransitionState> arrayTransitions = new ArrayList<TransitionState>(); 
//  arrayTransitions.add(transitionChecker1); 
//  System.out.println("Test contains? " + arrayTransitions.contains(transitionChecker2)); 




     BufferedReader br = new BufferedReader(new FileReader(new File("input.txt"))); 

     char [][] inputMatrix; 

     String line; 
     char [] lineAsCharArray; 
     int matrixSize; 

     while(true){ 

      line = br.readLine(); 
      matrixSize=Integer.parseInt(line); 

      inputMatrix = new char [matrixSize][matrixSize]; 

      if (matrixSize==0){ // end outer looping 
       break; 
      } 

      else { //begin inner looping 

       for (int i=0; i<matrixSize; i++){ 

        line = br.readLine(); 
        inputMatrix[i] =line.toCharArray(); 

       } 

       //matrix loaded 

       BFS(inputMatrix); 

      } 


     } 

    } 

} 

class PositionsAndCounter { 

    Position[] positionPair; 
    int counter; 

    PositionsAndCounter() { 
     positionPair = new Position[2]; 
     counter=0; 

    } 
}

问题： 1）在第一input.txt的文件时，它发现9个动作来找到）所述第一过程的溶液（当他们应为8和6找到的解决方案第二课程（当它应该是3）时，虽然它为最后（不可能）的课程配置正确打印-1。

2）在第二input.txt的文件，教授说，它应该打印在第一场和-1，虽然我的节目发现了第二种情况下plaussible解决方案和一个奇怪的一个第一（这是我认为一个更有经验的调试人员可以提供帮助的地方，我无法追踪第一个案例中被驱逐的命运输出的原因）。我的教授提出的输出是否正确？我的算法也陷入了应该打印46的情况。

来源

2011-05-05 andandandand

回答

4

的2个粗心的复制和粘贴问题的原因的代码不工作， 1，在顺时针旋转部分：

 if (oldR2Pos.orientation == 'E') { 

      newR2Pos.orientation = 'O'; 

     }

这是错误的...它应该是一个直接复制和粘贴的以上区块

 if (oldR2Pos.orientation == 'E') { 

      newR2Pos.orientation = 'S'; 
     }

然而你错过了它。

另一个问题实际上是在结束条件测试块

 //check if solution has been found 
      if 
      (
      ((destinies[0].i==newRobotPositions[0].i)&&(destinies[0].j==newRobotPositions[0].j) //robot in 0 arrived to destiny 
      || (destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j))// in 0 or 1 
       &&                          //and 
      ((destinies[0].i==newRobotPositions[1].i)&&(destinies[0].j==newRobotPositions[1].j) //robot in 1 arrived to destiny 
      || **(destinies[1].i==newRobotPositions[0].i)&&(destinies[1].j==newRobotPositions[0].j)**)//in 0 or 1 

      ) //end if

最后一部分（代码高亮）应

(destinies[1].i==newRobotPositions[1].i)&&(destinies[1].j==newRobotPositions[1].j)

这显然是一个复制粘贴，但忘了改错误。其中的逻辑是有点难以理解，但工程，

（A在Y X或B）和（在Y A或B中的X）

虽然是相同的（逻辑上不完全（A和B不能占据相同的位置），如果你使用

（Y中的A和Y中的A）或（Y中的A和B中的A）

除了上面提到的致命错误之外，您的程序还有一些其他问题需要解决。看起来您是一位正在考虑计算机科学的大学生，请阅读给定的源代码befo重新编码：根本没有使用TransistionState类，但是你创建了自己的PositionsAndCounter，翻转逻辑被执行两次，如果你没有重写转向代码，并使用给定的代码，你不会犯第一个问题....如果我是你的教授，那么我可能会让你失望。在敲击键盘之前，先好好规划好你的解决方案，并确保你的代码清晰可读，如同计划中文版，如果你盯着你的源代码5分钟，并且不知道代码块是什么，可能你没有正确的结构。

下面的列表为您的问题为例的解决方案：

import java.awt.Point; 
import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.Map; 


public class DualRobot { 

    public enum Orientation{ 
     E(1, 0), S(0, 1), O(-1, 0), N(0, -1); 

     public final int dx, dy; 
     private Orientation(int dx, int dy){ 
      this.dx = dx; 
      this.dy = dy; 
     } 

     public Orientation left(){ 
      return Orientation.values()[(this.ordinal() + 3) % 4]; 
     } 

     public Orientation right(){ 
      return Orientation.values()[(this.ordinal() + 1) % 4]; 
     } 

     public static Orientation valueOf(char c){ 
      for(Orientation o : Orientation.values()){ 
       if(o.toString().equalsIgnoreCase("" + c)) return o; 
      } 
      return null; 
     } 

    } 

    public enum Action {FORWARD, COUNTER_CLOCKWISE, CLOCKWISE}; // F: forward, L: Counter clockwise, R: clockwise 

    private static class Robot{ 
     Point position; 
     Orientation orientation; 

     public Robot(Robot r){ 
      this.position = new Point(r.position); 
      this.orientation = r.orientation; 
     } 
     public Robot(int x, int y, Orientation orientation){ 
      this.position = new Point(x, y); 
      this.orientation = orientation; 
     } 

     public void move(Action action, char[][] map){ 
      switch (action) { 
      case FORWARD: 
       Point nextPosition = new Point(position); 
       nextPosition.translate(orientation.dx, orientation.dy); 
       if(isValidPosition(nextPosition, map)) position = nextPosition; 
       break; 
      case COUNTER_CLOCKWISE: 
       this.orientation = this.orientation.left(); 
       break; 
      case CLOCKWISE: 
       this.orientation = this.orientation.right(); 
       break; 
      } 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if (obj instanceof Robot) { 
       Robot r = (Robot) obj; 
       return r.position.equals(this.position) && r.orientation == this.orientation; 
      } 
      return super.equals(obj); 
     } 

     @Override 
     public int hashCode() { 
      return orientation.ordinal() + position.x * 10 + position.y * 1000; 
     } 

     private boolean isValidPosition(Point p, char[][] map){ 
      return p.x >= 0 && p.x < map[0].length 
       && p.y >= 0 && p.y < map.length 
       && map[p.y][p.x] != '*'; 
     } 
    } 

    private static class State{ 
     private Robot a, b; 
     private int counter; 

     public State(Robot a, Robot b, int counter) { 
      this.a = new Robot(a); 
      this.b = new Robot(b); 
      this.counter = counter; 
     } 

     public List<State> nextStates(char[][] map){ 
      List<State> states = new ArrayList<State>(); 
      for(Action action : Action.values()){ 
       State s = new State(this.a, this.b, this.counter + 1); 
       s.a.move(action, map); 
       s.b.move(action, map); 
       if(!s.a.position.equals(s.b.position)){ // Test for collision 
        states.add(s); 
       } 
      } 
      return states; 
     } 

     @Override 
     public boolean equals(Object obj) { 
      if (obj instanceof State) { 
       State state = (State) obj; // Consider the state to be the same if the 2 robots are at identical location and orientation 
       return (this.a.equals(state.a) && this.b.equals(state.b)) 
        || (this.a.equals(state.b) && this.b.equals(state.a)); 
      } 
      return super.equals(obj); 
     } 

     @Override 
     public int hashCode() { 
      // The quality of this hashCode can affect the program's speed 
      // Multiply is transitive, so if you swap a and b, the hashcode is the same 
      return a.hashCode() * b.hashCode(); 
     } 

    } 

    public static void main(String[] args) throws IOException { 
     BufferedReader input = new BufferedReader(new FileReader("input.txt")); 
     int size; 

     while((size = Integer.parseInt(input.readLine())) > 0){ 
      // Load the data; 
      char[][] map = new char[size][size]; 
      for (int i = 0; i < size; i++) { 
       map[i] = input.readLine().toCharArray(); 
      } 

      // Construct initial state 
      List<Robot> robots = new ArrayList<Robot>(); 
      List<Point> destinations = new ArrayList<Point>(); 
      for(int i = 0; i < size; i ++){ 
       for(int j = 0; j < size; j ++){ 
        Orientation orientation = Orientation.valueOf(map[i][j]); 
        if(orientation != null){ 
         robots.add(new Robot(j, i, orientation)); 
        }else if(map[i][j] == 'D'){ 
         destinations.add(new Point(j, i)); 
        } 
       } 
      } 

      System.out.println(BFSSearch(map, new State(robots.get(0), robots.get(1), 0), destinations)); 

     } 

    } 

    private static int BFSSearch(char[][] map, State initialState, List<Point> destinations) throws IOException{ 
     List<State> queue = new LinkedList<State>(); // Array list is slightly more efficient 
     queue.add(initialState); // Initial state 
     Map<State, Boolean> testedStates = new HashMap<State, Boolean>(); 
     while(queue.size() > 0){ 
      State currentState = queue.remove(0); 
      if(testedStates.containsKey(currentState)) continue; 

      // Testing for end condition 
      if((currentState.a.position.equals(destinations.get(0)) && currentState.b.position.equals(destinations.get(1))) 
      || (currentState.a.position.equals(destinations.get(1)) && currentState.b.position.equals(destinations.get(0)))){ 
       return currentState.counter; 
      } 
      testedStates.put(currentState, true); 
      queue.addAll(currentState.nextStates(map)); 
     } 
     return -1; 
    } 
}

该程序吐在10秒左右的最终答案。

主要区别在于我使用了散列表来存储测试状态以提高速度，因此散列函数的质量会对速度产生影响。

推荐阅读：散列表，DRY原理。

来源

2011-05-05 10:46:09 user658991

+0

感谢您花时间查看代码。这段代码全由我编写。在我的大学里（我在委内瑞拉中央大学学习）我们从来没有得到部分项目建设，我很惊讶地听到这是其他方法。您指出的两个遗漏是使代码在所有情况下正确运行，除了第二个输入文件的最后一个，我的算法被卡住了。我想知道那里发生了什么。 – andandandand 2011-05-05 14:03:38

+0

你的程序没有挂起，实际上，它只需要很长时间才能运行。 1.具有约70％空间的25×25矩阵将给出单个机器人25 * 25 * 0.7 * 4 = 1750种不同状态，并且2个机器人的组合将大致为1750 * 1750 = 300万种不同状态。 – user658991 2011-05-06 02:37:15

+0

2.查看搜索过去状态的算法，您基本上遍历所有过去的状态，这意味着搜索有一个O（n）运行上界，结合3百万个状态的BFS，它是O（n^2），这意味着，当矩阵的大小增加时，您的程序将开始运行得越来越慢。 – user658991 2011-05-06 02:46:41

相关问题

 相关问题