啟發(fā)式算法是相對(duì)于最優(yōu)化算法提出的。一個(gè)問(wèn)題的最優(yōu)算法求得該問(wèn)題每個(gè)實(shí)例的最優(yōu)解。那么你對(duì)啟發(fā)式算法了解多少呢?以下是由學(xué)習(xí)啦小編整理關(guān)于什么是啟發(fā)式算法的內(nèi)容，希望大家喜歡!

　　啟發(fā)式算法的概括內(nèi)容

　　計(jì)算機(jī)科學(xué)的兩大基礎(chǔ)目標(biāo)，就是發(fā)現(xiàn)可證明其執(zhí)行效率良好且可得最佳解或次佳解的算法。而啟發(fā)式算法則試圖一次提供一或全部目標(biāo)。 例如它常能發(fā)現(xiàn)很不錯(cuò)的解，但也沒(méi)辦法證明它不會(huì)得到較壞的解;它通?？稍诤侠頃r(shí)間解出答案，但也沒(méi)辦法知道它是否每次都可以這樣的速度求解。

　　有時(shí)候人們會(huì)發(fā)現(xiàn)在某些特殊情況下，啟發(fā)式算法會(huì)得到很壞的答案或效率極差，然而造成那些特殊情況的數(shù)據(jù)組合，也許永遠(yuǎn)不會(huì)在現(xiàn)實(shí)世界出現(xiàn)。因此現(xiàn)實(shí)世界中啟發(fā)式算法常用來(lái)解決問(wèn)題。啟發(fā)式算法處理許多實(shí)際問(wèn)題時(shí)通常可以在合理時(shí)間內(nèi)得到不錯(cuò)的答案。

　　有一類的通用啟發(fā)式策略稱為元啟發(fā)式算法(metaheuristic)，通常使用亂數(shù)搜尋技巧。他們可以應(yīng)用在非常廣泛的問(wèn)題上，但不能保證效率。

　　近年來(lái)隨著智能計(jì)算領(lǐng)域的發(fā)展，出現(xiàn)了一類被稱為超啟發(fā)式算法(Hyper-Heuristic Algorithm)的新算法類型。最近幾年，智能計(jì)算領(lǐng)域的著名國(guó)際會(huì)議(GECCO 2009, CEC 2010，PPSN 2010)分別舉辦了專門針對(duì)超啟發(fā)式算法的workshop或session。從GECCO 2011開(kāi)始，超啟發(fā)式算法的相關(guān)研究正式成為該會(huì)議的一個(gè)領(lǐng)域(self* search-new frontier track)。國(guó)際智能計(jì)算領(lǐng)域的兩大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分別安排了?？亟榻B與超啟發(fā)式算法有關(guān)的研究進(jìn)展。

　　啟發(fā)式算法的最短路徑

　　所謂的最短路徑問(wèn)題有很多種意思， 在這里啟發(fā)式指的是一個(gè)在一個(gè)搜尋樹(shù)的節(jié)點(diǎn)上定義的函數(shù)h(n)，用于評(píng)估從此節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最便宜的路徑。啟發(fā)式通常用于資訊充分的搜尋算法，例如最好優(yōu)先貪婪算法與A*。最好優(yōu)先貪婪算法會(huì)為啟發(fā)式函數(shù)選擇最低代價(jià)的節(jié)點(diǎn);A*則會(huì)為g(n) + h(n)選擇最低代價(jià)的節(jié)點(diǎn)，此g(n)是從起始節(jié)點(diǎn)到目前節(jié)點(diǎn)的路徑的確實(shí)代價(jià)。如果h(n)是可接受的(admissible)意即h(n)未曾付出超過(guò)達(dá)到目標(biāo)的代價(jià)，則A*一定會(huì)找出最佳解。

　　最能感受到啟發(fā)式算法好處的經(jīng)典問(wèn)題是n-puzzle。此問(wèn)題在計(jì)算錯(cuò)誤的拼圖圖形，與計(jì)算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠(yuǎn)時(shí)，使用了本算法。注意，上述兩條件都必須在可接受的范圍內(nèi)。

　　啟發(fā)式算法的運(yùn)算效能

　　任何的搜尋問(wèn)題中，每個(gè)節(jié)點(diǎn)都有b個(gè)選擇以及到達(dá)目標(biāo)的深度d，一個(gè)毫無(wú)技巧的算法通常都要搜尋bd個(gè)節(jié)點(diǎn)才能找到答案。啟發(fā)式算法借由使用某種切割機(jī)制降低了分叉率(branching factor)以改進(jìn)搜尋效率，由b降到較低的b'。分叉率可以用來(lái)定義啟發(fā)式算法的偏序關(guān)系，例如：若在一個(gè)n節(jié)點(diǎn)的搜尋樹(shù)上，h1(n)的分叉率較h2(n)低，則 h1(n) < h2(n)。啟發(fā)式為每個(gè)要解決特定問(wèn)題的搜尋樹(shù)的每個(gè)節(jié)點(diǎn)提供了較低的分叉率，因此它們擁有較佳效率的計(jì)算能力。

　　新啟發(fā)式算法

　　如何找到一個(gè)分叉率較少又通用的合理啟發(fā)式算法，已被人工智能社群深入探究過(guò)。 他們使用幾種常見(jiàn)技術(shù)：

　　部分問(wèn)題的解答的代價(jià)通常可以評(píng)估解決整個(gè)問(wèn)題的代價(jià)，通常很合理。例如一個(gè)10-puzzle拼盤(pán)，解題的代價(jià)應(yīng)該與將1到5的方塊移回正確位置的代價(jià)差不多。通常解題者會(huì)先建立一個(gè)儲(chǔ)存部份問(wèn)題所需代價(jià)的模式數(shù)據(jù)庫(kù)(pattern database)以評(píng)估問(wèn)題。 解決較易的近似問(wèn)題通?？梢阅脕?lái)合理評(píng)估原先問(wèn)題。例如曼哈頓距離是一個(gè)簡(jiǎn)單版本的n-puzzle問(wèn)題，因?yàn)槲覀兗僭O(shè)可以獨(dú)立移動(dòng)一個(gè)方塊到我們想要的位置，而暫不考慮會(huì)移到其他方塊的問(wèn)題。 給我們一群合理的啟發(fā)式函式h1(n),h2(n),...,hi(n)，而函式h(n) = max{h1(n),h2(n),...,hi(n)}則是個(gè)可預(yù)測(cè)這些函式的啟發(fā)式函式。 一個(gè)在1993年由A.E. Prieditis寫(xiě)出的程式ABSOLVER就運(yùn)用了這些技術(shù)，這程式可以自動(dòng)為問(wèn)題產(chǎn)生啟發(fā)式算法。ABSOLVER為8-puzzle產(chǎn)生的啟發(fā)式算法優(yōu)于任何先前存在的!而且它也發(fā)現(xiàn)了第一個(gè)有用的解魔術(shù)方塊的啟發(fā)式程式。
看過(guò)“啟發(fā)式算法的運(yùn)算效能”的人還看了：

1.基于區(qū)分鏈表的屬性約簡(jiǎn)改進(jìn)算法

2.電力系統(tǒng)分析論文

3.淺論量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度

4.資源成本管理論文:電子廢棄物逆向物流分析

5.自動(dòng)化專業(yè)面試自我介紹

6.大學(xué)生自我介紹中英文版