java - A* 算法 8 谜题

Question

我读过很多A*算法的伪代码，但它们都没有真正解释如何输出解。我相信我理解使用优先级队列表示尚未访问的内容和使用已探索的表的概念，但是当我执行该算法时，我不知道在什么时候打印出结果。有没有人有一个伪代码来实际显示如何输出路径？

我真的很感激。我一直在尝试用算法来实现8-puzzle问题

这是我的代码:

public class Board{

private int[][] squares;
private int f;
private int g;
private int h;

private int size;
private Board parent;

public Board(Board current, Board parent)
{
    this(current);
    g = current.getG();
    h = current.getH();
    f = current.getF();
    this.parent = parent;

}

public void solveH1()
{

    while(!frontier.isEmpty())
    {
        board = frontier.poll();

        ArrayList<Board> successors = new ArrayList<Board>();
        Board b1 = new Board(board.moveDown(),board);
        Board b2 = new Board(board.moveUp(),board);
        Board b3 = new Board(board.moveLeft(),board);
        Board b4 = new Board(board.moveRight(),board);
        if(!b1.equals(board))
            successors.add(b1);
        if(!b2.equals(board))
            successors.add(b2);
        if(!b3.equals(board))
            successors.add(b3);
        if(!b4.equals(board))
            successors.add(b4);
        for(int i=0; i<successors.size(); i++)
        {
            if(successors.get(i).isGoal())
            {
                break;
            }
            int g = board.getG()+1;
            int h = successors.get(i).getH1Cost();
            successors.get(i).setG(g);
            successors.get(i).setH(h);
            successors.get(i).setF(g+h);

            if(frontier.contains(successors.get(i)))
            {
                Iterator<Board> iterator = frontier.iterator();
                Board b = null;
                while(iterator.hasNext())
                {
                    b = iterator.next();
                    if(b.equals(successors.get(i)))
                    {
                        break;
                    }
                }
                if(b.getG() < successors.get(i).getG())
                {
                    break;
                }
            }
            if(exploredSet.contains(successors.get(i)))
            {
                int index = exploredSet.indexOf(successors.get(i));
                if(exploredSet.get(index).getG() < successors.get(i).getG())
                    break;
            }
            else
            {
                frontier.add(successors.get(i));
            }
        }
        exploredSet.add(board);
    }
    printPath();
}
public void printPath()
{

    ArrayList<Board> path = new ArrayList<Board>();
    cursor = board;
    while(cursor.getParent()!=null)
    {
        path.add(cursor);
        cursor = cursor.getParent();
    }
    for(int i=0; i<path.size(); i++)
        System.out.println(path.get(i));
}

由于某种原因，这只是打印一个节点，而且它甚至不是目标。谁能告诉我我错过了什么？

Answer 1

当您将节点推送到队列时，您还保存(推送)它的父节点，即您访问它的节点。

class NodeWrapper {
 public float cost;
 public Node node;
 public Node parentNode;
 public NodeWrapper(Node node, Node parentNode) {
   this.node = node;
   this.parentNode = parentNode;
 }
}

然后

openQueue.push(new NodeWrapper(neihgbouringNode, currentNode));

当您到达结束节点时，您只需从它返回即可。

List<Node> out = new ArrayList<Node>();
while (currentNode != null) {
   out.add(currentNode.node);
   currentNode = currentNode.parentNode;
}
return out; 

Here's a demo of a A* pathfinder .