Ell*_* JJ 10 theory algorithm implementation
合法实用程序的哪些算法太复杂而无法实现？
让我说清楚:我不是在寻找像当前渐近最优矩阵乘法算法这样的算法,这种算法合理实现但是有一个常数使得它在实践中无用.我正在寻找可能具有实用价值的算法,但是编码非常困难,以至于它们从未实现过,只能在非常人为的设置中实现,或者只能用于非常特殊的应用程序.
同样受欢迎的是几乎不可能实现的算法,它们具有良好的渐近性但可能具有较差的实际性能.
Pet*_*der 14
我不认为有任何实际使用的算法从未编码,但有很多很难编码.
Chazelle的O(n)多边形三角剖分算法是渐近最优但很难编码的算法的一个例子.根据Skiena(算法设计手册的作者)的说法,"[该]算法实施起来毫无希望."
通常,三角测量和其他计算几何算法(例如3D凸包和Voronoi图)可能很难实现.很多诡计归结为处理浮点不准确性.
我不确定我知道你在问什么，但据我所知，标准的 NP 不完全计算相当困难，并且它们在很多方面都具有现实世界的价值，例如计算最有效的数据传输路径，或切割电路板，或将电力输送到电网......可能性有很多。