大自然的作品應該都稱得上是傑作。
--(古羅馬)西塞羅
啓發式算法廣泛地存在於求解NP難問題的數值求解算法中,它是根據目前的局部狀態下做出的一個決策,目的是爲了下一步的結果比當前的結果更加接近於理想的解。啓發式算法是一個基於直觀或經驗構造的算法,在可接受的花費下給出問題的一個可行解[1]。該類算法經常借鑑模擬自然界生物的覓食策略,如蟻羣算法,遺傳算法等。
演化算法也是模擬自然界生物的生存法則,它和啓發式算法的最主要的一點區別是,演化算法考慮多組解,然後從多組解中尋找合適的解;而啓發式算法只考慮一組解甚至是一組解的部分解(如禁忌搜索之於TSP問題)。當然,用於跳出局部最優的啓發式算法中的某些隨機性法則,同樣可以用到演化算法中。
和傳統算法確定性結果不同,由於在啓發式算法或者演化算法中使用了隨機策略,所以針對同一個問題,算法運行的結果一般不同。如果是最優問題,我們可以從多個結果中選取最好的那一個作爲問題的解。如果數值結果違反了約束條件的話,可以選取違反最小的那組解或者將解作平均(這是涉及到隨機或者概率方面經常使用的一種方法)。
後記:最近寫起東西來感覺力不從心,我把它理解成一個階段的瓶頸,堅持,堅持,再堅持……
參考資料:
[1]啓發式算法
https://baike.baidu.com/item/%E5%90%AF%E5%8F%91%E5%BC%8F%E7%AE%97%E6%B3%95/938987?fr=aladdin
[2] A*算法
https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/
[3] How to solve it: Modern Heristics, (美)Zbigniew Michalewicz, David B.Fogel著,曹宏慶等譯,中國水利水電出版社,2003年
领取专属 10元无门槛券
私享最新 技术干货