A *明星打開列表未按預期工作

我曾經問過A *的數據結構。我現在解決了這個問題。但還有另一個問題。我的A *速度很慢，不像我預期的那樣工作。這意味着我用維基百科僞碼（德語和英語）在Java中實現了源代碼。下圖中的圖表是我用於測試目的的圖表。例如，該算法從節點1開始到目的地節點8。啓發函數將通過使用曼哈頓距離，使用節點旁邊的方形剎車中的座標來計算。關閉列表從開始節點1（前身）到3（1）-6（3）-2（1）-4（1）-3（2）-2（3）-4（3）-8（6））。我認爲A *直接從1到8，因爲它是最短的路徑。但是它從6跳回到節點2，因爲2的f值是列表中最低的。那麼這是正確的嗎？在我看到的例子中，在它之後訪問了一個節點之後，它不會跳回到任何其他節點。我有一個從兩個方向與其他節點連接的圖。因此，如果相反的方式是或不在相應的列表中，我更改了源代碼中的if條件以證明。否則它會以無限循環結束。問題是什麼，它爲什麼從節點6跳回到節點2？我必須刪除我的公開列表中的節點嗎？ enter image description here 。A *明星打開列表未按預期工作

public ArrayList<NodeD> executeAstar(ArrayList<Arclistentry> data, NodeD start, NodeD dest) 
{ 
    openlist = new PriorityQueue<NodeD>(1,comp); 
    closedlist.clear(); 
    openlist.offer(start); 
    start.setg(0); 
    start.seth(manhattendistance(start, dest)); 
    start.setf(start.getg()+start.geth()); 
    while(!openlist.isEmpty()) 
    { 
     NodeD currentnode = openlist.poll(); 
     if(currentnode.getnodenumber() == dest.getpredessor()) 
     { 
      closedlist.add(currentnode); 
      return closedlist; 
     } 
     closedlist.add(currentnode); 
     for(int i=0; i< data.size(); i++) 
     { 
      if(data.get(i).getstart()==currentnode.getnodenumber()) 
      { 
       NodeD successor = new NodeD(data.get(i).getnode(),data.get(i).getstart(), data.get(i).getcoorddest()); 
       NodeD reversesuccessor = new NodeD(data.get(i).getstart(),data.get(i).getnode(),data.get(i).getcoordstart()); 
       float tentative_g = currentnode.getg()+data.get(i).getcost(); 
       if((contains(successor, closedlist)||contains(reversesuccessor, closedlist))&&(tentative_g >=successor.getg())) 
       { 
        continue; 
       } 
       if(!(contains(successor, openlist))|| (tentative_g < successor.getg())) 
       { 
        successor.setpredessor(currentnode.getnodenumber()); 
        successor.setg(tentative_g); 
        successor.seth(manhattendistance(successor, dest)); 
        successor.setf(successor.getg()+manhattendistance(successor, dest)); 
        if(!contains(successor, openlist)) 
        { 
         openlist.offer(successor); 
        } 
       } 
      } 
     } 
    } 
    ArrayList<NodeD> ret = null; 
    return ret; 
}

來源

2013-06-04 Irgendw Pointer

明確陳述要粘貼代碼將是有用的，很好。 – darijan

關於性能：首先，考慮將openList中的項目添加到一個名爲'openSet'的Set中。你可以通過調用'openSet.contains（node）'來快速檢查一個項目是否在openList中。只要確保在關閉時從openSet中刪除該項目。其次，考慮使用另一個openList：我在自己的A *算法中使用FibonnacciHeap在Java的PriorityQueue 上看到了10倍的速度提升。 –

在A *啓發式必須admissible - 也就是說，它絕不能高估兩個節點之間移動的成本。

在您的示例中，[2,4]和[4,2]之間的成本爲3，但是Manhatten距離爲4.因此，它是不可接受的，並且不適用於您作爲啓發式。

是否必須刪除我的打開列表中的節點？

呃，是的，否則你的while循環將永遠不會完成。刪除甚至在pseudocode

來源

2013-06-04 13:59:57

好的，但我必須使用啓發式？或者我的代碼是正確的，但是這個例子是以最壞的成本選擇的？我的while循環結束了。它通過執行openlist.poll（）;列表中具有最低f值的元素。 –

使用歐幾里德距離來計算啓發式算法會更好嗎？ –

@IndndwPointer：這取決於實際問題 - 在某些情況下，沒有好的啓發式。它**必須被允許返回最短路徑*（如果[一致]（http://en.wikipedia.org/wiki/Consistent_heuristic）也是最好的）*。從你的例子來看，歐幾里得距離看起來並不像歐幾里德距離那樣，因爲'[4,4]'和'[4,6]'只有距離1。 –

A *明星打開列表未按預期工作

回答

相關問題