啟發式程式是實現啟發式搜尋算法的電腦程式。著名的啟發式搜尋程式有20世紀70年代初N．J．尼爾松給出的A算法、A’算法，以及後來的與或圖啟發式AO‘搜尋算法等。
基本介紹
- 中文名：啟發式程式
- 外文名：heuristic procedure
- 拼音：qǐ fā shì chéng xù
- 定義：實現啟發式搜尋算法的電腦程式
- 性質：局域性、試探性、針對性
- 套用學科：程式語言術語
概述,性質,啟發式程式的套用環節,知識表示,搜尋求解,啟發式搜尋策略,
概述
啟發式搜尋法是一種有效的重要方法，它不是依靠數學上的理論推導，而主要是靠一些總結出來的解決問題的有效經驗，如策略、法制、簡化步驟等來解決問題，把這些經驗性的東西寫成規則形式就是啟發式規則。
所謂搜尋過程是指一種利用局部性知識(如何從任一狀態向目標狀態靠近的知識)構造出全局性答案(問題的一個解或最佳解)的過程，系統內部事先沒有構造這種答案的全局性知識。反之，如果系統內部已經具有直接構造全局性答案的完整知識，則構造這個答案的過程不是搜尋過程。
1987年，比利時學者H.穆勒利用啟發式知識發展支持決策系統，開發了複雜柔性生產系統的生產計畫專家系統H11。
1995年，何棟中研究了啟發式搜尋法在確定坯一材關係中的套用，制訂了最佳化的剪下方案。
啟發式程式是實現啟發式搜尋算法的電腦程式。著名的啟發式搜尋程式有20世紀70年代初N．J．尼爾松給出的A算法、A‘算法，以及後來的與或圖啟發式AO‘搜尋算法等。
啟發式程式的套用包括兩個主要環節：一是知識表示；二是搜尋求解。
布魯納還提出了啟發式程式的某種特性：“啟發式程式實質上是達到解決難題的一種不嚴密的方法：啟發式程式常常使難題解決，但它提不出解決難題的保證。此外，算法也是解答問題的一種程式，如果進行得準確，它保證會經由一定的步驟發現問題的解答辦法——只要這個問題有解答之道。當算法的程式不明了的時候，往往可用啟發式程式，這是啟發式程式的優點之一。而且，即使有合用的算法時，啟發式程式也往往進度更快得多。另一方面，經常套用一般的啟發式規則——利用類比：
性質
啟發式程式具有3個性質：
（1）局部性：啟發式程式在求解某類問題的結果時．不一定保證是準確解或最佳解；
（2）試探性：啟發式程式求解問題時允許失誤而改用其他的方法；
（3）針對性：啟發式程式可以利用某些被解問題的特殊規律，大大簡化該問題的求解過程，具有較強的針對性。
依靠啟發，只須事先掌握把前提和結論聯繫起來的部分先驗信息，一般求解問題比較簡捷，在求解複雜問題時，可以更好地表現出人類智慧的特徵。在處理實際問題時．並不是單純地使用上述兩種方法中的某一種，而是交替地使用算法和啟發。一般是在戰略決策上較多地使用啟發，在戰術推進上較多地使用算法。
啟發式程式的套用環節
知識表示
解決一個問題的前提是對此問題進行準確的描述，也就是對此問題中涉及的知識進行適當的表示。因此，運用知識表示方法對問題的概念、特點做出準確描述，為所求解問題建立準確的模型具有重要的意義。
知識表示方法是關於如何描述事物的一組約定。問題求解過程主要是一個獲得並套用知識的過程，而知識必須有適當的表示才能在計算機中儲存、檢索、使用和修改。所謂知識的機器表示技術就是研究在計算機中如何用最適合的形式對問題求解過程中所需的各種知識進行組織，它與問題的性質和求解的方法有密切的關係。
狀態空間表示法是最基本的知識表示方法，是討論其他形式化方法和問題求解技術的出發點。下面對狀態、操作和狀態空間做一簡單介紹。
所謂狀態(state)，就是為描述某一類事物中各個不同事物之間的差異而引入的一組變數q(0)，q(1)，q(2)，…的有序組合。它常表示成矢量形式：Q=[q(0)，q(1)，q(2)，…]
式中，每個元素q(i)稱為分量，其相應的變域為[q(i)，b(i)]。狀態的維數可以是有限的，也可以是無限的。給定每個分量的值g(i，k)，就得到一個具體的狀態：Q(k)=[q(0，k)，q(1，k)，q(2，k)，…]
狀態還可以表示成多元數組[q(0)，q(1)，q(2)，…]或其他方便的形式。
引起狀態中的某些分量發生改變，從而使問題由一個具體狀態變化到另一個具體狀態的作用，稱為運算元(operator)，它可以是一個機械性的步驟、過程、操作或規則。運算元描述了狀態之間的關係。
問題的狀態空間(state space)是一個表示該問題的全部可能狀態及其相互關係的圖，一般是一個賦值有向圖，其中包括以下三方面的詳細說明：
S：問題可能有的初始狀態的集合；
F：操作的集合；
G：目標狀態的集合。
所以狀態空間常記為三重序元(S，F，G)。在狀態空間表示法中，問題求解過程轉化為在圖中尋找從初始狀態
出發到達目標狀態
的路徑問題，也就是尋找操作序列口的問題。所以狀態空間中的解也常記為三重序元(
，a，
)，它包含了以下三方面的詳細說明：
a：把
變換成
的有限操作序列。
搜尋求解
所謂搜尋過程是指一種利用局部性知識(如何從任一狀態向目標狀態靠近的知識)構造出全局性答案(問題的一個解或最佳解)的過程，系統內部事先沒有構造這種答案的全局性知識。反之，如果系統內部已經具有直接構造全局性答案的完整知識，則構造這個答案的過程不是搜尋過程。例如盲人爬山時，他不知山在何方，向何處走(全局性答案)，只知道每步都選最陡的方向前進(局部性知識)，這個過程是搜尋；而利用解一元一次方程的算法，可以直接求出結果，這個過程不是我們所討論的搜尋問題，或稱為零步搜尋問題。
搜尋技術是套用十分廣泛的機械化推理技術之一，特別是其中的啟發式搜尋原理(heuristic search theory)，它可以幫助我們利用部分狀態空間來求解問題，這樣就大大提高了解題效率。
傳統的基本搜尋策略都是非啟發式的搜尋，其控制性知識僅僅是基本搜尋策略，沒有包含輔助性策略，例如被解問題的解的任何特性。基本搜尋策略的優點是控制性知識比較簡單，但它原則上都要求知道問題的全部狀態空間圖，其搜尋效率不高，不便於許多複雜問題的求解。為了提高搜尋效率，人們研究了許多有較強啟發能力的搜尋策略。
啟發式搜尋的基本思想是在控制性知識中增加關於被解問題的解的某些特性，以便指導搜尋朝最有希望的方向前進。所以啟發式搜尋與基本搜尋不同，從原則上講只需要知道問題的部分狀態空間就可以求解該問題，搜尋效率較高。通過後面的討論可以看出，正是控制性知識中的啟發信息，彌補了由於略去部分狀態空間帶來的信息損失。
啟發式搜尋策略
一般而言，問題的求解過程表現為從初始狀態（初始可行解）開始，不斷搜尋尋找目標狀態（最終最佳化解）的過程。由於求解問題的過程中求解條件的不確定性和不完備性，造成可能的分支有很多，從而使得眾多求解路徑構成了一個圖，即問題解的狀態空間。問題的求解實際上就是狀態空間搜尋過程。
常用的狀態空間搜尋策略有深度優先搜尋策略和廣度優先搜尋策略。廣度優先搜尋策略是從初始狀態一層一層向下找，直到找到目標解為止。深度優先搜尋策略是按照一定的順序先查找完一個分支，再查找另一個分支，以至找到目標解為止。然而廣度優先搜尋和深度優先搜尋都是在一個給定的狀態空間中進行窮舉搜尋，如果問題狀態空間非常大，且不可預測時，則深度優先搜尋和廣度優先搜尋效率太低，甚至不可完成。
啟發式搜尋策略是在問題狀態空間的搜尋中首先對每一個可能的搜尋位置進行評估，得到一個最好的位置，再從這個位置出發進行下一步搜尋，直到找到目標解，從而省略大量的搜尋路徑，提高了搜尋效率。
在啟發式搜尋中，對某個位置的評估是十分重要的。採用不同的評估函式可以有不同的效果，其一般形式如下：
其中
是節點
的估價函式，
是在狀態空間中從初始節點到節點n的實際代價，代表了搜尋廣度的優先趨勢。
是從節點n到目標節點最佳路徑的估計代價，它體現了搜尋的啟發信息。
設
為解的可行域，啟發式搜尋算法的基本思想是從一個初始解
開始，然後運用局部搜尋策略，持續地在當前解
的鄰域
中搜尋比
更優的解。若找到比
更優的解，就用這個解取代
，成為當前解，再對當前解繼續重複上述過程，直到當前解優於其鄰域中的所有解為止。
從PSO算法的仿生最佳化原理上看，PSO算法是一種啟發式算法。因為PSO算法是通過對某種社會性群體搜尋現象的簡化模擬而設計的。PSO算法搜尋的每一步都是在粒子自身歷史經驗和群體中最優粒子的指導（或啟發）下進行搜尋的。PSO算法並沒有從原理上說明這種算法為什麼有效，以及它的適用範圍，因此PSO算法特點也符合啟發式算法的定義：啟發式算法是一種技術，這種技術使得在可接受的計算費用內去尋找最好的解，但不一定能保證所得解的可行性和最優性，甚至在多數情況下，無法闡述所得解與最優解的近似程度。
