你好，我正在根据WikiLink实现A*搜索算法，但我的搜索完全没有得到答案。有什么提示和/或帮助可以告诉我我可能做错了什么吗？

我得到了一张包含泥土和障碍物的地图，我需要遍历所有泥土颗粒并清理它们，然后返回到起点。

搜索函数

private void search_Astar(State start){ // we have confirmed a valid start state    // needed vars    Map<State, Integer> g_score = new HashMap<>();    Map<State, Integer> f_score = new HashMap<>();    Queue<State> openQueue = new PriorityQueue<State>(((State o1, State o2) -> f_score.get(o1) - f_score.get(o2)));    HashSet<State> closedSet = new HashSet<>();    // inits    g_score.put(start, 0);    f_score.put(start, start.heuristic());    openQueue.add(start);    // search    while (!openQueue.isEmpty()){        State current = openQueue.poll();        if (current.isGoal()){            // create path            solutionStack.push(Actions.Turn_Off);            while (current.takenAction != null){                solutionStack.push(current.takenAction);                current = current.parent;            }            return;        }        closedSet.add(current);        for (String action:current.legalActions()){            State child = current.CreateState(action);            if (closedSet.contains(child)) continue;            int tentativeG = g_score.get(current) + 1; // the cost to take an action            if (!openQueue.contains(child)) openQueue.add(child);            else if (tentativeG >= g_score.getOrDefault(child, Integer.MAX_VALUE)) continue;            g_score.put(child, tentativeG);            f_score.put(child, tentativeG + child.heuristic());        }    }}

以及State类（抱歉代码量大）

import java.util.ArrayList;import java.util.Collection;public class State {// keep track of position and orientationpublic Orientation orientation;public Position position;public boolean turned_on;// track world stateprivate Collection<Position> dirt;private Collection<Position> obstacles;private Position size;// variables for detirmining goal state and heuristicprivate Position home;// for calculating Gpublic State parent;public String takenAction;public State(Position position, Orientation orientation, boolean turned_on, Collection dirt, Collection obs, Position home,             Position size, State parent, String action) {    this.position = position;    this.orientation = orientation;    this.turned_on = turned_on;    this.dirt = dirt;    this.obstacles = obs;    this.home = home;    this.size = size;    this.parent = parent;    this.takenAction = action;}public int G(){    State curr = parent;    int total = 0;    while (curr != null){        total += 1;        curr = parent.parent;    }    return total;}public String toString() {    return "State{position: " + position + ", orientation: " + orientation + ", on:" + turned_on + "}";}@Overridepublic int hashCode(){    int hashVal = 23;    hashVal = ((hashVal + position.x) << 5) - (hashVal + position.x);    hashVal = ((hashVal + position.y) << 5) - (hashVal + position.y);    if(turned_on){        hashVal += 1243;    }    if (orientation == Orientation.NORTH){        hashVal += 12;    }else if (orientation == Orientation.EAST){        hashVal += 2234;    }else if (orientation == Orientation.WEST){        hashVal += 32345;    }    return hashVal + dirt.size();}@Overridepublic boolean equals(Object o){    if (o instanceof State){        State other = (State)o;        if(!other.position.equals(this.position)){            return false;        }else if( other.turned_on != this.turned_on){            return false;        }else if( other.orientation != this.orientation){            return false;        }else if (other.dirt.size() != this.dirt.size()){            return false;        } else{            return true;        }    }else {        return false;    }}/** * check to see if current node is a valid goal node * * @return true if valid, false otherwise */public Boolean isGoal(){    return dirt.isEmpty() && position.equals(home);}/** * Calculate all legal moves from current state * * @return Collection of legal actions (as string) */public Collection<String> legalActions(){    Collection<String> actions = new ArrayList<String>();    if (!turned_on){        actions.add(Actions.Turn_On);    }else{        // no reason we couldn't turn        actions.add(Actions.Turn_Left);        actions.add(Actions.Turn_Right);        if (dirt.contains(position)){            actions.add(Actions.Suck);        }        // check if we can move forward        // ATTENTION this must be at bottom of function        if (orientation == Orientation.NORTH){            for (Position o: obstacles) {                if (o.y == position.y + 1 && o.x == position.x || position.y == size.y){                    return actions;                }            }            // we have checked every obstacle and we would not collide            actions.add(Actions.Go);        }else if (orientation == Orientation.SOUTH){            for (Position o: obstacles) {                if (o.y == position.y - 1 && o.x == position.x || position.y == 1){                    return actions;                }            }            actions.add(Actions.Go);        }else if (orientation == Orientation.WEST){            for (Position o: obstacles) {                if (o.x == position.x - 1 && o.y == position.y|| position.x == 1){                    return actions;                }            }            actions.add(Actions.Go);        }else {            // we are pointing east            for (Position o: obstacles) {                if (o.x == position.x + 1 && o.y == position.y|| position.x == size.x){                    return actions;                }            }            actions.add(Actions.Go);        }    }    return actions;}/** * return a value to determine how optimal this state is * * evaluation methood: number of dirt left times a constant * which is the added to the distance to the closest dirt * if there are no dirts left it is the mannhatan distance to home * * note: should add state depth? * @return int */public int heuristic(){    int h = 0;    for (Position p:obstacles){        h += mannhatandist(p);    }    h += mannhatandist(home);    return h + dirt.size();}private int mannhatandist(Position p){    return Math.abs(p.x - position.x) + Math.abs(p.y - position.y);}private int distToClosest(){    int min = Integer.MAX_VALUE;    if (dirt.isEmpty()){        int dist = Math.abs(home.x - position.x) + Math.abs(home.y - position.y);        return dist;    }    for (Position p: dirt) {        int dist = Math.abs(p.x - position.x) + Math.abs(p.y - position.y);        min = Math.min(min, dist);    }    if (!turned_on) min++;    return min;}public State CreateState(String action) {    //Copy the "old" values from the current state.    //Before any action done, the "new" state has the same values.    Position new_position = new Position(position.x, position.y);    Orientation new_orientation = orientation;    boolean new_turned_on = turned_on;    Collection new_dirt = new ArrayList(dirt);    State new_parent = this;    //If the action is to turn the robot on, the turned_on variable for the new state takes the value "true".    if(action == "TURN_ON") {        new_turned_on = true;    }    //If the action is to turn the robot on, the turned_on variable for the new state takes the value "true".    else if(action == "TURN_OFF") {        new_turned_on = false;    }    //If the action is to suck, the current position needs to be taken out of the new state's dirt collection.    else if(action == "SUCK") {        new_dirt.remove(position);    }    //If the action is to go it depends on the orientation of the robot how the position of the new state will change.    else if(action == "GO") {        //If it's facing north, the y position increases by one, considering the old state and so on.        if(orientation == Orientation.NORTH) {            new_position.y++;        }        else if(orientation == Orientation.EAST) {            new_position.x++;        }        else if(orientation == Orientation.SOUTH) {            new_position.y--;        }        else {            new_position.x--;         }    }    //If the action is to turn left it depends on the orientation of the robot in the current state what the new orientation will be.    else if(action == "TURN_LEFT") {        if(orientation == Orientation.NORTH) {            new_orientation = Orientation.WEST;        }        else if(orientation == Orientation.EAST) {            new_orientation = Orientation.NORTH;        }        else if(orientation == Orientation.SOUTH) {            new_orientation = Orientation.EAST;        }        else {            new_orientation = Orientation.SOUTH;        }    }    //If the action is to turn right it depends on the orientation of the robot in the current state what the new orientation will be.    else if(action == "TURN_RIGHT") {        if(orientation == Orientation.NORTH) {            new_orientation = Orientation.EAST;        }        else if(orientation == Orientation.EAST) {            new_orientation = Orientation.SOUTH;        }        else if(orientation == Orientation.SOUTH) {            new_orientation = Orientation.WEST;        }        else {            new_orientation = Orientation.NORTH;        }    }    //Make a new state from the new variables that have been changed according to the action done.    State new_state = new State(new_position, new_orientation, new_turned_on, new_dirt, obstacles, home, size, new_parent, action);    return new_state;}}

回答：

我现在已经修复了这个问题。问题出在我的启发式函数不一致。我已经修改了它，现在运行正常了。

由于这是学校项目，我不会分享我的答案，因为学校的自动反作弊系统可能会检测到这一点，我会在这个评论中添加我的学校用户名（dagur13）。

附注：我会在项目评分后发布我更新后的代码。