|
大英博物館算法
大英博物館算法或稱大英博物館技巧，即是以窮舉法，從最小的組合開始找答案。嚴格而言，這只是一個解題的概念而非一個可實作的算法，而且以窮舉法列出所有可能的話，運算時間和空間上並不划算。 大英博物館算法可以下例說，假設有一問題，希望得到一個最短的程式來解決，則求此程式的方法如下：先從長度為n=1開始，產生所有長度n的原始碼，再檢查當中有否可解決此問題的程式（因停機問題，此檢查過程不可能實作），若否，則測試n=2，如此類推，最終必會找到該最短程式，然而此方法卻須花費非常長的時間（大部分問題所須的時間比宇宙的生命還長）。 類似方法可用以證明例如優化、公式證明、辨別等問題可解還是不可解。 參見來源
|