人工智能搜索技術(shù)論文

人工智能搜索技術(shù)論文

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

　　人工智能搜索技術(shù)論文篇一

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

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

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

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

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

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

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

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

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

　　滑動積木塊游戲的棋盤結(jié)構(gòu)及某一種將牌的初始排列結(jié)構(gòu)如下：

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

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

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

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

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

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

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

　　傳教士野人問題，n個傳教士和n個野人從河的一邊擺渡到河的另一邊，為安全起見，任何時候傳教士的數(shù)目不能小于野人的數(shù)目，渡船每次渡k個人， N=5，k≤3的M-C問題，找到相應(yīng)的啟發(fā)函數(shù)。定義h1=M+C-2B，其中M，C分別是在河的左岸的傳教士人數(shù)和野人人數(shù)。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，而實(shí)際上只要一次擺渡就可以達(dá)到目標(biāo)狀態(tài)，其最優(yōu)路徑的耗散值為1。所以不滿足A*的條件。

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

　　我們分兩種情況考慮。先考慮船在左岸的情況。如果不考慮限制條件，也就是說，船一次可以將三人從左岸運(yùn)到右岸，然后再有一個人將船送回來。這樣，船一個來回可以運(yùn)過河2人，而船仍然在左岸。而最后剩下的三個人，則可以一次將他們?nèi)繌淖蟀哆\(yùn)到右岸。所以，在不考慮限制條件的情況下，也至少需要擺渡whx04.tif次。其中分子上的"-3"表示剩下三個留待最后一次運(yùn)過去。除以"2"是因?yàn)橐粋€來回可以運(yùn)過去2人，需要whx05.tif個來回，而"來回"數(shù)不能是小數(shù)，需要向上取整，這個用符號whx06.tif表示。而乘以"2"是因?yàn)橐粋€來回相當(dāng)于兩次擺

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

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

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

　　5 結(jié)束語

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

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