algorithm - 精确图算法

Question

在数据结构和算法中，“精确图算法”是什么意思？你能给我一些例子吗？

Answer 1

我想它指的是算法是否产生了一个结果，对于给定的问题是最优的，或者它是否产生“只是”一个近似的结果。

例如，如果您在图表中查找 shortest path从一个节点到另一个节点，有一堆算法( Dijkstra ， Floyd-Warshall ，......你的名字)可以准确地解决问题，即它们产生两个给定节点之间的最短路径。

另一方面，考虑 Travelling Salesman问题。它陈述了包含一些给定节点的最短循环路径的问题。这个问题是NP-complete ，因此(据推测)无法在合理的时间内准确解决(至少对于一般情况而言)。然而，存在在合理的时间内运行的近似算法，产生的解决方案最多为 2*length(best route)(至少对于公制 TSP)，因此该算法的解决方案是不是精确的，只是一个近似值。