文件名称：Exact Algorithms（英文版）
文件大小：4.22MB
文件格式：PDF
更新时间：2021-07-24 09:37:54
精确算法 NP完全
作者： Fedor V. Fomin , Dieter Kratsch 简介：很长一段时间，计算机科学家已经将快速和慢速算法区分开来。快速（或好）算法是在多项式时间内运行的算法，这意味着算法解决问题所需的步数受输入长度中的某些多项式的限制。所有其他算法都很慢（或很糟糕）。慢速算法的运行时间通常是指数级的。这本书是关于糟糕的算法。我们对指数时间算法感兴趣的原因有几个。我们大多数人都认为有许多自然问题无法通过多项式时间算法来解决。最着名和最古老的难题系列是NP完全问题的家庭。很可能没有多项式时间算法来解决这些难题，在最坏的情况下，指数运行时间是不可避免的。通过列举所有可能的解决方案，我可以在有限的时间内解决每个组合问题。即通过强力搜索。但蛮力搜索总是不可避免吗？绝对没有。早在20世纪60年代和70年代，人们就已经知道，一些NP完全问题可以比强力搜索更快地解决。三个经典示例是TRAVELING SALESMAN问题，MAXIMUM INDEPENDENT SET和COLORING的以下算法。