我试图运行BFS Algo，它抛出我

Question

我试图运行BFS，当我到达PriorityQueue openList.add（状态） 它第一次工作和secound时间剂量。 错误是：

Exception in thread "main" java.lang.ClassCastException: algorithms.mazeGenerators.Position cannot be cast to java.lang.Comparable 
    at java.util.PriorityQueue.siftUpComparable(Unknown Source) 
    at java.util.PriorityQueue.siftUp(Unknown Source) 
    at java.util.PriorityQueue.offer(Unknown Source) 
    at java.util.PriorityQueue.add(Unknown Source) 
    at algorithms.searchers.BFS.search(BFS.java:30) 
    at boot.Run.main(Run.java:18) 

BFS类：

public class BFS extends CommonSearcher { 

    @Override 
    public Solution search(Searchable s) { 

     State cur = null; 
     s.getStartState().setCost(0); 
     openList.add(s.getStartState()); 
     HashSet<State> closedSet = new HashSet<State>(); 
     while (!openList.isEmpty()) { 
      cur = popOpenList(); 
      closedSet.add(cur); 
      if (cur.equals(s.getGoalState())) { 
       return backTrace(cur, s.getStartState()); 
      } 
      ArrayList<State> successors = s.getAllPossibleStates(cur); 
      for (State state : successors) { 
       if (!closedSet.contains(state) && !openList.contains(state)) { 
        state.setCameFrom(cur); 
        state.setCost(cur.getCost() + 1); 
        openList.add(state); 
       } else { 
        if (openList.contains(state)) { 
         if (state.getCost() < returnWantedState(state).getCost()) { 
          openList.remove(state); 
          openList.add(state); 
          adjustPriorityList(); 
         } 

        } else { 
         openList.add(state); 
         adjustPriorityList(); 
        } 
       } 
      } 
     } 
     return null; 
    } 

    /* 
    * public State popOpenList() { State temp = openList.remove(); for (State 
    * state : openList) { if (temp.getCost() > state.getCost()) { 
    * openList.add(temp); temp = state; openList.remove(state); } } return 
    * temp; 
    * 
    * } 
    */ 

    public void adjustPriorityList() { 
     State temp = openList.remove(); 
     for (State state : openList) { 
      if (temp.getCost() < state.getCost()) { 
       openList.add(temp); 
       temp = state; 
       openList.remove(state); 

      } 
     } 
     openList.add(temp); 

    } 

    public State returnWantedState(State state) { 
     for (State state1 : openList) { 
      if (state.equals(state1)) 
       state = state1; 
     } 

     return state; 
    } 

} 

CommonSearcher Class: 

package algorithms.searchers; 

import java.util.PriorityQueue; 

import algorithms.mazeGenerators.Searchable; 
import algorithms.mazeGenerators.Solution; 
import algorithms.mazeGenerators.State; 

public abstract class CommonSearcher implements Searcher { 

    protected PriorityQueue<State> openList; 
    private int evaluatedNodes; 

    public CommonSearcher() { 
     openList = new PriorityQueue<State>(); 
     evaluatedNodes = 0; 
    } 

    protected State popOpenList(){ 
     evaluatedNodes++; 
     return openList.poll(); 
    } 


    @Override 
    public abstract Solution search(Searchable s); 

    @Override 
    public int getNumberOfnodesEvaluated() { 
     // TODO Auto-generated method stub 
     return evaluatedNodes; 
    } 

    protected Solution backTrace(State goalState, State startState){ 
     Solution sol = new Solution(); 
     while(!goalState.equals(startState)){ 
      sol.getSolutionList().add(goalState.getState()); 
      goalState = goalState.getCameFrom(); 
     } 
     return sol; 
    } 



} 

State Class: 

package algorithms.mazeGenerators; 

public abstract class State { 

    protected String state; // the state represented by a string 
    protected double cost;  // cost to reach this state 
    protected State cameFrom; // the state we came from to this state 

    public State(){ 

    } 

    public State(String state){ // CTOR  
     this.state = state; 
    } 

    @Override 
    public boolean equals(Object obj){ // we override Object's equals method 
     return state.equals(((State)obj).state); 
    } 

    public String getState() { 
     return state; 
    } 

    public void setState(String state) { 
     this.state = state; 
    } 

    public double getCost() { 
     return cost; 
    } 

    public void setCost(double cost) { 
     this.cost = cost; 
    } 

    public State getCameFrom() { 
     return cameFrom; 
    } 

    public void setCameFrom(State cameFrom) { 
     this.cameFrom = cameFrom; 
    } 

} 

Position Class: 

package algorithms.mazeGenerators; 

import java.util.ArrayList; 

public class Position extends State { 

    // Data members 
    private int x, y, z; 
    private int wallOrNot; 
    private boolean visted; 


    // Constructor 
    public Position() { 
     visted = false; 
     wallOrNot = 1; 
    } 

    /* 
    * The method gets the position details 
    * and checks if its a wall or not 
    * if its a wall then its marked as visited. 
    * */ 
    public void setPos(int x, int y, int z) { 
     this.x = x; 
     this.y = y; 
     this.z = z; 
     if (z % 2 != 0 || x % 2 != 0 || y % 2 != 0) 
      visted = true; 
     setState("{" + x+"," + y+","+ z +"}"); 
    } 

    // getrs and setters 

    public int getWallOrNot() { 
     return wallOrNot; 
    } 

    public void setWallOrNot(int wallOrNot) { 
     this.wallOrNot = wallOrNot; 
    } 

    public boolean isVisted() { 
     return visted; 
    } 

    public void setVisted(boolean visted) { 
     this.visted = visted; 
    } 

    public int getX() { 
     return x; 
    } 

    public void setX(int x) { 
     this.x = x; 
    } 

    public int getY() { 
     return y; 
    } 

    public void setY(int y) { 
     this.y = y; 
    } 

    public int getZ() { 
     return z; 
    } 

    public void setZ(int z) { 
     this.z = z; 
    } 


    /* 
    * This method gets returns all a list of neighbors that hasn't marked as visited for a specific Position. 
    * returns the list of neighbors. 
    * */ 
    public ArrayList<Position> getNeighbors(Position[][][] maze) { 
     ArrayList<Position> neighbors = new ArrayList<Position>(); 
     if (this.x > 1) 
      if (maze[x - 2][y][z].isVisted() == false) 
       neighbors.add(maze[x - 2][y][z]); 
     if (this.x < maze.length - 2) 
      if (maze[x + 2][y][z].isVisted() == false) 
       neighbors.add(maze[x + 2][y][z]); 
     if (this.y > 1) 
      if (maze[x][y - 2][z].isVisted() == false) 
       neighbors.add(maze[x][y - 2][z]); 
     if (this.y < maze[x].length - 2) 
      if (maze[x][y + 2][z].isVisted() == false) 
       neighbors.add(maze[x][y + 2][z]); 
     if (this.z > 1) 
      if (maze[x][y][z - 2].isVisted() == false) 
       neighbors.add(maze[x][y][z - 2]); 
     if (this.z < maze[x][y].length - 2) 
      if (maze[x][y][z + 2].isVisted() == false) 
       neighbors.add(maze[x][y][z + 2]); 
     return neighbors; 
    } 


    public String toString(){ 
     return "{" + x+"," + y+","+ z +"}"; 
    } 

    public boolean equals(Object obj){ // we override Object's equals method 
      return state.equals(((Position)obj).state); 
     } 

} 

Answer 1

优先级队列的目的，要求其元素的顺序。 在Java的PriorityQueue中，可以通过使元素实现Comparable接口， 或指定Comparator来完成此操作。

我正尝试运行BFS，当我第一次到达PriorityQueue时，openList.add（state）工作，它的secound时间是剂量。

如果你只插入一个对象到PriorityQueue， 它甚至会工作，如果目标没有实现Comparable接口， 因为单一对象不需要被比作什么。

当您插入第二个对象， 如果对象没有实现Comparable和你没有提供Comparator你得到一个ClassCastException。

public abstract class State implements Comparable<State> { 

    // ... 

    @Override 
    public int compareTo(State other) { 
     if (getCost() > other.getCost()) { 
      return -1; 
     } 
     if (getCost() < other.getCost()) { 
      return 1; 
     } 
     return 0; 
    } 
} 

Answer 2

PriorityQueue要求其元素来实现Comparable接口，但您State类并没有做到这一点。

从Java文档：

优先级队列依靠自然顺序也不允许 插入不可比较的对象的（这样做可能会导致 ClassCastException异常）。

你需要让你的State类是这样的：

public abstract class State implements Comparable<State> { 
    .... 

    @Override 
    public int compareTo(State s) { 
    ... 
    } 
}