設置A *搜索

我寫了一個程序的一小部分，在這個程序中我必須編寫一個尋路算法。該功能採用稱爲'路線'的方式，每個路線定義2D空間中的起點和終點。該算法需要找到最短和最有效（從原點）的路徑（通過這些路徑），最大限度地減少總體行駛距離。設置A *搜索

我做了一些研究，並開始了一條我認爲可行的道路。到目前爲止，我已經將路線轉換爲有向圖，它們都鏈接起來，就好像它是理想化的路線圖。然後我試圖在這個圖表上執行A *搜索。我使用的啓發式計算了左側行駛的'路線'的總距離，而我使用的起始距離（G）值僅僅是到達當前點的累計行駛距離。這對一些輸入有效，但其他人根本沒有返回路徑，我似乎無法弄清楚爲什麼。

我的啓發式算法有可能是錯誤的，這會導致某處出現錯誤計算，或者更可能是A *程序本身錯誤？還是我在這裏完全錯誤的軌道？

爲了以防萬一，我會把getPath函數放在下面（用Java編寫）。

在此先感謝。

public ArrayList<Vector2> getPath() 
{ 
    PriorityQueue<SearchNode> openList = new PriorityQueue<SearchNode>(10, new SearchNodeComparator()); 
    ArrayList<SearchNode> closedList = new ArrayList<SearchNode>(); 

    map.startJobs(); 
    searchDepth = 0; 

    SearchNode start = searchableGraph.getNode(new Vector2(0, 0)); 
    int goalsLeft = map.getJobCount(); 

    start.setDistanceTraveled(0); 

    openList.add(start); 

    while (openList.size() > 0) 
    { 
     SearchNode current = openList.peek(); 
     searchDepth++; 

     if (map.isJobEndPoint(current.getValue())) 
     { 
      map.completeJob(current.getValue()); 
      goalsLeft--; 

     } 

     if (reachedGoalState(current, searchableGraph.getNodes().size())) 
     { 
      return getFinalPath(current); 
     } 
     else 
     { 
      ArrayList<SearchNode> neighbours = getNeighbours(current); 

      for (int i = 0; i < neighbours.size(); i++) 
      { 
       SearchNode node = neighbours.get(i);   
       System.out.print("Inspecting node" + node.getValue().toString()); 

       float distanceTraveled = current.getDistanceTraveled() + getDistance(current.getValue(), node.getValue()); 

       float heuristic = heuristic(node); 

       if (!openList.contains(node) && !closedList.contains(node)) 
       { 

        node.setDistanceTraveled(distanceTraveled); 

        node.setDistanceToGoal(distanceTraveled + heuristic); 

        node.setParent(current); 

        openList.add(node); 
       } 
       else if(openList.contains(node)) 
       { 
        if (node.getDistanceTraveled() <= distanceTraveled) 
        { 

         node.setDistanceToGoal(distanceTraveled + heuristic); 


         node.setParent(current); 
        } 

       } 
      } 

      openList.remove(current); 
      closedList.add(current); 
     } 
    } 

    return new ArrayList<Vector2>(); 
}

來源

2013-04-27 Will Bagley