近似算法 编辑
近似算法是计算机科学中算法研究的一个重要方向。所谓“近似”，就是指结果不一定是最优的，但是也在可以承受的范围内，而且可以比精确求解消耗更少的资源。这里的资源是计算复杂性理论中的标准，可以是时间，空间或者询问次数等。
1
相关
克里斯托菲德斯算法 是旅行推销员问题在度量空间上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。尼科斯·克里斯托菲德斯 于1976年首次发表了这个算法，故以他的名字命名之。 截至2017年 ，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。
在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的道路。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路问题可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P/NP问题，否则对应于任意的图，没有办法在时间复杂度内解决该问题。更强的困难结果表明这个问题也是近似算法的。但是，有一个线性时间的方法可以用于有向无环图，这对于发现调度问题中的关键路径有重要的作用。
在计算机科学领域，多项式时间近似算法是一种用于最佳化问题的近似算法。
克里斯托菲德斯算法 是旅行推销员问题在度量空间上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。尼科斯·克里斯托菲德斯 于1976年首次发表了这个算法，故以他的名字命名之。 截至2017年 ，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。
克里斯托菲德斯算法 是旅行推销员问题在度量空间上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。尼科斯·克里斯托菲德斯 于1976年首次发表了这个算法，故以他的名字命名之。 截至2017年 ，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。