2008年12月15日 星期一

heuristic

heuristic rule 經驗法則

wiki, 啟發法,啟發法經常用於模式串識別與匹配,web頁面搜索

heuristic algorithm 啟發式演算法

有時候人們會發現在某些特殊情況下,啟發式演算法會得到很壞的答案或效率極差,然而造成那些特殊情況的資料結構,也許永遠不會在現實世界出現。因此現實世界中啟發式演算法很常用來解決問題。啟發式演算法處理許多實際問題時通常可以在合理時間內得到不錯的答案。

這真是個神奇的字,誰能告訴我他真正的意思.........

2 則留言:

線代離散助教(wynne) 提到...

我記得我剛認識這個字時也是一頭霧水...

Heuristic alg (or heuristics)指的是比較像是策略式的演算法, 這個字很難解釋, 但它的概念其實很簡單, 它指的是那些nondeterministic的alg, 也就是爲了確保它的實行效率不會太差, 所以它所求得的解通常會接近目標, 但卻不保證能獲得最佳解, 通常是對於比較難的, 像是NP-Complete的問題, 才會需要有heuritics

爲了要使難的問題在polynomial time可解, 常見的nondeterministic polynomial time alg有randomized和approximation alg等, 但heuritics通常因為不像上述兩者有其特定的雛型規範, 所以才沒有被歸類在其中

一般在AI領域裡, 因為要解的問題都是難題, 所以很容易出現這種alg, 譬如假設我們寫了一個下chess的alg, 這就可以稱為heuristic algorithm, 因為我們絕對不會想真的去跑出整盤棋的decision tree來決定每一步最佳的下法, 而是要在algorithm裡頭去implement一些方法, 使得我們可以根據一些目前的棋盤狀況, 來推算出那"看起來是最好的"一步

Daniel 提到...

果然很清楚~

樓上不愧是強者我同學

就甘心~謝啦^^