algorithm - 精确图算法

原文 标签 algorithm data-structures graph

在数据结构和算法中,“精确图算法”是什么意思你能给我举几个例子吗?

最佳答案

我想它是指算法是否产生一个结果,它对于一个给定的问题是最优的,或者如果它产生一个近似的结果。
例如,如果您在图中查找从一个节点到另一个节点的shortest path,则有一组算法(DijkstraFloyd-Warshall你可以给它们起名字)精确地解决问题,也就是说,它们在两个给定的节点之间产生一条最短的路径。
另一方面,考虑Travelling Salesman问题。它提出了一个包含给定节点的最短圆形路径问题。这个问题是NP-complete,因此(假设)不能在合理的时间内完全解决(至少对于一般情况)然而,在合理的时间内存在近似算法,其产生的解最多为2*length(best route)(至少对于度量TSP),因此该算法的解不是精确的,而是近似的。

相关文章:

python - 我的遗传算法有什么问题

algorithm - 将数字平均分为12个整数

algorithm - 寻找最小的比例因子,以便从一组 double 数中得到每个数字的十分之一

algorithm - 有效的数据结构,可计算序列的平均值

java - 使用csv中的数据在html中创建图形

python - 在python中走简单的树

iphone - Iphone中的股票图?

algorithm - 当数据包丢失时,TCP慢启动与拥塞避免

c++ - 读取结构定义的二进制文件

data-structures - 使用交换!更新Clojure(Script)原子中的映射 vector