什麼是啟發式？什麼是産生式？

一般而言，​機器常常被設定從已知推未知，而人們不時會從未知（假設）推未知，特殊情形下也有從未知推已知的，這些推導中常見的有産生式和啟發式，那麼究竟什麼是産生式和啟發式呢？！下面會進行簡要地分析和說明。

啟發式算法（heuristic algorithm)是相對于最優化算法提出的。一個問題的最優算法求得該問題每個執行個體的最優解。啟發式算法可以這樣定義：一個基于直覺或經驗構造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個執行個體的一個可行解，該可行解與最優解的偏離程度一般不能被預計。

計算機科學的兩大基礎目标，就是發現可證明其執行效率良好且可得最佳解或次佳解的算法。而啟發式算法則試圖一次提供一或全部目标。 例如它常能發現很不錯的解，但也沒辦法證明它不會得到較壞的解；它通常可在合理時間解出答案，但也沒辦法知道它是否每次都可以這樣的速度求解。

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

有一類的通用啟發式政策稱為元啟發式算法（metaheuristic），通常使用亂數搜尋技巧。他們可以應用在非常廣泛的問題上，但不能保證效率。

近年來随着智能計算領域的發展，出現了一類被稱為超啟發式算法（Hyper-Heuristic Algorithm）的新算法類型。最近幾年，智能計算領域的著名國際會議（GECCO 2009, CEC 2010，PPSN 2010）分别舉辦了專門針對超啟發式算法的workshop或session。從GECCO 2011開始，超啟發式算法的相關研究正式成為該會議的一個領域（self* search-new frontier track）。國際智能計算領域的兩大著名期刊Journal of Heuristics和Evolutionary Computation也在2010年和2012年分别安排了專刊，着重介紹與超啟發式算法有關的研究進展。

最短路徑

所謂的最短路徑問題有很多種意思， 在這裡啟發式指的是一個在一個搜尋樹的節點上定義的函數h(n)，用于評估從此節點到目标節點最便宜的路徑。啟發式通常用于資訊充分的搜尋算法，例如最好優先貪婪算法與A。最好優先貪婪算法會為啟發式函數選擇最低代價的節點；A則會為g(n) + h(n)選擇最低代價的節點，此g(n)是從起始節點到目前節點的路徑的确實代價。如果h(n)是可接受的（admissible）意即h(n)未曾付出超過達到目标的代價，則A*一定會找出最佳解。

最能感受到啟發式算法好處的經典問題是n-puzzle。此問題在計算錯誤的拼圖圖形，與計算任兩塊拼圖的曼哈頓距離的總和以及它距離目的有多遠時，使用了本算法。注意，上述兩條件都必須在可接受的範圍内。

運算效能

任何的搜尋問題中，每個節點都有b個選擇以及到達目标的深度d，一個毫無技巧的算法通常都要搜尋bd個節點才能找到答案。啟發式算法借由使用某種切割機制降低了分叉率(branching factor)以改進搜尋效率，由b降到較低的b'。分叉率可以用來定義啟發式算法的偏序關系，例如：若在一個n節點的搜尋樹上，h1(n)的分叉率較h2(n)低，則 h1(n) < h2(n)。啟發式為每個要解決特定問題的搜尋樹的每個節點提供了較低的分叉率，是以它們擁有較佳效率的計算能力。

新算法

如何找到一個分叉率較少又通用的合理啟發式算法，已被人工智能社群深入探究過。 他們使用幾種常見技術：

部分問題的解答的代價通常可以評估解決整個問題的代價，通常很合理。例如一個10-puzzle拼盤，解題的代價應該與将1到5的方塊移回正确位置的代價差不多。通常解題者會先建立一個儲存部份問題所需代價的模式資料庫(pattern database)以評估問題。 解決較易的近似問題通常可以拿來合理評估原先問題。例如曼哈頓距離是一個簡單版本的n-puzzle問題，因為我們假設可以獨立移動一個方塊到我們想要的位置，而暫不考慮會移到其他方塊的問題。 給我們一群合理的啟發式函式h1(n),h2(n),...,hi(n)，而函式h(n) = max{h1(n),h2(n),...,hi(n)}則是個可預測這些函式的啟發式函式。 一個在1993年由A.E. Prieditis寫出的程式ABSOLVER就運用了這些技術，這程式可以自動為問題産生啟發式算法。ABSOLVER為8-puzzle産生的啟發式算法優于任何先前存在的！而且它也發現了第一個有用的解魔術方塊的啟發式程式。

産生式 由條件和動作組成的指令，即所謂的條件—活動規則，（condition—action 簡稱C-A規則）。

在計算機中指Tiger編譯器将源程式經過詞法分析（Lexical Analysis）和文法分析（Syntax Analysis）後得到的一系列符合文法規則（Backus-Naur Form，BNF）的語句，包含在由Andrew W.Appel在Modern Compiler Implementation（虎書）一書中首次提出的”Tiger編譯程式“中。

産生式是表征程式性知識的最小機關，是指人腦中貯存的一系列如果—那麼形式表示的規則。一個産生式是一個由條件和動作組成的指令，即所謂的條件—活動規則，（condition—action 簡稱C-A規則）。

“産生式”這一術語是在1943年由美國數學家E.L.Post首先提出的，它根據串替代規則提出了一種稱為Post機的計算模型，模型中的每一條規則稱為産生式。

産生式通常用于表示具有因果關系的知識，其基本形式為：P→Q 或者 IF P THEN Q

人類的認知模式常常是啟發式，機器的計算模式往往是産生式。

原文釋出時間：2019-12-06

本文作者：人機與認知實驗室

本文來自阿裡雲雲栖号&雲栖社群合作夥伴“

人機與認知實驗室

”，了解相關資訊可以關注“

”