A*平均时间复杂度

Question

我正在为我的学士论文做两个算法的研究: Floyd-Warshall和A*算法。在我的工作中，时间复杂度是两种算法比较中的一个重要部分。但由于A*中的启发式算法，算法的时间复杂度不是恒定的。我发现的唯一信息是，在最坏的情况下，时间复杂性可能是指数级的困难。

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

Answer 1

首先，我建议你将A*看作是某种具有启发式近似的Dijkstra，所以在最坏的情况下，你的解决方案将是Dijkstra的时间复杂度(在原始算法中是O(|V|+|E|) * log|V|)，所以肯定不是指数级的，当然，如果你考虑启发式函数不大于实际距离本身的话)。为了理解起见，你可以在这里查看我在相同算法上实现Dijkstra和A*时的"relax“函数代码的比较器：

---
//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%准确时，就会发生这种情况-这将是通向解决方案的直接路径。