大英博物馆算法

✍ dations ◷ 2025-07-27 20:24:49 #算法

大英博物馆算法或称大英博物馆技巧,即是以穷举法,从最小的组合开始找答案。严格而言,这只是一个解题的概念而非一个可实现的算法,而且以穷举法列出所有可能的话,运算时间和空间上并不划算。

大英博物馆算法可以下例说,假设有一问题,希望得到一个最短的程序来解决,则求此程序的方法如下:先从长度为n=1开始,产生所有长度n的源代码,再检查当中有否可解决此问题的程序(因停机问题,此检查过程不可能实现),若否,则测试n=2,如此类推,最终必会找到该最短程序,然而此方法却须花费非常长的时间(大部分问题所须的时间比宇宙的生命还长)。

类似方法可用以证明例如优化、公式证明、辨别等问题可解还是不可解。

相关

  • 附着语素附着语素(英语:Clitic;源自古希腊语:ἐγκλιτικός“倾斜”)是一个词法学概念,上指在句法作用有如一自由词素,在语音学上却表现出规范语素特性的语素,其发音必须依附于前面或
  • τ子τ子(tauon),又称陶子、濤子,是带负电荷、自旋1⁄2的基本粒子,标记为τ−,由马丁·佩尔实验团队于1975年发现。τ子、电子、μ子与对应的三种中微子,都归属于轻子;τ子是第三代轻子,
  • 龙须菜龙须菜可能指下列可食蔬菜之一:
  • 盎博罗削圣盎博罗削(拉丁语:Sanctus Ambrosius,意大利语:Sant'Ambrogio,英文中常作 Ambrose,约340年-397年4月4日),罗马公教(天主教)神职人员,任米兰主教,4世纪基督教著名的拉丁教父之一。他也是
  • 斐波那契数列斐波那契数列(意大利语:Successione di Fibonacci),又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列。在数学上,斐波那契数列是以递归的方法来定义:用文字来说,就是斐波
  • 大灰厂组大灰厂组是位于中国北京的下白垩世地层,1933年由谢家荣命名。该地层以砂质砾岩、砂岩、泥岩以及黄绿、灰黑色页岩为主。
  • 各国军力排名列表各国军力排名列表列出各国在单一军力指标的排名及在世界主要军力排名中的排名。以下是2017年的排名:瑞士信贷发表的军力强度指数排名,其衡量方式与知名军力排行网站公布的环球
  • 庄淑旗庄淑旗(1920年11月26日-2015年2月4日),生于台湾台北市,汉方传统医学及保健推广工作者,食疗养生专家。是台湾首位女性汉医师,台湾首位女性汉医博士。庄淑旗父亲庄阿炎祖籍广东梅县,15
  • 王海丁王海丁(1985年-),中国江苏省南京市公安局江宁分局网安大队副大队长,是江宁分局官方新浪微博“江宁公安在线”的运营者,昵称“江宁婆婆”,因其风趣幽默、贴合网民心理的发言风格而在
  • 工作集工作集(英语:Working set)是一个计算机科学术语,定义为在一个特定的时间段内一个进程所需要的内存。Peter Denning(英语:Peter_J._Denning)将一个进程在时间t的工作集