0

我已经阅读了许多 A* 算法的伪代码，但它们都没有真正解释如何输出解决方案。我相信我理解为尚未访问的对象使用优先级队列并为已探索的对象使用 has 表的概念，但是当我通过算法时，我不知道在什么时候打印出结果。有没有人有一个伪代码实际显示如何输出路径？

我真的很感激。我一直在尝试使用算法来实现 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));
}

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

4

1 回答 1

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;

这是 A* pathfinder 的演示。

于 2014-10-25T10:27:13.140 回答