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

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

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

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

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

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

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

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

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

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

　　用來(lái)評(píng)估節(jié)點(diǎn)重要性的函數(shù)稱為評(píng)估函數(shù)。評(píng)估函數(shù)f(x)定義為從初始節(jié)點(diǎn)S0出發(fā)，約束地經(jīng)過(guò)節(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)路徑的評(píng)估代價(jià)，它體現(xiàn)了問(wèn)題的啟發(fā)式信息，其形式要根據(jù)問(wèn)題的特征確定，h(x)稱為啟發(fā)式函數(shù)。因此，啟發(fā)式方法把問(wèn)題狀態(tài)的描述轉(zhuǎn)換成了對(duì)問(wèn)題解決程度的描述，這一程度用評(píng)估函數(shù)的值來(lái)表示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　5 結(jié)束語(yǔ)

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

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