近似算法寻找的是接近，但并不一定要是完全正确的答案。总的来说就是一个权衡：牺牲结果的准确性，换取更短的运行时间。
当完全正确的结果并不必要，而较好的答案就可以接受时，就可以考虑以准确性为代价来提高解决问题的速度，旅行商问题（TSP）就是这样一个典例。旅行商问题是指，给定一个需要走访的城市集合以及每对城市之间的距离，如何找到一条最短的旅游路线：从某个城市开始，走遍每一个城市，且每个只经过一次，最后回到这个城市。这是计算机科学所有问题中研究最深入的问题之一，不太可能存在一个多项式复杂度的算法能够解决TSP问题。也就是说，没有算法能够以O(nK)的复杂度解决，其中K是固定的某个整数。它属于NP-hard问题，人们坚信这类问题天生就很难找到完全正确的答案。
但是，假设各城市间的距离满足三角形不等式（对于a、b、c三个点来说，a到b之间的距离不会大于a到c的距离加上c到b的距离）。Christofides（1976）设计了一种有效的解决算法能够找到一条较短路径，而这条路径不会长过最短路径50%。