我正在尝试实现A*算法来解决滑动拼图问题，但算法无法正常工作。我已经为此努力了几天，但老实说，我现在完全不知道发生了什么。我一直在参考维基百科和“RedBlobGame”博客的伪代码，但现在我完全迷失了方向。

这是A*算法的代码

    ArrayList<Node> open = new ArrayList<Node>();    ArrayList<Node> closed = new ArrayList<Node>();    Node goal = new Node(myBoard.getGoalBoard());    Node start = new Node(mb);    start.setH(this.heuristic.calculate(start, goal));    start.setG(0);    start.setDepth(0);    open.add(start);    Node current = null;    while(!open.isEmpty() && !myBoard.stopAlgorithm){        current = getLowest(open);        if(current.isGoal()){            System.out.println("done");            return finalise(current.getBoard(), displaySearch, current.getDepth());        }        open.remove(current);        closed.add(current);        int depth = current.getDepth() + 1;        ArrayList<Node> succesors = current.getSuccessors(depth);        for(Node node: succesors){            node.setH(this.heuristic.calculate(node, goal));            node.setG(current.getG() + 1);            node.setParent(current);            if(!closed.contains(node)){                if(!open.contains(node)){                    open.add(node);                }else{                    Node openN = open.get(open.indexOf(node));                    if(node.getG() < openN.getG()){                        openN.setG(node.getG());                        openN.setParent(node.getParent());                    }                }            }        }    }    System.out.println("path not finded");    return null;

有时候它们能找到解决方案，有时候只是继续寻找并扩展更多的可能状态，我看不出问题出在哪里。有人能帮我吗？

这是Node类的代码 http://pastie.org/10521788以及启发式计算（本例中为曼哈顿距离）的代码 http://pastie.org/10521789

回答：

这只是我的猜测。我已经有一段时间没有编写A*算法了，我看不出你是如何实现Node类的。我认为你不应该使用node.setG(current.getG()+1)来设置G值，或者在节点已经添加到开放列表时设置父节点为当前节点。

试试这个：

int depth = current.getDepth() + 1;ArrayList<Node> succesors = current.getSuccessors(depth);for (Node node : succesors) {    if (!closed.contains(node) && !open.contains(node)) {        node.setH(this.heuristic.calculate(node, goal));        node.setG(current.getG() + 1);        node.setParent(current);        open.add(node);    } }

这是一个更完整的版本，似乎对我有效（仅在3×3上测试过）。大部分代码只是设置状态。需要注意的是：为了提高效率，你不希望搜索列表来查看某个状态是否包含在其中。使用HashSet会更好，但这需要一致地实现hashCode()和equals()方法。你的IDE可能可以生成它们。