<分区>
有哪些合法实用的算法过于复杂而无法实现？
让我明确一点:我不是在寻找像当前渐近最优矩阵乘法算法这样的算法，这种算法实现起来很合理，但有一个常数，因此在实践中毫无用处。我正在寻找看似具有实用值(value)但难以编码以致于它们从未被实现、仅在极端人工设置中实现或仅针对非常特殊用途的应用程序实现的算法。
也欢迎具有良好渐近性但实际性能可能较差的几乎不可能实现的算法。
<分区>
有哪些合法实用的算法过于复杂而无法实现？
让我明确一点:我不是在寻找像当前渐近最优矩阵乘法算法这样的算法，这种算法实现起来很合理，但有一个常数，因此在实践中毫无用处。我正在寻找看似具有实用值(value)但难以编码以致于它们从未被实现、仅在极端人工设置中实现或仅针对非常特殊用途的应用程序实现的算法。
也欢迎具有良好渐近性但实际性能可能较差的几乎不可能实现的算法。
最佳答案
我认为没有从未编码过的具有实际用途的算法，但有很多算法很难编码。
渐近最优但很难编码的算法示例是 Chazelle's O(n) polygon triangulation algorithm .根据 Skiena(《算法设计手册》的作者)的说法，“[该]算法实现起来毫无希望。”
一般来说，三角剖分和其他计算几何算法(例如 3D 凸包和 Voronoi 图)实现起来可能会很棘手。许多技巧归结为处理浮点不准确。
关于algorithm - 强大的算法过于复杂而无法实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4771736/