关于算法的理论和实践的gap,一直是算法研究中常被提及的话题。大部分人,包括不少本身研究算法理论的研究人员,认为算法理论确实没有很好的发挥其本应该有的功能。我自己理解主要应该有解释功能(解释问题难度和算法行为)和引导功能(引导实践算法设计)。 从解释功能讲,NP复杂性理论指出很多问题是难的(假设P!=NP),而且有许多悲观结论,典型的一个就是SAT(布尔可满足性问题,第一个被证明的NP完全问题)的强指数时间假设,而且目前SAT问题依然没有突破最平凡的界2^n. 再比如,最大团问题不存在有意义的近似算法。。。 但现实中,SAT求解器可以解决许多工业几十万甚至百万变量级别的SAT实例,最大团问题也没见过难到无法找到一定质量近似解的程度。(NP复杂性理论说明理论上存在很难的实例,但是没法构造出实例。现实中可能不会遇到“那么难”的实例。) 再从引导功能或说使用功能讲,算法理论中一个最出名的范式就是近似算法。不过那么多年过去,真的有什么近似算法在实践中发挥重要作用吗?应该说如果有,也是极其罕见的。随机算法,实践中的随机算法似乎也很少经典的理论算法那些idea。非要说,random walk算一个。 如果我们认为算法理论纯粹是数学理论(游戏),这个辩论就可以打住,也并非不可,各自发展。但是如果大家承认,算法最终是为了解决问题,理论毕竟还是要解释现实或者引导实践,那么我们就会思考,这么多年的算法理论,是否有很大轨迹依赖的成分(毕竟是在电子计算机被发明之前就有大O),而导致没有面对现实,越来越脱节。 算法理论和实践的主要研究对象不同,理论考虑极其简单的算法还有只剩下定义的问题,而计算机上的实际计算是程序和实例。有没有更具体的算法理论,可以解释为什么很多工业实例是容易的,也可能给出一些真正可以对实践有用的算法思路? 最近几年看到研究算法理论的人也在思考这个问题,期待早日见到突破。不过,也许大家特别是年轻人都有发论文的需要,我见到的算法理论方面的paper,依然是我行我素,什么时候看到具体的算法理论呢? 想到Knuth写过具体数学了,期待有人去创造一个具体TCS方向。
– 蔡少伟,中国科学院软件研究所 研究员 博导
https://weibo.com/7743147596/ODtFfBgE6
未经允许不得转载:岩猫星空网 » 关于算法的理论和实践的gap