A-星算法。獲取最佳路徑

有幾天我試圖在圖中學習一些關於尋路的新知識。
現在我正在探索A-star算法。A-星算法。獲取最佳路徑

我寫我的基於Wikipedia代碼，它工作正常，但我試圖解決幾個小時一個問題：

從維基百科的實施允許「重建路徑」 - 它會展示了用於尋找路徑的所有方式。

是否有任何機會只顯示連接起點和終點的路徑而不顯示中間步驟（算法出錯的方式）？

UPDATE 2 這是陽極：

class aNode 
{ 
public: 
    QHash<quint64,Node>::iterator it; 
    quint64 comeFrom; 
    double f; 
    double g; 
    double h; 
}

因此，我已經改變類型的陽極類從int加倍（如我使用的是具有真實地理COORDS兩個節點之間的距離）和改性我的算法。
這是：

bool Graph::findPath(Node* node_from, Node* node_to) 
{ 
    QMap<double,aNode> open; // key - cost function f 
    QMap<quint64,aNode> closed; // key - Node id 

    aNode sNode; 
    sNode.it = nodes.find(node_from->id); 
    sNode.g = 0; 
    sNode.h = distance(node_from,node_to); 
    sNode.f = sNode.g + sNode.h; 
    sNode.comeFrom = 0; 

    open.insert(sNode.f, sNode); 

    while (!open.isEmpty()) 
    { 
     aNode x = open.begin().value(); 
     if (x.it->id == node_to->id) 
     { 
      int comeFrom = x.comeFrom; 
      while (comeFrom != 0) 
      { 
       route.push_back(comeFrom); 
       comeFrom = closed.find(comeFrom)->comeFrom; 
      } 
      return true; 
     } 
     open.remove(x.f); 
     closed.insert(x.it->id,x); 
     for (int i = 0 ; i < x.it->adj.size() ; i++) 
     { 
      if (!edges.contains(QPair<quint64,quint64>(x.it->id,x.it->adj[i]))) 
       continue; 
      if (closed.contains(x.it->adj[i])) 
       continue; 
      aNode y; 
      y.it = nodes.find(x.it->adj[i]); 
      y.g = x.g + edges.find(QPair<quint64,quint64>(x.it->id,x.it->adj[i]))->cost; 
      y.h = distance(&(*y.it),node_to); 
      y.f = y.g + y.h; 
      y.comeFrom = x.it->id; 
      if (open.key(y,-2) == -2) 
       open.insert(y.f,y); 
      else 
       if (y.g < open.find(open.key(y))->g) 
        open.insert(y.f, y); 
     } 
    } 
    return false; 
}

但它仍然繪製中間步驟。在我看來，斯密錯「comefrom」成員提起

來源

2013-12-15 tema

關閉列表中的每個節點都有一個'comeFrom'條目。從目標回溯到開始重建一條單一的最短路徑。 – IInspectable

@IInspectable實際上，如果我畫它顯示我所有的過程，它用來找到方式，我的意思是錯誤轉身等等 – tema

因爲你沒有顯示你的渲染代碼，或你的'reconstruct_path'甚至你的'aNode '執行它是不可能知道你的問題在哪裏。 – IInspectable

你的算法不正確，因爲你開集是地圖，而不是一個優先級隊列。爲了正確執行星標，您需要始終評估具有最小成本函數的節點（tentative_score）。在你的情況下aNode x

你可以使用stl priority queue implementation。

來源

2013-12-16 13:27:57 UmNyobe

在我的QMap中的鍵可能是代價函數值，所以一切都作爲優先級隊列，因爲在QMap對象存儲按他們的密鑰的順序（從最小） – tema

我已更新我的代碼，請參閱更新2 – tema

A-星算法。獲取最佳路徑

回答

相關問題