大英博物馆算法
外观
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
图与树 搜索算法 |
---|
分类 |
相关主题 |
大英博物馆算法或称大英博物馆技巧,即是以穷举法,从最小的组合开始找答案。严格而言,这只是一个解题的概念而非一个可实现的算法,而且以穷举法列出所有可能的话,运算时间和空间上并不划算。
大英博物馆算法可以下例说,假设有一问题,希望得到一个最短的程序来解决,则求此程序的方法如下:先从长度为n=1开始,产生所有长度n的原始码,再检查当中有否可解决此问题的程序(因停机问题,此检查过程不可能实现),若否,则测试n=2,如此类推,最终必会找到该最短程序,然而此方法却须花费非常长的时间(大部分问题所须的时间比宇宙的生命还长)。
类似方法可用以证明例如优化、公式证明、辨别等问题可解还是不可解。
参见
[编辑]来源
[编辑]- 原文来自Paul E. Black所著、公共著作权之NIST文件British Museum technique(辑录于Dictionary of Algorithms and Data Structures)