人工智能搜索技術論文

人工智能搜索技術論文

　　人工智能的核心問題及啟發(fā)式搜索函數的基本概念，介紹了4種經典問題啟發(fā)式搜索函數的選擇及其研究中遇到的難題，并從中求解來探討解決問題的思路。以下是學習啦小編整理的人工智能搜索技術論文的相關資料，歡迎閱讀!

　　人工智能搜索技術論文篇一

　　摘要：闡述了人工智能的核心問題及啟發(fā)式搜索函數的基本概念，介紹了4種經典問題啟發(fā)式搜索函數的選擇及其研究中遇到的難題，并從中求解來探討解決問題的思路。

　　關鍵詞：人工智能;問題求解;啟發(fā)式搜索函數

　　中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)08-10ppp-0c

　　人工智能問題廣義地說，都可以看作是一個問題求解過程，因此問題求解是人工智能的核心問題，它通常是通過在某個可能的解答空間中尋找一個解來進行的。在問題求解過程中，人們所面臨的大多數現實問題往往沒有確定性的算法，通常需要用搜索算法來解決。目標和達到目標的一組方法稱為問題，搜索就是研究這些方法能夠做什么的過程。問題求解一般需要考慮兩個基本問題：首先是使用合適的狀態(tài)空間表示問題，其次是測試該狀態(tài)空間中目標狀態(tài)是否出現。

　　1 什么是啟發(fā)式搜索函數

　　在人工智能中有很大一類問題的求解技術依賴于搜索。啟發(fā)式方法就是采用有利于問題自身特征信息來引導搜索過程的方法，在學生學習過程中啟發(fā)式函數的選取至關重要，決定整個算法的效率與成敗。啟發(fā)式搜索通常用于兩種不同類型的問題：(1)前向推力和(2)反向推理。前向推理一般用于狀態(tài)空間的搜索。在前向推理中，推理是從預定義的初始狀態(tài)出發(fā)向目標狀態(tài)反向方向執(zhí)行;反向推理一般用于問題歸約中。在反向推理中，推理是從給定的目標狀態(tài)向初始狀態(tài)執(zhí)行。

　　用來評估節(jié)點重要性的函數稱為評估函數。評估函數f(x)定義為從初始節(jié)點S0出發(fā)，約束地經過節(jié)點x到達目標節(jié)點Sg的所有路徑中最小路徑代價的估計值。其一般形式為：

　　其中，g(x)表示從初始節(jié)點S0到節(jié)點x的實際代價;h(x)表示從x到目標節(jié)點Sg的最優(yōu)路徑的評估代價，它體現了問題的啟發(fā)式信息，其形式要根據問題的特征確定，h(x)稱為啟發(fā)式函數。因此，啟發(fā)式方法把問題狀態(tài)的描述轉換成了對問題解決程度的描述，這一程度用評估函數的值來表示。

　　2 滑動積木游戲啟發(fā)式搜索函數

　　滑動積木塊游戲的棋盤結構及某一種將牌的初始排列結構如下：

　　其中B表示黑色將牌，W表示白色將牌，E表示空格。游戲的規(guī)定走法是：

　　(1)任意一個將牌可以移入相鄰的空格，規(guī)定其耗散值為1;

　　(2)任意一個將牌可相隔1個或2個其他的將牌跳入空格，規(guī)定其耗散值等于跳過將牌的數目;游戲要達到的目標是使所有白將牌都處在黑將牌的左邊(左邊有無空格均可)。對這個問題，定義一個啟發(fā)函數h(n)，并給出利用這個啟發(fā)函數用算法A求解時所產生的搜索樹。可定義h為：h=B右邊的W的數目

　　很多知識對求解問題有好處，這些知識并不一定要寫成啟發(fā)函數的形式，很多情況下，也不一定能清晰的寫成一個函數的形式。由題意，在目標狀態(tài)下，一個扇區(qū)的數字之和等于12，一個相對扇區(qū)的數字之和等于24，而一個陰影扇區(qū)或者非陰影扇區(qū)的數字之和為48。

　　為此，我們可以將目標進行分解，首先滿足陰影扇區(qū)的數字之和為48。為了這個目標我們可以通過每次轉動圓盤45o實現。在第一個目標被滿足的情況下，我們再考慮第二個目標：每一個相對扇區(qū)的數字和為24。在實現這個目標的過程中，我們希望不破壞第一個目標。為此我們采用轉動90o的方式實現，這樣即可以調整相對扇區(qū)的數字和，又不破壞第一個目標。在第二個目標實現之后，我們就可以實現最終目標：扇區(qū)內的數字和為12。同樣我們希望在實現這個目標的時候，不破壞前兩個目標。為此我們采用轉動180o的方式實現。這樣同樣是即可以保證前兩個目標不被破壞，又可以實現第三個目標。

　　經過這樣的分析以后，我們發(fā)現該問題就清晰多了。當然，是否每一個第一、第二個目標的實現，都能夠實現第三個目標呢?有可能不一定。在這種情況下，就需要在發(fā)現第三個目標不能實現時，重新試探其他的第一、第二個目標。

　　4 傳教士野人問題啟發(fā)式搜索函數

　　傳教士野人問題，n個傳教士和n個野人從河的一邊擺渡到河的另一邊，為安全起見，任何時候傳教士的數目不能小于野人的數目，渡船每次渡k個人， N=5，k≤3的M-C問題，找到相應的啟發(fā)函數。定義h1=M+C-2B，其中M，C分別是在河的左岸的傳教士人數和野人人數。B=1表示船在左岸，B=0表示船在右岸。也可以定義h2=M+C，h1是滿足A*條件的，而h2不滿足。

　　要說明h(n)=M+C不滿足A*條件是很容易的，只需要給出一個反例就可以了。比如狀態(tài)(1, 1, 1)，h(n)=M+C=1+1=2，而實際上只要一次擺渡就可以達到目標狀態(tài)，其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。

　　下面我們來證明h(n)=M+C-2B是滿足A*條件的。

　　我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運到右岸，然后再有一個人將船送回來。這樣，船一個來回可以運過河2人，而船仍然在左岸。而最后剩下的三個人，則可以一次將他們全部從左岸運到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡whx04.tif次。其中分子上的"-3"表示剩下三個留待最后一次運過去。除以"2"是因為一個來回可以運過去2人，需要whx05.tif個來回，而"來回"數不能是小數，需要向上取整，這個用符號whx06.tif表示。而乘以"2"是因為一個來回相當于兩次擺

　　渡，所以要乘以2。而最后的"+1"，則表示將剩下的3個運過去，需要一次擺渡。

　　再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運到左岸。因此對于狀態(tài)(M，C，0)來說，其所需要的最少擺渡數，相當于船在左岸時狀態(tài)(M+1，C，1)或(M，C+1，1)所需要的最少擺渡數，再加上第一次將船從右岸送到左岸的一次擺渡數。因此所需要的最少擺渡數為：(M+C+1)-2+1 。其中(M+C+1)的"+1"表示送船回到左岸的那個人，而最后邊的"+1"，表示送船到左岸時的一次擺渡。

　　綜合船在左岸和船在右岸兩種情況下，所需要的最少擺渡次數用一個式子表示為：M+C-2B。其中B=1表示船在左岸，B=0表示船在右岸。 由于該擺渡次數是在不考慮限制條件下，推出的最少所需要的擺渡次數。因此，當有限制條件時，最優(yōu)的擺渡次數只能大于等于該擺渡次數。所以該啟發(fā)函數h是滿足A*條件的。

　　5 結束語

　　總之，計算機人工智能啟發(fā)式搜索函數選取的方法比較多，試圖找出問題中選取函數的相似的方法，從文中可知還沒有那一個函數可以處于絕對的地位，可以適用于所有環(huán)境。如何將各種選取啟發(fā)式搜索函數的思路結合起來，尋找各個問題選取函數的特點規(guī)律，在這個方面還是有很多的理論和實踐值得深入研究。

下一頁分享更優(yōu)秀的<<<人工智能搜索技術論文