了解啟發(fā)式搜索領(lǐng)域及其在人工智能上的應(yīng)用。本文作者展示了他們?nèi)绾纬晒τ?Java 實現(xiàn)了最廣為使用的啟發(fā)式搜索算法。他們的解決方案利用一個替代的 Java 集合框架，并使用最佳實踐來避免過多的垃圾收集。

通過搜尋可行解決方案空間來解決問題是人工智能中一項名為狀態(tài)空間搜索 的基本技術(shù)。 啟發(fā)式搜索 是狀態(tài)空間搜索的一種形式，利用有關(guān)一個問題的知識來更高效地查找解決方案。啟發(fā)式搜索在各個領(lǐng)域榮獲眾多殊榮。在本文中，我們將向您介紹啟發(fā)式搜索領(lǐng)域，并展示如何利用 Java 編程語言實現(xiàn) A*，即最廣為使用的啟發(fā)式搜索算法。啟發(fā)式搜索算法對計算資源和內(nèi)存提出了較高的要求。我們還將展示如何避免昂貴的垃圾收集，以及如何利用一個替代的高性能 Java 集合框架 (JCF)，通過這些改進(jìn) Java 實現(xiàn)。本文的所有代碼都可以從 下載 部分獲得。

啟發(fā)式搜索

計算機科學(xué)中的許多問題可用一個圖形數(shù)據(jù)結(jié)構(gòu)表示，其中圖形中的路徑表示潛在的解決方案。查找最優(yōu)解決方案需要找到一個最短路徑。例如，以自主視頻游戲角色為例。角色做出的每個動作都與圖形中的一個邊緣相對應(yīng)，而且角色的目標(biāo)是找到最短路徑，與對手角色交手。

深度優(yōu)先 搜索和廣度優(yōu)先 搜索等算法是流行的圖形遍歷算法。但它們被視為非啟發(fā)式 算法，而且常常受到它們可以解決的問題規(guī)模的嚴(yán)格限制。此外，不能保證深度優(yōu)先搜索能找到最優(yōu)解決方案（或某些情況下的任何解決方案），可以保證廣度優(yōu)先搜索僅能在特殊情況下找到最優(yōu)解決方案。相比之下，啟發(fā)式搜索是一種提示性 搜索，利用有關(guān)一個問題的知識，以啟發(fā)式方式進(jìn)行編碼，從而更高效地解決問題。啟發(fā)式搜索可以解決非啟發(fā)式算法無法解決的很多難題。

視頻游戲?qū)ぢ肥菃�發(fā)式搜索的一個受歡迎的領(lǐng)域，它還可以解決更復(fù)雜的問題。2007 年舉行的無人駕駛汽車比賽 “DARPA 城市挑戰(zhàn)賽” 的優(yōu)勝者就利用了啟發(fā)式搜索來規(guī)劃平坦的、直接的可行使路線。啟發(fā)式搜索在自然語言處理中也有成功應(yīng)用，它被用于語音識別中的文本和堆棧解碼句法解析。它在機器人學(xué)和生物信息學(xué)領(lǐng)域也有應(yīng)用。與傳統(tǒng)的動態(tài)編程方法相比較，使用啟發(fā)式搜索可以使用更少的內(nèi)存更快地解決多序列比對 (Multiple Sequence Alignment, MSA)，這是一個經(jīng)過深入研究的信息學(xué)問題。

通過 Java 實現(xiàn)啟發(fā)式搜索

Java 編程語言不是實現(xiàn)啟發(fā)式搜索的一種受歡迎的選擇，因為它對內(nèi)存和計算資源的要求很高。出于性能原因，C/C++ 通常是首選語言。我們將證明 Java 是實現(xiàn)啟發(fā)式搜索的一種合適的編程語言。我們首先表明，在解決受歡迎的基準(zhǔn)問題集時，A* 的 textbook 實現(xiàn)確實很緩慢，并且會耗盡可用內(nèi)存。我們通過重訪一些關(guān)鍵實現(xiàn)細(xì)節(jié)和利用替代的 JCF 來解決這些性能問題。

很多這方面的工作都是本文作者合著的一篇學(xué)術(shù)論文中發(fā)表的作品的一個擴展。盡管原作專注于 C/C++  編程，但在這里，我們展示了適用于 Java 的許多同樣的概念。

廣度優(yōu)先搜索

熟悉廣度優(yōu)先搜索（一個共享許多相同概念和術(shù)語的更簡單的算法）的實現(xiàn)，將幫助您理解實現(xiàn)啟發(fā)式搜索的細(xì)節(jié)。我們將使用廣度優(yōu)先搜索的一個以代理為中心 的視圖。在一個以代理為中心的視圖中，代理據(jù)說處于某種狀態(tài)，并且可從該狀態(tài)獲取一組適用的操作。應(yīng)用操作可將代理從其當(dāng)前狀態(tài)轉(zhuǎn)換到一個新的后繼 狀態(tài)。該視圖適用于多種類型的問題。

廣度優(yōu)先搜索的目標(biāo)是設(shè)計一系列操作，將代理從其初始狀態(tài)引導(dǎo)至一個目標(biāo)狀態(tài)。從初始狀態(tài)開始，廣度優(yōu)先搜索首先訪問最近生成的狀態(tài)。所有適用的操作在每個訪問狀態(tài)都可以得到應(yīng)用，生成新的狀態(tài)，然后該狀態(tài)被添加到未訪問狀態(tài)列表（也稱為搜索的前沿）。訪問狀態(tài)并生成所有后繼狀態(tài)的過程被稱為擴展 該狀態(tài)。

您可以將該搜索過程看作是生成了一個樹：樹的根節(jié)點表示初始狀態(tài)，子節(jié)點由邊緣連接，該邊緣表示用于生成它們的操作。圖 1 顯示該搜索樹的一個圖解。白圈表示搜索前沿的節(jié)點。灰圈表示已展開的節(jié)點。

圖 1. 二叉樹上的廣度優(yōu)先搜索順序

搜索樹中的每一個節(jié)點表示某種狀態(tài)，但兩個獨特的節(jié)點可表示同一狀態(tài)。例如，搜索樹中處于不同深度的一個節(jié)點可以與樹中較高層的另一個節(jié)點具有同樣的狀態(tài)。這些重復(fù) 節(jié)點表示在搜索問題中達(dá)到同一狀態(tài)的兩種不同方式。重復(fù)節(jié)點可能存在問題，因此必須記住所有受訪節(jié)點。

標(biāo)簽： Java 啟發(fā)式搜索 人工智能 

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。