在数据结构和算法中,“精确图算法”是什么意思?你能给我一些例子吗?
最佳答案
我想它指的是算法是否产生了一个结果,对于给定的问题是最优的,或者它是否产生“只是”一个近似的结果。
例如,如果您在图表中查找 shortest path从一个节点到另一个节点,有一堆算法( Dijkstra , Floyd-Warshall ,......你的名字)可以准确地解决问题,即它们产生两个给定节点之间的最短路径。
另一方面,考虑 Travelling Salesman问题。它陈述了包含一些给定节点的最短循环路径的问题。这个问题是NP-complete ,因此(据推测)无法在合理的时间内准确解决(至少对于一般情况而言)。然而,存在在合理的时间内运行的近似算法,产生的解决方案最多为 2*length(best route)
(至少对于公制 TSP),因此该算法的解决方案是不是精确的,只是一个近似值。
关于algorithm - 精确图算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3210119/