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-星算法。获取最佳路径

回答

相关问题