A*平均时间复杂度

Question

我正在为我的学士论文研究两种算法：Floyd-Warshall 和 A* 算法。在我的工作中，时间复杂度是比较这两种算法的重要部分。但是由于 A* 中的启发式算法，算法的时间复杂度不是常数。我发现的唯一信息是，在最坏的情况下，时间复杂度可能成倍增加。

在正常实践中，A* 算法的平均时间复杂度和最佳时间复杂度是多少？

Answer 1

首先，我建议您将 A* 视为某种具有启发式近似解的 Dijkstra，因此在最坏的情况下，您的解决方案将是 Dijkstra 的时间复杂度（即 O(|V|+|E |) * log|V|) 在原始算法中）所以肯定不是指数，当然如果你认为启发式函数不大于实际距离本身）。为了便于理解，当我在同一算法上实现 Dijkstra 和 A* 时，您可以在此处查看我的“放松”函数代码比较器：

---
//this function is a comparator between the distance of two vertices, it will be used 
for the heap and the Relax function in Dijkstra 
struct minDistance {
    bool operator()(Vertex* a, Vertex * b) const {
        return (a->getDis() > b->getDis());
    }
};

//this function is a comparator between the distance of two vertices but with the 
heurstic function's value added, it will be used in AStar
struct minDistanceProx {
    bool operator()(Vertex* a, Vertex * b) const {
        return ((a->getDis() + a->getDisProx()) > (b->getDis() + b->getDisProx()));
        //notice that the relax function will only change the distance value,
        //but the heap will count the distance and the heuristic value together so the 
heap is sorted as planned!
    }
};
---

您可以将其视为“从该节点到解决方案的距离至少为 x 远”，这就是为什么在从目的地或“空中距离”的转置图上可以将良好的近似值实现为 BFS 的原因，如果您将节点视为某种地图。对于最佳时间复杂度，当您的启发式函数是实际距离并且近似值将是 100% 准确时，它就会发生——这将是通往解决方案的直接途径。

A*平均时间复杂度

A* average time complexity

algorithm

path-finding

a-star