A * Алгоритм Java

Question

Я провел целый уик-энд, играя с этим. Я пытаюсь сохранить узлы в структуре данных PriorityQueue. Моя астарная функция, похоже, не делает то, что нужно. Любой разум смотрит?

public void aStar(Node from, Node to) { 

    PriorityQueue<Node> exploreList = new PriorityQueue<Node>(); 
    ArrayList<Node> visited = new ArrayList<Node>(); 
    ArrayList<Node> successors = new ArrayList<Node>(); 

    Node current = from; 
    System.out.println(current.getName()); 
    while (current != to) { 
      successors = current.getConnected(); 
      Collections.sort(successors); 
      for (Node n : successors) { 
        if (!visited.contains(n)) { 
          exploreList.add(n); 
        } 
        for (Node n1 : successors) { 
          if (n.fSum() > n1.fSum()) { 
          exploreList.remove(n); 
          exploreList.add(n1); 
          }  
        } 
      } 
      visited.add(current); 
      current = exploreList.remove(); 
      System.out.println(current.getName()); 
    } 

Node Class здесь

public class Node implements Comparable { 
    private String name; 
    private int travDist; 
    private int straightDist; 
    private ArrayList<Arc> arcs; 

/** 
* Constructor for a new node 
* 
* @param n 
*/ 
    public Node(String n, int aTravDist, int aStraightDist) { 
     name = n; 
     travDist = aTravDist; 
     straightDist = aStraightDist; 

     arcs = new ArrayList<Arc>(); 
    } 

/** 
* Adds a new arc 
* 
* @param to 
* @param c 
*/ 
public void addArc(Node to, int c) { 
    arcs.add(new Arc(to, c)); 
} 

/** 
* Gets the list of connected nodes to this node 
* 
* @return 
*/ 
public ArrayList<Node> getConnected() { 
    ArrayList<Node> returnData = new ArrayList<Node>(); 
    for (Arc a : arcs) { 
     returnData.add(a.getNode()); 
    } 
    return returnData; 
} 

@Override 
public int compareTo(Object o) { 
    //return name.compareTo(((Node) o).getName()); 
    Integer sum = ((Node)o).fSum(); 
    return sum.compareTo(fSum()); 
} 

public int fSum() { 

    return travDist + straightDist; 
} 

/** 
* Gets the name of the Node 
* 
* @return 
*/ 
public String getName() { 
    return name; 
} 


} 

Answer 1

То, что вы делаете, это не правильный алгоритм звезды.

Collections.sort(successors); 

Вы не должны этого делать. В «Звезде» вы всегда считаете всех преемников. Вам не нужно беспокоиться о заказе - очередь приоритетов позаботится об этом. Однако, добавив эту строку, вы увеличите сложность алгоритма.

for (Node n1 : successors) { 
    if (n.fSum() > n1.fSum()) { 
    exploreList.remove(n); 
    exploreList.add(n1); 
    }  
} 

Это совершенно неправильно. Что вы здесь делаете: вы добавляете только ближайших из всех преемников. Это будет beam search с лучом размера 1, а не звездой - просто держите их всех.