java - 我正在尝试运行 BFS Algo，但它让我失望了

Question

当我到达 PriorityQueue openList.add(state) 时，我正在尝试运行 BFS第一次有效，第二次无效。错误是:

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 接口(interface)来完成，或者通过指定一个 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 接口(interface)，它也会工作，因为不需要将单个对象与任何对象进行比较。

当您插入第二个对象时，您会得到一个 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;
    }
}