A * 알고리즘 Java

Question

나는 주말 내내 이걸 가지고 놀고있다. PriorityQueue 데이터 구조에 노드를 저장하려고합니다. 나의 astar 기능 doesnt는해야하는 것을하고있는 것처럼 보인다. 누구 봐도 괜찮 니?

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

당신이하고있는 것은 적절한 스타 알고리즘이 아니다.

Collections.sort(successors); 

그렇게해서는 안됩니다. 스타에서는 항상 모든 후임자를 고려합니다. 주문에 대해 걱정할 필요가 없습니다. 우선 순위 대기열이이를 처리합니다. 그러나이 줄을 추가하면 알고리즘의 복잡성이 증가합니다.

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

이것은 완전히 잘못되었습니다. 여기에서하는 일은 모든 후임자 중 가장 가까운 것만 추가하는 것입니다. 이것은 별이 아닌 크기가 1 인 빔이있는 beam search이 될 것입니다. 전체를 그대로 유지하십시오.