关于算法的理论和实践的gap
关于算法的理论和实践的gap,一直是算法研究中常被提及的话题。大部分人,包括不少本身研究算法理论的研究人员,认为算法理论确实没有很好的发挥其本应该有的功能。我自己理解主要应该有解释功能(解释问题难度和算法行为)和引导功能(引导实践算法设计)。 从解释功能讲,NP复杂性理论指出很多问题是难的(假设P!=NP),而且有许多悲观结论,典型的一个就是SAT(布尔可满足性问题,第一个被证明的NP完全问题)的强指数时间假设,而且目前SAT问题依然没有突破最平凡的界2^n. 再比如,最大团问题不存在有意义的近似算法。。。 但现实中,SAT求解器可以解决许多工业几十万甚至百万变量级别的SAT实例,最大团问题也没见过难到无法找到一定质量近似解的程度。(NP复杂性理论说明理论上存在很难的实例,但是没法构造出实例。现实中可能不会遇到“那么难”的实例。) 再从引导功能或说使用功能讲,算法理论中一个最出名的范式就是近似算法。不过那么多年过去,真的有什么近似算法在实践中发挥重要作用吗?应该说如果有,也是极其罕见的。随机算法,实践中的随机算法似乎也很少经典的理论算法那些idea。非要说,random walk算一个...







