人工智慧搜尋技術論文
人工智慧的核心問題及啟發式搜尋函式的基本概念，介紹了4種經典問題啟發式搜尋函式的選擇及其研究中遇到的難題，並從中求解來探討解決問題的思路。以下是小編整理的的相關資料，歡迎閱讀!
篇一
摘要：闡述了人工智慧的核心問題及啟發式搜尋函式的基本概念，介紹了4種經典問題啟發式搜尋函式的選擇及其研究中遇到的難題，並從中求解來探討解決問題的思路。
關鍵詞：人工智慧;問題求解;啟發式搜尋函式
中圖分類號：TP18文獻標識碼：A文章編號：1009-3044200808-10ppp-0c
人工智慧問題廣義地說，都可以看作是一個問題求解過程，因此問題求解是人工智慧的核心問題，它通常是通過在某個可能的解答空間中尋找一個解來進行的。在問題求解過程中，人們所面臨的大多數現實問題往往沒有確定性的演算法，通常需要用搜索演算法來解決。目標和達到目標的一組方法稱為問題，搜尋就是研究這些方法能夠做什麼的過程。問題求解一般需要考慮兩個基本問題：首先是使用合適的狀態空間表示問題，其次是測試該狀態空間中目標狀態是否出現。
1 什麼是啟發式搜尋函式
在人工智慧中有很大一類問題的求解技術依賴於搜尋。啟發式方法就是採用有利於問題自身特徵資訊來引導搜尋過程的方法，在學生學習過程中啟發式函式的選取至關重要，決定整個演算法的效率與成敗。啟發式搜尋通常用於兩種不同型別的問題：1前向推力和2反向推理。前向推理一般用於狀態空間的搜尋。在前向推理中，推理是從預定義的初始狀態出發向目標狀態反向方向執行;反向推理一般用於問題歸約中。在反向推理中，推理是從給定的目標狀態向初始狀態執行。
用來評估節點重要性的函式稱為評估函式。評估函式fx定義為從初始節點S0出發，約束地經過節點x到達目標節點Sg的所有路徑中最小路徑代價的估計值。其一般形式為：
其中，gx表示從初始節點S0到節點x的實際代價;hx表示從x到目標節點Sg的最優路徑的評估代價，它體現了問題的啟發式資訊，其形式要根據問題的特徵確定，hx稱為啟發式函式。因此，啟發式方法把問題狀態的描述轉換成了對問題解決程度的描述，這一程度用評估函式的值來表示。
2 滑動積木遊戲啟發式搜尋函式
滑動積木塊遊戲的棋盤結構及某一種將牌的初始排列結構如下：
其中B表示黑色將牌，W表示白色將牌，E表示空格。遊戲的規定走法是：
1任意一個將牌可以移入相鄰的空格，規定其耗散值為1;
2任意一個將牌可相隔1個或2個其他的將牌跳入空格，規定其耗散值等於跳過將牌的數目;遊戲要達到的目標是使所有白將牌都處在黑將牌的左邊左邊有無空格均可。對這個問題，定義一個啟發函式hn，並給出利用這個啟發函式用演算法A求解時所產生的搜尋樹。可定義h為：h=B右邊的W的數目
很多知識對求解問題有好處，這些知識並不一定要寫成啟發函式的形式，很多情況下，也不一定能清晰的寫成一個函式的形式。由題意，在目標狀態下，一個扇區的數字之和等於12，一個相對扇區的數字之和等於24，而一個陰影扇區或者非陰影扇區的數字之和為48。
為此，我們可以將目標進行分解，首先滿足陰影扇區的數字之和為48。為了這個目標我們可以通過每次轉動圓盤45o實現。在第一個目標被滿足的情況下，我們再考慮第二個目標：每一個相對扇區的數字和為24。在實現這個目標的過程中，我們希望不破壞第一個目標。為此我們採用轉動90o的方式實現，這樣即可以調整相對扇區的數字和，又不破壞第一個目標。在第二個目標實現之後，我們就可以實現最終目標：扇區內的數字和為12。同樣我們希望在實現這個目標的時候，不破壞前兩個目標。為此我們採用轉動180o的方式實現。這樣同樣是即可以保證前兩個目標不被破壞，又可以實現第三個目標。
經過這樣的分析以後，我們發現該問題就清晰多了。當然，是否每一個第一、第二個目標的實現，都能夠實現第三個目標呢?有可能不一定。在這種情況下，就需要在發現第三個目標不能實現時，重新試探其他的第一、第二個目標。
4 傳教士野人問題啟發式搜尋函式
傳教士野人問題，n個傳教士和n個野人從河的一邊擺渡到河的另一邊，為安全起見，任何時候傳教士的數目不能小於野人的數目，渡船每次渡k個人， N=5，k≤3的M-C問題，找到相應的啟發函式。定義h1=M+C-2B，其中M，C分別是在河的左岸的傳教士人數和野人人數。B=1表示船在左岸，B=0表示船在右岸。也可以定義h2=M+C，h1是滿足A*條件的，而h2不滿足。
要說明hn=M+C不滿足A*條件是很容易的，只需要給出一個反例就可以了。比如狀態1, 1, 1，hn=M+C=1+1=2，而實際上只要一次擺渡就可以達到目標狀態，其最優路徑的耗散值為1。所以不滿足A*的條件。
下面我們來證明hn=M+C-2B是滿足A*條件的。
我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運到右岸，然後再有一個人將船送回來。這樣，船一個來回可以運過河2人，而船仍然在左岸。而最後剩下的三個人，則可以一次將他們全部從左岸運到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡whx04.tif次。其中分子上的"-3"表示剩下三個留待最後一次運過去。除以"2"是因為一個來回可以運過去2人，需要whx05.tif個來回，而"來回"數不能是小數，需要向上取整，這個用符號whx06.tif表示。而乘以"2"是因為一個來回相當於兩次擺
渡，所以要乘以2。而最後的"+1"，則表示將剩下的3個運過去，需要一次擺渡。
再考慮船在右岸的情況。同樣不考慮限制條件。船在右岸，需要一個人將船運到左岸。因此對於狀態M，C，0來說，其所需要的最少擺渡數，相當於船在左岸時狀態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表示船在右岸。 由於該擺渡次數是在不考慮限制條件下，推出的最少所需要的擺渡次數。因此，當有限制條件時，最優的擺渡次數只能大於等於該擺渡次數。所以該啟發函式h是滿足A*條件的。
5 結束語
總之，計算機人工智慧啟發式搜尋函式選取的方法比較多，試圖找出問題中選取函式的相似的方法，從文中可知還沒有那一個函式可以處於絕對的地位，可以適用於所有環境。如何將各種選取啟發式搜尋函式的思路結合起來，尋找各個問題選取函式的特點規律，在這個方面還是有很多的理論和實踐值得深入研究。
下一頁分享更優秀的<<<