A 알고리즘 8- 퍼즐

Question

A * 알고리즘에 대한 많은 의사 코드를 읽었지만 둘 다 실제로 솔루션을 출력하는 방법을 설명하지 못했습니다. 나는 아직 방문하지 않은 우선 순위 큐를 사용하는 개념을 이해하고 탐험을위한 테이블을 가지고 있다고 믿는다.하지만 알고리즘을 통해 갈 때 어떤 점에서 결과를 출력 할 지 모르겠다. 경로를 출력하는 방법을 실제로 보여주는 의사 코드가 있습니까?

정말 고맙습니다. 이것은 단지 하나 개의 노드를 인쇄, 어떤 이유로

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)); 
} 

, 그것도 목표 봇입니다 : 나는 8 퍼즐 문제

여기 내 코드의를 구현하는 알고리즘을 사용하려고 시도하고있다. 아무도 내가 누락 된 것을 말할 수 있습니까?

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.