A* Algorithm Java

Question

我花了整个周末玩这个。我试图在优先队列数据结构中存储节点。我的星形函数似乎没有做它应该做的。有人介意看一下吗?

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

这里的节点类

   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

你所做的不是一个合适的a星算法。

Collections.sort(successors);

你不应该那样做。在一个明星中，你总是要考虑到所有的接班人。您不必担心顺序——优先队列会处理这个问题。但是，添加这一行会增加算法的复杂性。

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

这是完全错误的。你在这里所做的是:你只添加了所有继承人中最接近的人。这将是一个光束搜索，光束的大小为1，而不是a星-只要保持它们都在