我正在尝试运行 BFS 算法，但它让我失望了

Question

我正在尝试运行 BFS，当我到达 PriorityQueue openList.add（状态）第一次有效，第二次无效。错误是：

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 CLASS:

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

PriorityQueue 要求其元素实现 Comparable 接口，但您的 State class 没有实现。

来自 java 文档：

A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

您需要将 State class 设置为：

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

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

Answer 2

优先级队列的用途需要对其元素进行排序。在 Java 的 PriorityQueue 中，这可以通过使元素实现 Comparable 接口来完成，或者通过指定 Comparator.

I`m trying to run BFS, when i get to PriorityQueue openList.add(state) the first time it works and the secound time it dosent.

如果您只将一个对象插入 PriorityQueue，即使对象没有实现 Comparable 接口，它也会工作，因为不需要将单个对象与任何对象进行比较。

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

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;
    }
}

我正在尝试运行 BFS 算法，但它让我失望了

Im trying to run BFS Algo and it throws me out

java

priority-queue

我正在尝试 运行 BFS 算法，但它让我失望了

Im trying to run BFS Algo and it throws me out

java

priority-queue

我正在尝试运行 BFS 算法，但它让我失望了