大英博物館演算法
外觀
![本頁使用了標題或全文手工轉換](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)